Proof Stirling Numbers of First Kind

Question

The following three equations of the Stirling numbers (kind 1) should be proved:

1) $S_{n+1,k} = s_{n,k-1} + ns_{n,k}$

2) $s_{n,1} = (n-1)!$

3) $s_{n,n-1} = \binom{n}{2}$

Can someone please help me?

Answer 1

I'll show you the first and third.

Let $\pi$ be an arbitrary permutation of the natural numbers from $1$ through $n+1$ that has $k$ cycles. Consider where $n+1$ is in that permutation. There are two possibilities:

• $n+1$ is fixed by $\pi$; i.e. it is alone in its own cycle. The remaining $n$ elements form $k-1$ cycles, so there are $s_{n,k-1}$ of these.

• $n+1$ is not fixed by $\pi$. These can be "built" by taking one of the $s_{n,k}$ permutations of the natural numbers from $1$ through $n$ and "inserting" $n+1$ after any of the $n$ elements in its cycle. Therefore, there are $ns_{n,k}$ permutations where $n+1$ is not fixed.

Since those two cases are exhaustive, we conclude the recurrence relation $s_{n+1,k}=s_{n,k-1}+ns_{n,k}$.

---

$s_{n,n-1}$ represents the number of permutations of $n$ elements into $n-1$ cycles. This clearly can only be achieved by a single transposition. We designate these by choosing the two elements that are to be swapped, so this can be done in $n\choose 2$ ways.