Find the number of permutations $\sigma \in S_n$ with exactly $c_i$ cycles of length $i$ for each $i$.

Question

Let $n$ be a positive integer, and let $(c_1, \ldots, c_n)$ be a sequence of integers such that $\sum_{i=1}^n ic_i = n$. Show that the number of permutations $\sigma \in S_n$ with exactly $c_i$ cycles of length $i$ for each $i$ is given by $$\frac{n!}{1^{c_1} c_1! 2^{c_2} c_2! \cdots n^{c_n} c_n!}$$

Here, I believe that the approach would be to define a surjection $f: S_n \to X$ and then show that it is surjective, and that $|f^{-1}(\sigma)| = 1^{c_1} c_1! 2^{c_2} c_2! \cdots n^{c_n} c_n!$ for any $\sigma \in X$.

However, I still confused and I don't know how to proceed.

Answer 1

Supposing our sequence $(c_1, c_2, \ldots, c_n)$ is such that $\sum_{q=1}^n q c_q = n$ with some $c_q$ possibly zero so that there are $c_q$ cycles of length $q$ we first have to select the values from $n$ that go on every cycle by a multinomial coefficient

$$\frac{n!}{\prod_{q=1}^n q!^{c_q}}$$

Now a set of $q$ values gives $q!/q$ cycles for a contribution of

$$\prod_{q=1}^n \frac{q!^{c_q}}{q^{c_q}}$$

and the ordering of the $c_q$ cycles of the same length does not matter, giving

$$\prod_{q=1}^n \frac{1}{c_q!}.$$

Collecting everything we find

$$\frac{n!}{\prod_{q=1}^n q!^{c_q}} \prod_{q=1}^n \frac{q!^{c_q}}{q^{c_q}} \prod_{q=1}^n \frac{1}{c_q!} = \frac{n!}{\prod_{q=1}^n c_q! q^{c_q}}$$

as claimed.

Answer 2

The surjection is given by writing the permutation in one line notation, and then breaking into consecutive blocks as follows: $c_1$ blocks of size $1$, $c_2$ block of size $2$, etc. Each of those blocks is then interpreted as a cycle, so the entire thing is a permutation in cycle notation. For example,

\begin{align} n &= 14\\ (c_1,c_2,c_3,\dots)&=(2,3,2,0,0,0\dots)\\ \pi&=[1, 2, 3, 4, 5, 6, 7, 8, 9 , 10, 11, 12, 13, 14]&\text{one-line notation}\\ f(\pi)&=(1)(2)(3\;4)(5\;6)(7\;8)(9\;10\;11)(12\;13\;14)&\text{cycle notation} \end{align}

To see why $|f^{-1}(\sigma)|=1^{c_1}c_12^{c_2}c_2!\cdots n^{c_n}c_n!$, note that each of the cycles of length $i$ can be rearranged in $i$ ways, by rotating any of the $i$ elements to the first position, while giving the same cycle. There are $c_i$ cycles of length $i$ for each $i$, contributing the factors of $i^{c_i}$. Then, rearranging the order of the cycles of any given length also results in the same cycle structure. The $c_i$ cycles of any given length can be rearranged in $c_i!$ ways. In the above example, starting with $$ \pi'=[1,2,5,6,7,8,3,4,10,11,9,14,12,13] $$ yields the same permutation $f(\pi)$. The only difference is the cycles of length $2$ appear in a different order, and the cycles of length $3$ are written with different elements first.