The Stirling Numbers of the Second Kind
In the previous chapter, we introduced the Stirling number of the first kind s(m, k) which is defined as the coefficient of xk in the expansion of
namely,
The sequence of numbers s(m, l),s(m, 2),..., s(m, m) alternate in sign with s(m, 1) positive when and only when m is odd.
We also gave a combinatorial interpretation of s(m, k), i.e. the absolute value of s(m, k) is the number of ways of arranging m distinct objects around k identical circles with at least one object at each circle.
In this chapter, we shall introduce the other sequence of Stirling numbers, called the Stirling numbers of the second kind.
Let us begin with a simple example. Consider four distinct objects: a, b, c and d. Clearly, there is one and only one way to group them into one group, i.e. {a, b, c, d}; and there is one and only one way to divide them into four groups, i.e.
Now, (i) how many ways are there to divide them into two groups? There are 7 ways as shown below:
(ii) How many ways are there to divide them into three groups?
There are 6 ways as shown below:
Given two positive integers n and k with k ≤ n, the Stirling number of the second kind, denoted by S(n,k), is defined as the number of ways of dividing n distinct objects into k (nonempty) groups; i.e. the number of ways of partitioning an n-element set into k nonempty subsets. Thus, as shown in the above example, we have
Example 18.1 Find the number of ways to express 2730 as a product ab of two numbers a and b, where a > b > 2.
Solution Observe that 2730 = 2 · 3 · 5 · 7 · 13, and such a pair a,b of factors is obtained by dividing {2,3, 5, 7,13} into two groups (and then taking the product of all the elements within each group). Thus, the desired number of ways is given by S(5, 2) (= 15 (see Table 18.1)).
It is clear that
(i) 
(ii) 
(iii) 
We define
(iv) 
It can also be proved (see Problem 18.3) that for n ≥1,
(v) 
,
(vi) 
.
Table 18.1 The values of S(n, k), 0 ≤ k ≤ n ≤ 9.
The Number of Onto Mappings
We pointed out in Chapter 13 that the problem of counting the number of onto mappings from a finite set to another finite set is not straightforward, and we showed by an example how to tackle this problem by applying (PIE). Here, we shall point out that this counting problem is actually closely related to the problem of evaluating the S(n, k)’s.
Consider an onto mapping from {a, b, c, d} to {1, 2, 3}, say,
This onto mapping can be regarded as first dividing the 4 elements a, b, c, d into 3 groups {a, b}, {c}, {d}, and then naming the groups as “1 , “2” and “3” respectively. If we rename the groups as “2, “3” and “1” respectively, then we get another onto mapping :
Since there are 3! ways to name the 3 groups, we see that a way of dividing 4 distinct objects into 3 groups gives rise to 3! onto mappings from {a, b, c, d} to {1, 2, 3}. It thus follows that the number of onto mappings from {a, b, c, d} to {1, 2, 3} is given by 3!S(4, 3) (= 36).
In general, we have:
Using the general statement of (PIE), as shown in Chapter 14, one can show that (see Problem 14.5) the number of onto mappings from an n-element set to a k-element set is given by
Combining this with (18.1), we have:
The formula (18.2) provides us with a way to evaluate S(n, k)’s. There is another way to do so. As shown in Chapter 17, the Stirling numbers of the first kind s(m,k)’s satisfy the following recurrence relation:
For the Stirling numbers of the second kind, likewise, we have the following recurrence relation :
To see why (18.3) holds, suppose a1, a2,...,an are the n distinct objects which are divided into k groups. Consider a particular object, say a1 .
Case (1) a1 forms a group by itself.
In this case, the n – 1 objects a2,a3,...,an are then divided into k – 1 groups. By definition, there are S(n – 1,k – 1) ways of grouping.
Case (2) a1 is in a group with at least one other object.
In this case, the n – 1 objects a2, a3,...,an are then divided into k groups and by definition, there are S(n – 1,k) ways of grouping. In any such grouping, a1 has k choices to be in one of the k groups. Thus there are kS(n – 1,k) ways in this case.
The relation (18.3) now follows by (AP).
Using the initial values shown earlier as (i)-(iv) and to be worked out in Problem 18.3 as (v) and (vi), and applying (18.3), one can find out the values of other S(n,k)’s. For instance,
It is in this way that one can easily construct Table 18.1 for the values of the S(n, k)’s.
Expressing xn in terms of [x]i’s
As shown in Chapter 17, when [x]m is expressed in terms of xi,s, the Stirling numbers of the first kind are the coefficients. Suppose, conversely, we wish to express xn in terms of [x]j’ s. What can be said about the coefficients? To answer this question, let us consider the following counting problem:
Let 
= {1,2,3,..., n}. Determine a, the number of mappings from to 
.
We shall now use two different methods to count a. The first method is the “natural” one (see (13.7)):
The second method is a “stupid” one. According to the size 
of the range of a mapping 
the set of mappings from to can be partitioned into k groups Ai,i = 1,2,...,k, where Ai consists of those mappings whose ranges have exactly i elements, i.e.
What is the value of |Ai|? Well, \Ai\ counts the number of onto mappings from to an i-element subset of . There are 
number of ways to choose an i-element subset of , and the number of onto mappings from to this chosen i-element subset of is i!S(n,i) by (18.1). Thus
Comparing this result with (18.4) and noting that both count for a, we have
If we replace k by a real variable x, we then obtain:
Thus, we see that when xn is expressed in terms of [x]i’s, the Stirling numbers of the second kind are the coefficients.
For instance, when n = 4,
Exercise
18.1 Find the value of S(10, k), where k = 1,2,3,4, 5. You may want to write a simple computer program to generate the values.
18.2 Find, in terms of S(n, k), the number of ways to express 35310 as a product abc of three integers a, b, and c, where a > b > c > 2.
18.3 Show that for n > 1,
(i) 
(ii) 
18.4 Show that for n > 3,
(i) 
(ii) 
18.5 In Example 13.4, we applied (PIE) to compute the number of onto mappings from a 5-element set to a 3-element set, and found it to be “150”. Verify this result by applying (18.1) and the value for S(5, 3) in Table 18.1.