0

How to prove that the number of $[n]$ permutations with $k$ cycles is equal with $|s(n,k)|$?

Marko Polo
  • 329
  • 1
    That’s how I usually define the unsigned Stirling numbers of the first kind, so for me there’s nothing to prove. What definition are you using? – Brian M. Scott May 15 '16 at 22:48
  • We are using the polynomial $F_n(x)=x(x-1)...(x-n+1)$ and the factors of that polynomial are the Stirling numbers of The First Kind.Ie $F_n(x)=\sum_{k=0}^{n} s(n,k)x^k$ – Marko Polo May 15 '16 at 23:03
  • Even the most simple answer would help. – Marko Polo May 15 '16 at 23:08

1 Answers1

1

You have

$$x^{\underline n}=\sum_{k=0}^ns(n,k)x^k\;,$$

where $x^{\underline n}=x(x-1)\ldots(x-n+1)$. Notice that if you replace $x^{\underline n}$ by

$$x^{\overline n}=x(x+1)\ldots(x+n-1)\;,$$

you get the absolute values of the same coefficients:

$$x^{\overline n}=\sum_{k=0}^n|s(n,k)|x^k\;.$$

Now

$$\begin{align*} \sum_{k=0}^n|s(n,k)|x^k&=x^{\underline n}\\ &=(x+n-1)x^{\overline{n-1}}\\ &=(x+n-1)\sum_{k=0}^{n-1}|s(n-1,k)|x^k\\ &=\sum_{k=0}^{n-1}|s(n-1,k)|x^{k+1}+\sum_{k=0}^{n-1}(n-1)|s(n-1,k)|x^k\\ &=\sum_{k=1}^n|s(n-1,k-1)|x^k+\sum_{k=0}^{n-1}(n-1)|s(n-1,k)|x^k\\ &=|s(n-1,n-1)|x^n+\sum_{k=1}^{n-1}\big(|s(n-1,k-1)|+(n-1)|s(n-1,k)|\big)x^k+(n-1)|s(n-1,0)|\\ &=x^n+\sum_{k=1}^{n-1}\big(|s(n-1,k-1)|+(n-1)|s(n-1,k)|\big)x^k\\ &=\sum_{k=0}^{n-1}\big(|s(n-1,k-1)|+(n-1)|s(n-1,k)|\big)x^k\;, \end{align*}$$

so

$$|s(n,k)|=|s(n-1,k-1)|+(n-1)|s(n-1,k)|\;.$$

Now show that the number of permutations of $[n]$ with $k$ cycles satisfies the same recurrence and has the same initial values. If you get stuck, there’s a proof here.

Brian M. Scott
  • 616,228