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

As discussed e.g. in this other question, as well as the relevant Wikipedia page, we have $$\frac{x!}{(x-n)!} = \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+k-1)=(x-1+k)!/(x-1)!$$.

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? Why are the coefficients of $$x^{\overline n}$$ connected to the number of this particular type of permutations?

## 2 Answers

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

• could you go into a little bit more detail? When counting the number of terms with a given power $x^k$, you also need to take into account the ways in which you can choose the rows, no? In your counting you seem to be only taking into account the terms $x^k$ resulting from taking $1$s in the first $n-k$ rows. – glS Oct 24 '20 at 17:05

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.

• Now, if you want to really grasp combinatorially this concept, I suggest you compute an expression for the numbers and think about cycle structure of permutations. math.stackexchange.com/questions/3630227/… – Phicar Oct 23 '20 at 14:59