In exercise 4 in section 1.4, we saw the Stirling numbers of the second kind. Not surprisingly, there are Stirling numbers of the first kind. Recall that Stirling numbers of the second kind are defined as follows:
Definition 1.8.1 The Stirling number of the second kind, $S(n,k)$ or $\stwo{n}{k}$, is the number of partitions of $[n]=\{1,2,\ldots,n\}$ into exactly $k$ parts, $1\le k\le n$. $\square$
Before we define the Stirling numbers of the first kind, we need to revisit permutations. As we mentioned in section 1.7, we may think of a permutation of $[n]$ either as a reordering of $[n]$ or as a bijection $\sigma\colon [n]\to[n]$. There are different ways to write permutations when thought of as functions. Two typical and useful ways are as a table, and in cycle form. Consider this permutation $\sigma\colon [5]\to[5]$: $\sigma(1)=3$, $\sigma(2)=4$, $\sigma(3)=5$, $\sigma(4)=2$, $\sigma(5)=1$. In table form, we write this as $\left(1\; 2\; 3\; 4\; 5\atop 3\; 4\; 5\; 2\; 1\right)$, which is somewhat more compact, as we don't write "$\sigma$'' five times. In cycle form, we write this same permutation as $(1,3,5)(2,4)$. Here $(1,3,5)$ indicates that $\sigma(1)=3$, $\sigma(3)=5$, and $\sigma(5)=1$, whiile $(2,4)$ indicates $\sigma(2)=4$ and $\sigma(4)=2$. This permutation has two cycles, a 3-cycle and a 2-cycle. Note that $(1,3,5)$, $(3,5,1)$, and $(5,1,3)$ all mean the same thing. We allow 1-cycles to count as cycles, though sometimes we don't write them explicitly. In some cases, however, it is valuable to write them to force us to remember that they are there. Consider this permutation: $\left(1\; 2\; 3\; 4\; 5\; 6\atop 3\; 4\; 5\; 2\; 1\; 6\right)$. If we write this in cycle form as $(1,3,5)(2,4)$, which is correct, there is no indication that the underlying set is really $[6]$. Writing $(1,3,5)(2,4)(6)$ makes this clear. We say that this permutation has 3 cycles, even though one of them is a trivial 1-cycle. Now we're ready for the next definition.
Definition 1.8.2 The Stirling number of the first kind, $s(n,k)$, is $(-1)^{n-k}$ times the number of permutations of $[n]$ with exactly $k$ cycles. The corresponding unsigned Stirling number of the first kind, the number of permutations of $[n]$ with exactly $k$ cycles, is $|s(n,k)|$, sometimes written $\sone{n}{k}$. Using this notation, $s(n,k)=(-1)^{n-k}\sone{n}{k}$. $\square$
Note that the use of $\sone{n}{k}$ conflicts with the use of the same notation in section 1.7; there should be no confusion, as we won't be discussing the two ideas together.
Some values of $\sone{n}{k}$ are easy to see; if $n\ge 1$, then $$\matrix{ \rlap{\left[\matrix{n\cr n\cr}\right]=1}\phantom{\left[\matrix{n\cr 1\cr}\right]=(n-1)!} &\quad&\left[\matrix{n\cr k\cr}\right]=0, \;\mbox{ if $k>n$}\cr \left[\matrix{n\cr 1\cr}\right]=(n-1)!&\quad& \rlap{\left[\matrix{n\cr 0\cr}\right]=0}\phantom{\left[\matrix{n\cr k\cr}\right]=0, \;\mbox{ if $k>n$}}\cr }$$ It is sometimes convenient to say that $\sone{0}{0}=1$. These numbers thus form a triangle in the obvious way, just as the Stirling numbers of the first kind do. Here are lines 1–5 of the triangle: $$\matrix{ 1\cr 0&1\cr 0&1&1\cr 0&2&3&1\cr 0&6&11&6&1\cr 0&24&50&35&10&1\cr }$$ The first column is not particularly interesting, so often it is eliminated.
In exercise 4 in section 1.4, we saw that $$\eqalignno{ \stwo{n}{k}&=\stwo{n-1}{k-1}+k\cdot\stwo{n-1}{k}. &(1.8.1)\cr }$$ The unsigned Stirling numbers of the first kind satisfy a similar recurrence.
Proof. The proof is by induction on $n$; the table above shows that it is true for the first few lines. We split the permutations of $[n]$ with $k$ cycles into two types: those in which $(n)$ is a 1-cycle, and the rest. If $(n)$ is a 1-cycle, then the remaining cycles form a permutation of $[n-1]$ with $k-1$ cycles, so there are $\sone{n-1}{k-1}$ of these. Otherwise, $n$ occurs in a cycle of length at least 2, and removing $n$ leaves a permutation of $[n-1]$ with $k$ cycles. Given a permutation $\sigma$ of $[n-1]$ with $k$ cycles, $n$ can be added to any cycle in any position to form a permutation of $[n]$ in which $(n)$ is not a 1-cycle. Suppose the lengths of the cycles in $\sigma$ are $l_1,l_2,\ldots,l_k$. In cycle number $i$, $n$ may be added after any of the $l_i$ elements in the cycle. Thus, the total number of places that $n$ can be added is $l_1+l_2+\cdots+l_k=n-1$, so there are $(n-1)\cdot\sone{n-1}{k}$ permutations of $[n]$ in which $(n)$ is not a 1-cycle. Now the total number of permutations of $[n]$ with $k$ cycles is $\sone{n-1}{k-1}+ (n-1)\cdot\sone{n-1}{k}$, as desired. $\qed$
The Stirling numbers satisfy two remarkable identities. First a definition:
Definition 1.8.5 The Kronecker delta $\delta_{n,k}$ is 1 if $n=k$ and 0 otherwise. $\square$
Theorem 1.8.6 For $n\ge 0$ and $k\ge 0$, $$\eqalign{ \sum_{j=0}^n s(n,j)S(j,k) &= \sum_{j=0}^n (-1)^{n-j}\sone{n}{j}\stwo{j}{k} =\delta_{n,k}\cr \sum_{j=0}^n S(n,j)s(j,k) &= \sum_{j=0}^n (-1)^{j-k}\stwo{n}{j}\sone{j}{k} = \delta_{n,k}\cr }$$
Proof. We prove the first version, by induction on $n$. The first few values of $n$ are easily checked; assume $n>1$. Now note that $\sone{n}{0}=0$, so we may start the sum index $j$ at 1.
When $k>n$, $\stwo{j}{k}=0$, for $1\le j\le n$, and so the sum is 0. When $k=n$, the only non-zero term occurs when $j=n$, and is $(-1)^0\sone{n}{n}\stwo{n}{n}=1$, so the sum is 1. Now suppose $k< n$. When $k=0$, $\stwo{j}{k}=0$ for $j>0$, so the sum is 0, and we assume now that $k>0$.
We begin by applying the recurrence relations: $$\eqalign{ \sum_{j=1}^n &(-1)^{n-j}\sone{n}{j}\stwo{j}{k}= \sum_{j=1}^n (-1)^{n-j}\left(\sone{n-1}{j-1}+(n-1)\sone{n-1}{j}\right) \stwo{j}{k}\cr &=\sum_{j=1}^n (-1)^{n-j}\sone{n-1}{j-1}\stwo{j}{k}+ \sum_{j=1}^n (-1)^{n-j}(n-1)\sone{n-1}{j}\stwo{j}{k}\cr &=\sum_{j=1}^n (-1)^{n-j}\sone{n-1}{j-1}\left(\stwo{j-1}{k-1}+ k\stwo{j-1}{k}\right) + \sum_{j=1}^n (-1)^{n-j}(n-1)\sone{n-1}{j}\stwo{j}{k}\cr &=\sum_{j=1}^n (-1)^{n-j}\sone{n-1}{j-1}\stwo{j-1}{k-1}+ \sum_{j=1}^n (-1)^{n-j}\sone{n-1}{j-1}k\stwo{j-1}{k}\cr &\qquad+ \sum_{j=1}^n (-1)^{n-j}(n-1)\sone{n-1}{j}\stwo{j}{k}.\cr }$$
Consider the first sum in the last expression: $$ \eqalign{ \sum_{j=1}^n (-1)^{n-j}\sone{n-1}{j-1}\stwo{j-1}{k-1} &=\sum_{j=2}^n (-1)^{n-j}\sone{n-1}{j-1}\stwo{j-1}{k-1}\cr &=\sum_{j=1}^{n-1} (-1)^{n-j-1}\sone{n-1}{j}\stwo{j}{k-1}\cr &=\delta_{n-1,k-1}=0, }$$ since $k-1< n-1$ (or trivially, if $k=1$). Thus, we are left with just two sums. $$\eqalign{ \sum_{j=1}^n &(-1)^{n-j}\sone{n-1}{j-1}k\stwo{j-1}{k} +\sum_{j=1}^n (-1)^{n-j}(n-1)\sone{n-1}{j}\stwo{j}{k}\cr &=k\sum_{j=1}^{n-1} (-1)^{n-j-1}\sone{n-1}{j}\stwo{j}{k} -(n-1)\sum_{j=1}^{n-1} (-1)^{n-j-1}\sone{n-1}{j}\stwo{j}{k}\cr &=k\delta_{n-1,k}-(n-1)\delta_{n-1,k}. }$$ Now if $k=n-1$, this is $(n-1)\delta_{n-1,n-1}-(n-1)\delta_{n-1,n-1}=0$, while if $k< n-1$ it is $k\delta_{n-1,k}-(n-1)\delta_{n-1,k}=k\cdot 0-(n-1)\cdot 0=0$. $\qed$
If we interpret the triangles containing the $s(n,k)$ and $S(n,k)$ as matrices, either $m\times m$, by taking the first $m$ rows and columns, or even the infinite matrices containing the entire triangles, the sums of the theorem correspond to computing the matrix product in both orders. The theorem then says that this product consists of ones on the diagonal and zeros elsewhere, so these matrices are inverses. Here is a small example: $$ \pmatrix{ 1& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0\cr 0& -1& 1& 0& 0& 0\cr 0& 2& -3& 1& 0& 0\cr 0& -6& 11& -6& 1& 0\cr 0& 24& -50& 35& -10& 1\cr } \pmatrix{ 1& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0\cr 0& 1& 1& 0& 0& 0\cr 0& 1& 3& 1& 0& 0\cr 0& 1& 7& 6& 1& 0\cr 0& 1& 15& 25& 10& 1\cr } = \pmatrix{ 1& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0\cr 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 1& 0& 0\cr 0& 0& 0& 0& 1& 0\cr 0& 0& 0& 0& 0& 1\cr } $$
Exercises 1.8
Ex 1.8.1 Find a simple expression for $\sone{n}{n-1}$.
Ex 1.8.2 Find a simple expression for $\sone{n}{1}$.
Ex 1.8.3 What is $\sum_{k=0}^n \sone{n}{k}$?
Ex 1.8.4 What is $\sum_{k=0}^n s(n,k)$?
Ex 1.8.5 Show that $x^{\underline n}=\prod_{k=0}^{n-1}(x-k)=\sum_{i=0}^n s(n,i)x^i$, $n\ge 1$; $x^{\underline n}$ is called a falling factorial. Find a similar identity for $x^{\overline n}=\prod_{k=0}^{n-1}(x+k)$; $x^{\overline n}$ is a rising factorial.
Ex 1.8.6 Show that $\ds \sum_{k=0}^n \stwo{n}{k} x^{\underline k} = x^n$, $n\ge 1$; $x^{\underline k}$ is defined in the previous exercise. The previous exercise shows how to express the falling factorial in terms of powers of $x$; this exercise shows how to express the powers of $x$ in terms of falling factorials.
Ex 1.8.7 Prove: $\ds S(n,k)=\sum_{i=k-1}^{n-1} {n-1\choose i}S(i,k-1)$.
Ex 1.8.8 Prove: $\ds \sone{n}{k}=\sum_{i=k-1}^{n-1} (n-i-1)! {n-1\choose i}\sone{i}{k-1}$.
Ex 1.8.9 Use the previous exercise to prove $\ds s(n,k)=\sum_{i=k-1}^{n-1} (-1)^{n-i-1}(n-i-1)! {n-1\choose i}s(i,k-1)$.
Ex 1.8.10 We have defined $\sone{n}{k}$ and $\stwo{n}{k}$ for $n,k\ge 0$. We want to extend the definitions to all integers. Without some extra stipulations, there are many ways to do this. Let us suppose that for $n\not=0$ we want $\sone{n}{0}=\sone{0}{n}=\stwo{n}{0}=\stwo{0}{n}=0$, and we want the recurrence relations of equation 1.8.1 and in theorem 1.8.3 to be true. Show that under these conditions there is a unique way to extend the definitions to all integers, and that when this is done, $\stwo{n}{k}=\sone{-k}{-n}$ for all integers $n$ and $k$. Thus, the extended table of values for either $\sone{n}{k}$ or $\stwo{n}{k}$ will contain all the values of both $\sone{n}{k}$ and $\stwo{n}{k}$.
Ex 1.8.11 Under the assumptions that $s(n,0)=s(0,n)=0$ for $n\not=0$, and $s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k)$, extend the table for $s(n,k)$ to all integers, and find a connection to $S(n,k)$ similar to that in the previous problem.
Ex 1.8.12 Prove corollary 1.8.4.
Ex 1.8.13 Prove the remaining part of theorem 1.8.6.