TAOCP 1.3.3 Exercise 21
Let a permutation of $n$ objects have exactly $\alpha_k$ cycles of length $k$ for each $k \ge 1$, with only finitely many nonzero $\alpha_k$.
Section 1.3.3: Applications to Permutations
Exercise 21. [M22] What is the probability $P(n;\alpha_1,\alpha_2,\ldots)$ that a permutation of $n$ objects has exactly $\alpha_1$ one-cycles, $\alpha_2$ two-cycles, etc.?
Verified: yes
Solve time: 42s
Solution
Let a permutation of $n$ objects have exactly $\alpha_k$ cycles of length $k$ for each $k \ge 1$, with only finitely many nonzero $\alpha_k$. The constraint on the parameters is
$$ \sum_{k \ge 1} k \alpha_k = n. $$
Let $N(n;\alpha_1,\alpha_2,\ldots)$ denote the number of such permutations. The probability is
$$ P(n;\alpha_1,\alpha_2,\ldots) = \frac{N(n;\alpha_1,\alpha_2,\ldots)}{n!}. $$
A permutation is constructed by partitioning the $n$ labeled objects into disjoint cycles, then assigning cyclic order within each cycle. The counting is performed in stages.
First, partition the set of $n$ elements into $\alpha_k$ groups of size $k$ for each $k$. If all cycles were considered as ordered lists, the number of ways to arrange the $n$ objects in a linear sequence is $n!$. From such a sequence, cycles are formed by breaking it into blocks of sizes $k$ according to the prescribed multiset of cycle lengths. This overcounts in two ways.
Within each cycle of length $k$, there are $k$ cyclic rotations that produce the same cycle in cycle notation $(x_1 x_2 \ldots x_k)$, since
$$ (x_1 x_2 \ldots x_k) = (x_2 \ldots x_k x_1) = \cdots = (x_k x_1 \ldots x_{k-1}). $$
Hence each $k$-cycle contributes a factor $k$ of overcounting.
Furthermore, the $\alpha_k$ cycles of the same length $k$ are indistinguishable as unordered blocks in the final permutation. Permuting these $\alpha_k$ cycles among themselves does not change the permutation, producing an additional factor $\alpha_k!$ of overcounting.
For each fixed $k$, these corrections contribute a factor $k^{\alpha_k}\alpha_k!$. Multiplying over all $k$ yields total overcounting factor
$$ \prod_{k \ge 1} k^{\alpha_k}\alpha_k!. $$
Hence the number of permutations with cycle structure $(\alpha_1,\alpha_2,\ldots)$ is
$$ N(n;\alpha_1,\alpha_2,\ldots) = \frac{n!}{\prod_{k \ge 1} k^{\alpha_k}\alpha_k!}. $$
Dividing by $n!$ gives the probability
$$ P(n;\alpha_1,\alpha_2,\ldots) = \frac{1}{\prod_{k \ge 1} k^{\alpha_k}\alpha_k!}. $$
This completes the proof. ∎
$$ \boxed{P(n;\alpha_1,\alpha_2,\ldots)=\frac{1}{\prod_{k \ge 1} k^{\alpha_k}\alpha_k!}} $$