TAOCP 1.3.3 Exercise 20
Let r=\alpha_1+\alpha_2+\alpha_3+\cdots be the total number of cycles of the permutation, including the one-cycles.
Section 1.3.3: Applications to Permutations
Exercise 20. [M20] Given that all singleton cycles are written out explicitly, how many different ways are there to write the cycle notation of a permutation that has $\alpha_1$ one-cycles, $\alpha_2$ two-cycles, ... ? (See exercise 5.)
Verified: yes
Solve time: 2m07s
Solution
Let
$$ r=\alpha_1+\alpha_2+\alpha_3+\cdots $$
be the total number of cycles of the permutation, including the one-cycles.
Two independent choices determine a written cycle notation for a fixed permutation.
1. Ordering of the cycles
The permutation has $r$ specific cycles. Even when two cycles have the same length, they contain different elements and are therefore different cycles.
For example,
$$ (12)(34) $$
and
$$ (34)(12) $$
are different written notations.
Hence every permutation of the $r$ cycles gives a distinct cycle notation. The number of possible cycle orders is therefore
$$ r!. $$
No division by $\alpha_m!$ is appropriate, because cycles of equal length are still distinct cycles.
2. Choice of starting point in each cycle
An $m$-cycle
$$ (a_1a_2\cdots a_m) $$
may be written starting with any of its $m$ elements:
$$ (a_1a_2\cdots a_m),\quad (a_2a_3\cdots a_ma_1),\quad \ldots,\quad (a_ma_1\cdots a_{m-1}). $$
Thus each $m$-cycle has exactly $m$ possible written forms.
Since there are $\alpha_m$ cycles of length $m$, the total number of choices of starting points is
$$ \prod_{m\ge1} m^{\alpha_m}. $$
For $m=1$, this contributes the factor $1^{\alpha_1}=1$, consistent with the convention that singleton cycles are written explicitly.
3. Total number of cycle notations
The choice of cycle order and the choice of starting point in each cycle are independent. Therefore the total number of different ways to write the cycle notation is
$$ r!\prod_{m\ge1} m^{\alpha_m}. $$
Substituting $r=\sum_{m\ge1}\alpha_m$, we obtain
$$ \boxed{ \left(\sum_{m\ge1}\alpha_m\right)! \prod_{m\ge1} m^{\alpha_m} }. $$
This is the number of distinct cycle notations for a permutation having $\alpha_1$ one-cycles, $\alpha_2$ two-cycles, and so on. ∎