AMC 12 Mock Exam 1 Problem 21

Problem 21 of 25

A function $\sigma:\{1,2,\dots,10\}\to\{1,2,\dots,10\}$ is chosen uniformly at random from among the $10!$ bijections of $\{1,2,\dots,10\}$ to itself. Let $N$ be the number of integers $x$ in $\{1,2,\dots,10\}$ for which $\sigma(\sigma(\sigma(x)))=x$ . What is the expected value of $N$ ?

Show solution

Solution

Decompose $\sigma$ into disjoint cycles. We have $\sigma^3(x)=x$ exactly when the length $\ell$ of the cycle containing $x$ divides $3$ , i.e., $\ell=1$ or $\ell=3$ .

Fix $x$ . The number of permutations in which $x$ lies in a cycle of length $\ell$ is the same for every $\ell\in\{1,\dots,10\}$ : choose the ordered list of the other $\ell-1$ elements of its cycle in $\frac{9!}{(10-\ell)!}$ ways, and permute the remaining $10-\ell$ elements arbitrarily in $(10-\ell)!$ ways, for a total of $9!$ . So $x$ lies in a cycle of any given length with probability $\frac{9!}{10!}=\frac1{10}$ .

Hence $P(\sigma^3(x)=x)=\frac1{10}+\frac1{10}=\frac15$ . By linearity of expectation, $E[N]=10\cdot\frac15=\boxed{2}$ .

Tagged: random permutations, linearity of expectation, cycles

Answer choices

Solution