Why are Stirling numbers of the first kind related to the number of permutations with $k$ cycles?

Question

As discussed e.g. in this other question, as well as the relevant Wikipedia page, we have $$(x)_n \equiv x(x-1)\cdots (x-(n-1)) = \sum_{k=0}^n s(n,k) x^k,$$ where $s(n,k)$ are the so-called Stirling numbers of the first kind. These are also written as $$s(n,k) = (-1)^{n-k} \left[\begin{matrix}n\\k \end{matrix}\right],$$ where $\left[\begin{smallmatrix}n\\k \end{smallmatrix}\right]$ are the unsigned Stirling numbers of the first kind, which are also the coefficients of the polynomial expansion of $x^{\overline n}\equiv x(x+1)\cdots (x+(n-1))$.

It is not hard to see that these are tightly related to sums of powers of integers: $$x^{\bar n} = x^n + x^{n-1}\left(\sum_{k=1}^n(k-1)\right) + x^{n-2}\left(\sum_{i<j=1}^{n}(i-1)(j-1)\right)+\cdots + x\left(\prod_{k=1}^{n}(k-1)\right).$$

The unsigned Stirling numbers $\left[\begin{smallmatrix}n\\k \end{smallmatrix}\right]$ are also equal to the number of permutations of $n$ elements which are composed of exactly $k$ disjoint cycles. E.g. $\left[\begin{smallmatrix}3\\2 \end{smallmatrix}\right]=3$ because the permutations in $S_3$ with two cycles are (in cycle notation), $(12)$, $(13)$, and $(23)$.

Is there a good way to see the connection between these two definitions? More specifically, why are the coefficients of $x^{\overline n}$ connected to the number of this particular type of permutations? Equivalently, why does counting these classes of permutations result in expressions involving these sums of products of integers?

Answer 1

The easiest way, probably, is by recursion. Notice that $x^{\overline{n+1}}=(x+n)x^{\overline{n}}$ just by distributing the product, this creates the recursion $${n+1 \brack k}={n \brack k-1}+n\cdot {n \brack k}.$$ The first terms you can think about it by placing $n+1$ as a fix point(so you create a new cycle) and the other term can be seen as placing $n+1$ as the pre-image of some element $x$ and the old pre-image as the preimage of $n+1.$ These choice of $x$ can be done in $n$ ways.

Answer 2

There is a nice proof, which is similar to the proof that $$ (x+1)^n=\sum_{k=0}^n\binom{n}kx^k $$ by counting the number of ways to expand $(x+1)^n$ with the distributive property.

It is helpful to write $x^{\overline n}$ as $$ (x+1+\dots+1)\cdots (x+1+1)(x+1)x $$ When you expand this out with the distributive property, there are $n!$ terms, as you have $n$ choices for the term from $(x+1+\dots+1)$, then $n-1$ choices from the second factor, and so on down to $1$ choice from the $x$ factor. When choosing from the $k^{th}$ factor, there are $n-k+1$ choices, and exactly one choice will increase the resulting power of $x$.

On the other hand, consider the following method of choosing a permutation, $\pi$. You first choose $\pi(1)$, from one of $n$ options. Then, you choose $\pi(\pi(1))$, then $\pi(\pi(\pi(1)))$, and so on until you complete a cycle. Then, you choose $\pi(s)$, where $s$ is the smallest unassigned element, etc. During the $k^{th}$ stage of this process, you have $n-k+1$ options. Exactly one of these leads to the creation of a cycle.

After some thought, these processes are exactly the same, so that the number of ways to choose a permutation with $k$ cycles is the coefficient of $x^k$ in the expansion of $x^{\overline n}$.

Answer 3

$\require{cancel}$

This answer contains exactly the same information as that of Mike's. It is just more elaborate.

Write the product $x^{\overline{n}}$

$$x^{\overline{n}}=\left(x+\underset{n-1\text{ times}}{\underbrace{1+\dots+1}}\right)\cdots\left(1+x\right)x.$$

Imagine the process of expanding this product from the left. We record which summand (from the left) we choose on the $k$th term $\left(x+\underset{n-k\text{ times}}{\underbrace{1+\dots+1}}\right)$. Say that you chose the $i_k$th summand from the $k$th term. We define a sequence $j_1,\dots,j_n$ by

$$j_{k+1}=i_{k+1}\text{th smallest element in }\{1,\dots,n\}\setminus\{j_1,\dots,j_{k}\}.$$

The sequence $j_1\dots j_{n}$ is a reordering of $1,\dots ,n$. Now for each $k$ such that $i_k=1,$ put a slash "/" between $j_{k}$ and $j_{k+1}.$ This means that if you chose $i$ $x$'s, then you have $i$ slashes. The resulting sequence looks like

$$j_1\dots j_{k_{1}}/j_{k_1+1}\dots j_{k_2}/\dots/j_{k_{i}+1}\dots j_{n},$$

and we can regard this sequence as a permutation which is the product of $i$ cycles. Since every such permutation arises uniquely in this way, the coefficient of $x^i$ in $x^{\overline{n}}$ counts the number of permutations which is the product of precisely $i$ cycles.

---

As an example, consider the case $n=4$ and $i_1=3$, $i_2=1$, $i_3=2$, and $i_4=1$. In this case $$ \begin{align} j_1&= 3\text{rd smallest element in} \{1,2,3,4\}=3,\\ j_2&= 1\text{st smallest element in} \{1,2,\cancel{3},4\}=1,\\ j_3&= 2\text{nd smallest element in } \{\cancel{1},2,\cancel{3},4\}=4,\\ j_4&= 1\text{st smallest element in} \{\cancel{1},2, \cancel{3},\cancel{4}\}=2,\\ \end{align} $$ so the resulting permutation will be $(31)(42)$.

Answer 4

I will present a way to count the number of permutations in $S_n$ composed of exactly $k\le n$ cycles, that will naturally give expressions of the form $\sum_{i_1\cdots i_k=1}^{n} (i_1-1)\cdots(i_k-1)$, which as mentioned in the question equals ${n\brack k}$.

Specific example: ${4\brack2}$

To this end, I'll start from a specific example, and only afterward discuss the general approach. Consider then the permutations in $S_4$ composed of two cycles. There are two cycle types compatible with having two cycles: $(22)$ and $(31)$. We will list the possible permutations $\pi\in S_4$ as follows:

1. Start asking where $1$ is sent by $\pi$, that is, what is $\pi(1)$. If $\pi(1)=1$, then we are dealing with a (31) cycle. We then take the lowest "unused" integer (so in this case $2$) and ask what is $\pi(2)$. Now, because we want two cycles overall, $2$ must belong to a 3-cycle, meaning $2\neq\pi(2)\neq\pi^2(2)$ and $\pi^3(2)=2$. Counting the corresponding number of permutations is easy: $1$ and $2$ are fixed, and the remaining number of 3-cycles are $2\times1=2$. In other words, we just counted the number of permutations of the form $$(s)(s\,{\bullet}\,{\bullet}).$$ We'll use this notation again in the following: each $s$ means "fill this place with the smallest available integer", and each $\bullet$ means "any available integer can be put here". So to be more explicit, the two $S_4$ permutations compatible with $(s)(s\,{\bullet}\,{\bullet})$ are $(1)(234)$ and $(1)(243)$.

2. If $\pi(1)\neq1$ but $\pi^2(1)=1$, then we have a $(22)$ cycle structure. We will use the same approach as above to count these: we consider permutations of the form $$(s\,{\bullet})(s\,{\bullet}),$$ which includes $3\times1$ permutations, and more specifically, the permutations $(12)(34), (13)(24)$, and $(14)(23)$.

3. The last remaining possibility is that $1$ fits in a 3-cycle. This means cycles of the form $$(s\,{\bullet}\,{\bullet})(s).$$ There are $3\times2$ of these, which are explicitly $$(123)(4),(124)(3),(132)(4),(134)(2),(142)(3),(143)(2).$$ Let me stress that, while these permutations have the same cycle structure as in the point 1 above, there is no overlap between the permutations in $(s\,{\bullet}\,{\bullet})(s)$ and those in $(s)(s\,{\bullet}\,{\bullet})$, meaning we can simply sum the individual counts to get the total number of permutations of cycle type $(31)$.

So, overall, we found that the number of $S_4$ permutations with two cycles equals $2\cdot1+3\cdot1+3\cdot2$, which is exactly the expression we were looking for.

General case

More generally, our approach to count $S_n$ permutations with $k$ cycles is to count such permutations by writing all possible expressions with $s$ and $\bullet$ like above containing $k$ cycles. This, however, leaves the problem of having to "select" the appropriate cycle structure when writing down the expressions. Fortunately, this is not really a problem: we can observe that the parentheses in the above expressions are completely redundant: we could have equivalently wrote $ss{\bullet}{\bullet}$ and $s{\bullet}s{\bullet}$ with no ambiguity as what is the corresponding cycle structure. The strings are understood as prescribing that a new cycle is started every time we get an "$s$" symbol.

We can thus conclude that the possible $S_n$ permutations with $k$ cycles are all and only those coming from strings of length $n$ containing "$s$" and "$\bullet$", with exactly $k$ copies of "$s$", with the additional rule that the first symbol is always an "$s$".

As an additional example, that means to count ${5\brack 2}$ we consider strings of the form $$sss\,{\bullet}\,{\bullet}, \qquad ss\,{\bullet}\,s\,{\bullet}, \qquad ss\,{\bullet}\,{\bullet}\,s, \qquad s\,{\bullet}\,ss\,{\bullet}, \qquad s\,{\bullet}\,s\,{\bullet}\,s, \qquad s\,{\bullet}\,{\bullet}\,ss. $$ It is easy to count the number of permutations in each of this strings: we just multiply the positions corresponding to each of the $\bullet$ in the string, counting positions from $1$ from the right. So for the example above, we have the correspondence: $$sss\,{\bullet}\,{\bullet} \to 2\times1, \qquad ss\,{\bullet}\,s\,{\bullet} \to 3\times1, \qquad ss\,{\bullet}\,{\bullet}\,s \to 3\times2, \\ s\,{\bullet}\,ss\,{\bullet} \to 4\times1, \qquad s\,{\bullet}\,s\,{\bullet}\,s \to 4\times2, \qquad s\,{\bullet}\,{\bullet}\,ss \to 4\times3. $$ As an additional consistency check, consider the permutations in $ss\,{\bullet}\,s\,{\bullet}$, which are $(1)(23)(45),(1)(24)(35),(1)(25)(34)$.

Summing all of these we get the expressions we wanted: ${5\brack2}=\sum_{i<j=1}^5 (i-1)(j-1)$.