# 1.8: Stirling numbers

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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: The Stirling number of the second kind

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\).

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: Stirling number of the first kind

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}\).

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.

Theorem 1.8.3

\(\sone{n}{k}=\sone{n-1}{k-1} + (n-1)\cdot\sone{n-1}{k}\), \(k\ge 1\), \(n\ge1\).

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.

$\square$

Corollary 1.8.4 \(s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k)\).

The Stirling numbers satisfy two remarkable identities. First a definition:

Definition: The Kronecker delta

The *Kronecker delta* \(\delta_{n,k}\) is 1 if \(n=k\) and 0 otherwise.

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\).

$\square$

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