I'm working through the textbook A Course in Enumeration. In the section about permutations and Stirling numbers, I'm having trouble understanding problem 1.45. It is:
We fix $n \in \mathbb{N}$, and we let $S(n)$ be the $n$-th symmetric group.
Define the type of a permutation $\sigma \in S(n)$ to be the formal expression $1^{c_1}2^{c_2}\ldots
n^{c_n}$, where $c_i$ is the number of cycles in $\sigma$ of length $i$; thus
$\sum_{i=1}^nic_i=n$.
Now, fix nonnegative integers $c_1, c_2, \ldots, c_n$ satisfying $\sum_{i=1}^nic_i=n$.
Show that the number of $\sigma \in S(n)$ with type $1^{c_1}2^{c_2}\ldots n^{c_n}$ equals
$\dfrac{n!}{1^{c_1}c_1!2^{c_2}c_2!\ldots n^{c_n}c_n!}$.
I haven't tried much (but I have searched Google and MSE) as I'm wrapping my head around what exactly this is asking and what "type" means.
Why isn't the number of $\sigma \in S(n)$ just $n!$? Can't all permutations be described in that "type" $\sigma$?
Thanks!
Edit: This question ends up with the same answer, but the answer confuses me. Maybe a combinatorial explanation would help?
Best Answer
The proof given by anon at the question to which you linked in the edit is the simplest one that I know; let me see if I can explain it a little more clearly. We want to count the permutations of $[n]$ of type $\sigma=1^{c_1}2^{c_2}\ldots n^{c_n}$ (where we are using the letter $\sigma$ for the type, not the permutation). These are the permutations that have $c_1$ $1$-cycles, $c_2$ $2$-cycles, and so on when written in cycle notation.
Here is a procedure for generating all of the permutations of $[n]$ of a given type $\sigma$; I’ll illustrate it with the same example. First write down an arbitrary permutation of $[n]$ in one-line notation.
Working from left to right, insert pairs of parentheses to make this cycle notation for a permutation of type $\sigma$, making sure that the lengths of the cycles are non-decreasing from left to right. There is only one way to do this.
It’s clear that by starting with each of the $n!$ permutations of $[n]$, we generate in this way cycle notations for precisely the permutations of $[n]$ of type $\sigma$. Unfortunately, we generate the same permutation multiple times, once for each of its possible cycle notations that has the cycles listed in non-decreasing order of length.
If each permutation of type $\sigma$ is counted the same number of times, say $m$ times, then we can compensate for the overcounting simply by dividing by $m$: there must be $\frac{n!}m$ permutations of $[n]$ of type $\sigma$. The problem now is to find $m$ given $\sigma$.
Let’s look first at the example.
More generally, if we have a permutation $\pi$ of $[n]$ of type $\sigma$, any cycle notation for it whose cycles are listed in non-decreasing order of length must start with the $c_1$ $1$-cycles, but they can appear in any of $c_1!$ different orders. They must be followed by the $c_2$ $2$-cycles, but those $2$-cycles can appear in any of $c_2!$ different orders. Proceeding in similar fashion, we see that just changing the orders in which the $k$-cycles are listed for each $k$ introduces a factor of $c_1!c_2!\ldots c_n!$ into the calculation of $m$.
But a $k$-cycle always has $k$ different cycle representations, since we can list it starting with any of its $k$ elements.
More generally, each of the $c_k$ $k$-cycles of $\pi$ can be written in any of $k$ different ways, so once the order of the $c_k$ $k$-cycles has been chosen, we can write each of them in $k$ ways, for a total of $k^{c_k}$ different ways of writing those $k$ cycles in that same order.
Putting the pieces together, we have $c_1!c_2!\ldots c_n!$ ways to order the cycles in non-decreasing order of length. Once one of those orders has been chosen, for each $k=1,\ldots,n$ there are $k^{c_k}$ ways to write the $c_k$ $k$-cycles. Thus, the total number of one-line permutations of $[n]$ that give rise to $\pi$ is
$$m=c_1!c_2!\ldots c_n!1^{c_1}2^{c_2}\ldots n^{c_n}\;,$$
independent of $\pi$. We are overcounting by a fixed factor, so the number of permutations of type $\sigma$ must be
$$\frac{n!}{c_1!c_2!\ldots c_n!1^{c_1}2^{c_2}\ldots n^{c_n}}\;.$$