Stirling Numbers of first kind $s(n,k)$

Question

Stirling Numbers, $s(n,k)$ are defined as the permutation of $[n]$={$1,2,...,n$} of having $k$ cycles,

why is it/how can you prove $s(n,1)=(n-1)!$ and $s(n,n)=1$

and

$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$

I don't really understand how to do this at all?

Answer 1

To show $s(n,1) = (n-1)!$ we know that all $n$ numbers are in one cycle. So we can select the first element and place it into the cycle in $n$ ways, then to the right of it we can place the next number in $n-1$ ways, then to the right of that the next number in $(n-2)$ ways etc. So placing all numbers there are $n!$ ways. But for each such permuation, we could have started it at any of the $n$ positions, and so we divide by $n$ to get $(n-1)!$

$s(n,n) = 1$ because in this case each element is in its own cycle (i.e.) it is the identity permutation.

For $s(n,k), $ consider the element $n$. There are two possibilites, $n$ is in its own cycle, or it is not. The number of possibilites when $n$ is in its own cycle is then $s(n-1, k-1)$ (because that is what we can do with the remaining $n-1$ elements). If it is not in its own cycle, then if we remove $n$ from its cycle there are still $k$ cycles with the remaining $n-1$ elements. We can then place the element $n$ into the permuation in $n-1$ positions, leading to the term $(n-1)s(n-1,k)$.