How many permutations in S(n) have this particular type?

Question

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?

Answer 1

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.

For example, if $n=7$ we might have

$$\sigma=1^02^23^14^05^06^07^0=2^23^1\;.$$

(It’s common to omit the zero exponents.)

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.

For $n=7$ that might be $3521476$.

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.

In the example we get $(35)(21)(476)$.

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.

Another cycle notation for $(35)(21)(476)$ is $(12)(53)(764)$; we get this if we start with the one-line permutation $1253764$ of $[7]$.

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.

A cycle notation for $(35)(21)(476)$ with its cycles listed in non-decreasing order of length must start with $2$ $2$-cycles, but they can appear in either order; that introduces a factor of $2$ into the calculation of $m$.

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$.

In our example this is simply a factor of $0!2!1!0!0!0!0!=2!1!=2$: the only freedom that we have in ordering our three cycles is in which of the two $2$-cycles we put first.

But a $k$-cycle always has $k$ different cycle representations, since we can list it starting with any of its $k$ elements.

The $2$-cycle $(35)$ can also be written $(53)$; the $2$-cycle $(21)$ can also be written $(12)$; and the $3$-cycle $(476)$ can also be written $(764)$ and $(647)$.

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}}\;.$$

In the example that is $$\frac{7!}{2!1!\cdot 2^2\cdot3^1}=\frac{5040}{24}=210\;.$$ As a quick check, we can calculate this directly. There are $\binom73=35$ ways to choose the elements of the $3$-cycle and then $2$ different $3$-cycles that can be made from those $3$ elements; that’s a factor of $35\cdot2=70$. There are $3$ ways to divide the remaining $4$ elements into two pairs, and each pair can be formed into a cycle in only one way, so there are $3$ possible pairs of $2$-cycles to be combined with a given $3$-cycle. Thus, there are $70\cdot3=210$ possible permutation of $[7]$ of type $2^23^1$.