10. Let $S$ be a set of size 11. A random 12-tuple $\left(s_{1}, s_{2}, \ldots, s_{12}\right)$ of elements of $S$ is chosen uniformly at random. Moreover, let $\pi: S \rightarrow S$ be a permutation of $S$ chosen uniformly at random. The probability that $s_{i+1} \neq \pi\left(s_{i}\right)$ for all $1 \leq i \leq 12$ (where $s_{13}=s_{1}$ ) can be written as $\frac{a}{b}$ where $a$ and $b$ are relatively prime positive integers. Compute $a$.
Answer: 1000000000004
Solution: Given a permutation $\pi$, let $\nu(\pi)$ be the number of fixed points of $\pi$. We claim that if we fix $\pi$, then the probability that the condition holds, over the randomness of $s_{i}$, is $\frac{10^{12}+\nu\left(\pi^{12}\right)-1}{11^{12}}$. Note that a point in $S$ is a fixed point of $\pi^{12}$ if and only if the length of its cycle in $\pi$ is $1,2,3,4$, or 6 , which happens with probability $\frac{5}{11}$, as each cycle length from 1 to 11 is equally likely. Therefore, the answer is
$$
\mathbb{E}_{\pi}\left[\frac{10^{12}+\nu\left(\pi^{12}\right)-1}{11^{12}}\right]=\frac{10^{12}+4}{11^{12}} .
$$

Since 11 does not divide $10^{12}+4$ this fraction is simplified.
We now prove the claim. Instead of counting $\left(s_{1}, s_{2}, \ldots, s_{12}\right)$, we count tuples $\left(t_{1}, t_{2}, \ldots, t_{12}\right)$ so that $t_{i} \neq t_{i+1}$ for $1 \leq i \leq 11$ and $t_{1} \neq \pi^{12}\left(t_{12}\right)$. A bijection between the two is to let $t_{i}=\pi^{-i}\left(s_{i}\right)$. To do this, fix a $t_{1}$. If $t_{1}$ is a fixed point of $\pi^{12}$, we need to count the possibilities for $t_{2}, \ldots, t_{12}$ so that $t_{1} \neq t_{2}, t_{2} \neq t_{3}, \ldots, t_{12} \neq t_{1}$. This can be done via recursion: if $a_{k}$ is the number of $t_{2}, \ldots, t_{k+1}$ so that $t_{1} \neq t_{2}, t_{2} \neq t_{3}, \ldots, t_{k+1} \neq t_{1}$, then $a_{0}=0$, while for $n \geq 0$ we have $a_{n+1}=9 a_{n}+10\left(10^{n}-a_{n}\right)=$ $10^{n+1}-a_{n}$; thus $a_{11}=10^{11}-10^{10}+\cdots+10^{1}=\frac{1}{11}\left(10^{12}+10\right)$. Similarly, if $t_{1}$ is not a fixed point of $\pi^{12}$, there are $\frac{1}{11}\left(10^{12}-1\right)$ ways. Therefore, number of possible $\left(t_{1}, \ldots, t_{n}\right)$ is
$$
\frac{10^{12}}{11}\left(\nu\left(\pi^{12}\right)+\left(11-\nu\left(\pi^{12}\right)\right)\right)+\frac{1}{11}\left(10 \nu\left(\pi^{12}\right)-\left(11-\nu\left(\pi^{12}\right)\right)\right)=10^{12}+\nu\left(\pi^{12}\right)-1,
$$
as desired.