The Stirling Numbers of the First Kind
In Chapter 3, we learnt that the number of ways to choose m objects from n distinct objects, where m ≤ n, and arrange them in a row is given by
As shown in Chapter 13 (see (13.8)), the expression (17.1) can also be interpreted as the number of 1-1 mappings from the set {1,2,…, m} to the set {1,2,…, n}.
As (17.1) will be mentioned very often in what follows, for simplicity, we may denote it by [n]m; that is,
Let us replace “n” in (17.2) by a real variable “x”. Then we have
which can be regarded as a polynomial in x of degree m. For instance,
Just like what we did above, we shall express the polynomial [x]m in increasing order of powers of x. The following question arises naturally: what can be said about the coefficient of xk in the expansion of [x]m, where 0 ≤ k ≤ m? It is clear from (17.3) that this coefficient depends on both m and k; and so let us, at this moment, denote it by s(m, k). Thus, we have:
By comparing with the expansions of [x]1, [x]2,…, [x]5 as shown above, we can easily obtain the values of s(m,k), where 0 ≤ k ≤ m ≤ 5. These are recorded in Table 17.1 (note that we define s(0, 0) to be 1).
It follows from (17.3) and (17.4) that s(m, 0) = 0 and s(m,m) = 1 for all m ≥ 1. Also, the sequence of numbers s(m, 1),s(m, 2),…, s(m, m) alternate in sign with s(m, 1) positive when and only when m is odd. It can be shown (see Problem 17.2) that for m ≥ 2, we have
(i) 
and
(ii) 
How are we going to evaluate s(m, k) in general? We see from the above that when k = 0, 1 or k = m – 1, m, the values of s(m, k) can be computed by simple formulas. For general k, there is a “recursive” way to evaluate s(m, k) that we shall now present.
By comparing [x]m and [x]m–1 by (17.3), we have
Table 17.1 The values of s(m, k), 0 ≤ k ≤ m ≤ 5.
Thus, by (17.4),
Hence, by equating the coefficients of xk on both sides of the above equality, we have
and, in general,
As was pointed out before, the value of s(m, k) depends on two parameters: m and k. In (17.5), we observe that the value of s(m, k) is expressed in terms of the values of s(m – 1,k – 1) and s(m – 1,k), where the values of the parameters do not exceed those in s(m,k). Thus, we can evaluate s(m, k) if we know the values of s(p, q) where p ≤ m and q ≤ k. For instance, when (m, k) = (6, 3), by (17.5)
Checking from Table 17.1, we have s(5,2) = –50 and s(5,3) = 35. Thus
In Chapter 16, we introduced the notion of “recurrence relation” with examples such as an = an–1 + an–2 and an = 2an–1 +1, where the value of an is expressed in terms of the values of ar’s where r < n. The relation (17.5) is also regarded as a recurrence relation, but it is more complicated as it involves two parameters.
The numbers s(m,k) are called the Stirling numbers of the first kind in honour of the Scottish mathematician James Stirling (1692–1770). Inspired by the theory on plane curves due to Isaac Newton, Stirling worked on its extensions and published in 1730 his most influential work Methodus Differentialis, where the numbers s(m, k) were introduced.
Combinatorial Interpretation of the Stirling
Number s(m, k)
The Stirling number s(m, k) was defined as the coefficient of xk in the expansion of [x]m, which is purely algebraic in nature. Does it have any combinatorial interpretation? The answer is yes, and we shall now present one.
Let us recall the notion of “circular arrangement” from Chapter 7: two arrangements of n distinct objects in a circle are considered different if and only if there is at least one object whose neighbour on the right is different in the two arrangements. Recall also the following result:
Let us proceed further to study a variation of circular arrangements. Suppose now there are, say, 5 distinct objects to be arranged around, say, 2 identical circles with at least one object at each circle. In how many ways can this be done? Again, before we move on, let us agree on what we mean when we say that two arrangements are the same. We will use a definition which extends that for circular arrangements in one circle: two arrangements of n distinct objects in k identical circles are considered different if and only if there is at least one object whose neighbour on the right is different in the two arrangements.
Thus, for instance, we agree that
while 
and 
With this clarification, we are now ready to solve the problem. There are two ways to split 5 distinct objects into 2 nonempty groups; namely,
Case (i) There are 4 objects around a circle and 1 object around another circle.
In this case, there are 
ways to select 4 objects from 5 distinct ones to put them around one circle. By (17.6), there are (4 — 1)! ways to arrange the selected 4 objects around the circle. (Of course, the remaining object is on the other circle.) Thus the number of ways of arrangement is, by (MP),
Case (ii) There are 3 objects around a circle and 2 objects around another circle.
In this case, there are 
ways to select 3 objects from 5 distinct ones to put them around one circle. By (17.6), there are (3 — 1)! ways to arrange the selected 3 objects around the circle. By (17.6) again, the remaining 2 objects can be arranged around the other circle in (2 — 1)! ways. Thus the number of ways of arrangement is, by (MP),
Finally, by (AP), the required number of arrangements is given by 30 + 20 = 50.
We thus conclude that the number of ways of arranging 5 distinct objects around 2 identical circles with at least one object at each circle is 50.
Note that 50 is related to a Stirling number of the first kind. Indeed, s(5,2) = –50 (m = 5 corresponds to 5 objects and k = 2 corresponds to 2 circles).
For convenience, let us denote by s*(m, k), with k ≤ m, the number of ways of arranging m distinct objects around k identical circles with at least one object at each circle. Thus, as shown above, s*(5, 2) = 50 = |s(5,2)|, where |x| denotes the absolute value of the real number x.
By comparing the answers of Problems 17.1 and 17.3, we have s*(6, 3) = 225 = |s(6, 3)|.
We define s*(0,0) = 1. Clearly, s*(m, 0) = 0 and s*(m, 1) = (m — 1)! by (17.6).
Our aim is to show that, indeed,
The result (17.5) provides us with a recurrence relation for the numbers s(m, k). In what follows, we shall establish a corresponding recurrence relation for s*(m, k).
Let us give a combinatorial argument to see why (17.7) holds. The number s*(m, k) counts the number of ways of arranging m distinct objects, say X1, X2,… ,Xm around k identical circles with at least one object at each circle. Let us fix one of the objects, say Xm. Clearly, in any such arrangement, either (i) Xm is the only object at a circle, or (ii) Xm is with others at a circle. We now count s*(m, k) by splitting our consideration into the above two cases.
Case (i) Xm is the only object at a circle.
In this case, the remaining (m — 1) objects X1, X2,…, Xm-1 are arranged around k — 1 circles with at least one object at each circle. By definition, there are s*(m — 1,k — 1) ways to do this.
Case (ii) Xm is mixed with others at a circle.
In this case, we can accomplish the task by first arranging the objects X1, X2,… ,Xm-1 around k circles with at least one object at each circle and then place Xm in one of the circles. By definition, there are s*(m — 1,k) ways to perform the first step. How many ways are there for the second step? After arranging m — 1 objects around the circles, Xm can be placed at any of the m — 1 spaces to the right of each object, and so there are m — 1 ways to do so. Thus, by (MP), there are (m — 1)s*(m — 1, k) ways in this case.
Finally, by (AP), we arrive at the result (17.7).
With the help of (17.5) and (17.7), we shall now see why 
Note that:
Also, as s(m — 1, k — 1) and s(m — 1, k) are different in sign or one of them is zero, we have
Consider (m,k) = (3,2). Observe that
When (m,k) = (4,2), we have
When (m,k) = (4,3), we have
If we proceed in this manner by following the ordering, say, (m,k) = (3,2), (4, 2), (4, 3), (5, 2), (5, 3), (5, 4), (6, 2), (6, 3), (6, 4), (6, 5), (7, 2), (7, 3), …, we shall always find that
Let us explain why (17.9) holds for all (m,k), where 1 ≤ k ≤ m, with the help of Figure 17.1. We have already verified that (17.8) holds when k = 1 and k = m. This is indicated in Figure 17.1 at the entries (m, k) enclosed by rectangles. The key tools in the process are the recurrence relations (17.5) and (17.7) (and, of course, (17.8) also). We now start with (m, k) = (3,2). Using the verified results for (2,1) and (2, 2), and applying (17.5) and (17.7), we show that (17.9) holds for (3, 2). This fact is indicated in Figure 17.1 by the two arrows pointing to entry (3, 2) from entries (2, 1) and (2, 2). We then proceed to (m, k) = (4, 2). Using the verified results for (3, 1) and (3, 2), and applying (17.5) and (17.7), we show that (17.9) holds for (4, 2). Again, this is indicated in Figure 17.1 by the two arrows pointing to entry (4, 2) from entries (3, 1) and (3, 2). Thus, following the ordering of (m, k) as fixed above and the arrows pointing to the corresponding entries in Figure 17.1, we see that the result (17.9) is indeed valid for each (m, k) with 1 ≤ k ≤ m.
Figure 17.1
Following this, the reader may want to attempt a rigorous proof of (17.9) by mathematical induction (see Problem 17.4) using the inductive steps suggested by Figure 17.1.
Finally, we shall give a direct combinatorial argument for particular values of (17.9).
Let us consider the case when m = 8 and k = 3. By the algebraic definition, the Stirling number s(8, 3) is the coefficient of x3 in the expansion of x(x — 1)(x — 2) … (x — 7). Then |s(8,3)| is the coefficient of x3 in the expansion of x(x + 1)(x + 2) … (x + 7). The combinatorial definition says that s*(8,3) counts the number of ways that elements 0, 1,2,… ,7 can be arranged around 3 identical circles with at least one object at each circle. We shall show that the coefficient of x3 the expansion of 
is the same as the number of ways of arranging the 8 distinct elements around 3 identical circles with at least one object at each circle.
Note that the sum of the terms with x3 in the expansion of
is given by
Each term is a product of x3 and five numbers chosen from among 1 through 7. This can be seen as taking three x’s from three factors and the “numbers” from the remaining five factors. Thus
Coefficient of x3 in the expansion of
Now, let us see how this expression 3 · 4 · 5 · 6 · 7 + 2 · 4 · 5 · 6 · 7 + 2 · 3 · 5 · 6 · 7+ … +1 · 2 · 3 · 4 · 5 counts the number of ways elements 0 through 7 can be arranged around 3 circles with at least one object at each circle.
Let us take a term, say 1 · 3 · 4 · 5 · 7. We place the “missing” elements 0, 2 and 6 on three different circles and make the rule that these “missing” elements will be the least elements of the circles. Next we place the remaining elements one at a time in increasing order. The number 1 has just one option, which is on the right of 0 (it cannot be placed on either of the other circles for then it would violate the least property of the incumbent “missing” elements 2 and 6, respectively). The element 3 then has three options: the right of 0, the right of 1 or the right of 2 on the other circle. The element 4 now has four options: the right of 0, the right of 1, the right of 2 or the right of 3. We can similarly see that element i has i options. Thus, by (MP), the number of ways of placing the eight elements 0, 1,2, … ,7 around three circles such that elements 0, 2 and 6 are the least elements in each of their circles is 1 · 3 · 4 · 5 · 7.
Every term in the expression 3 · 4 · 5 · 6 · 7 + 2 · 4 · 5 · 6 · 7 + 2 · 3 · 5 · 6 · 7 + … + 1 · 2 · 3 · 4 · 5 can be combinatorially interpreted as above and every arrangement of the eight elements 0,1,2,…, 7 around three circles with at least one object at each circle can be matched uniquely to one term in the expression. For example, the arrangement with 3, 4, 0 in clockwise order around one circle, 1, 2, 7 in clockwise order around another circle and 5, 6 around a third circle, is matched uniquely to the term with “missing” elements 0, 1, 5, i.e. the term 2 · 3 · 4 · 6 · 7. Hence, we have shown that s*(8,3) = |s(8,3)|.
The reader is invited to prove the general result using the combinatorial argument above in Problem 17.5.
Exercise
17.1 Find the values of s(6, k), where 1 ≤ k ≤ 6.
17.2 Show that for m ≥ 2,
(i) 
(ii) 
17.3 Show, from “first principles”, that the number of ways of arranging 6 distinct objects around 3 identical circles with at least one object at each circle is given by 225.
17.4 Use mathematical induction to show that
17.5 A permutation (a1,a2,…, an) of the integers 1,2,… ,n is used to distribute these n integers into indistinguishable circles as follows. Locate ai1 = 1 and arrange ai1,ai1+1,…,an in a clockwise direction around a circle. Next, locate ai2 = min{a1,a2,…,ai1-1} and arrange ai2,ai2+1,…,ai1–1 in a clockwise direction around a second circle. Continue doing this until all the integers are distributed around k tables. Use this correspondence to show that
