4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You are asked not the numbe of all $\sigma\in S(N)$ but the number of those $\sigma$ which have a given type (that is, have $c_1$ cycles of length 1, $c_2$ cycles of length 2, etc. with $c_1,c_2,\dots $ given). $\endgroup$ – Vladimir Sep 10 '16 at 19:12
  • $\begingroup$ @Vladimir I think I am understanding a bit better now. So if $S(n)$ is all permutations of the set $\{1,2,3\}$, then the set of all $\sigma$s is $\{1^32^03^0, 1^12^13^0,1^0,2^0,3^1\}$, correct? $\endgroup$ – Tyler Durden Sep 10 '16 at 19:16
  • $\begingroup$ Not exactly; you have permutations (1)(2)(3), which sends $1\mapsto1,2\mapsto2,3\mapsto3$ ($c_1=3$, $c_2=c_3=0$); (1,2)(3) ($1\mapsto2, 2\mapsto1,3\mapsto3$; $c_1=1,c_2=1,c_3=0$), etc. $\endgroup$ – Vladimir Sep 10 '16 at 19:20
  • $\begingroup$ @Tyler: Yes, it’s correct, apart from the two extraneous commas in the third type. The unique permutation of type $1^3$ is the identity permutation, $(1)(2)(3)$. There are $3$ of type $1^12^1$: $(1)(23),(2)(13)$, and $(3)(12)$. And there are $2!=2$ of type $3^1$, $(123)$ and $(132)$. $\endgroup$ – Brian M. Scott Sep 10 '16 at 19:22
  • $\begingroup$ Sorry about those commas! I meant: I think I am understanding a bit better now. So if $S(n)$ is all permutations of the set $\{1,2,3\}$, then the set of all $\sigma$s is $\{1^32^03^0, 1^12^13^0,1^02^03^1\}$, correct? $\endgroup$ – Tyler Durden Sep 10 '16 at 19:23
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the answer! This helped my understanding immensely. $\endgroup$ – Tyler Durden Sep 10 '16 at 20:32
  • $\begingroup$ Tyler: You’re welcome! Glad it helped. $\endgroup$ – Brian M. Scott Sep 10 '16 at 20:41
  • $\begingroup$ Great piece of exposition! (I have made a little edit to clarify that the meaning of the letter $\sigma$ in your post is completely different from that in the original question. I hope this is not against the spirit of your post.) $\endgroup$ – darij grinberg Apr 15 '17 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.