1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – glS Oct 24 '20 at 17:05
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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/… $\endgroup$ – Phicar Oct 23 '20 at 14:59

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.