3.2: Partitions and Stirling Numbers
( \newcommand{\kernel}{\mathrm{null}\,}\)
We have seen how the number of partitions of a set of k objects into n blocks corresponds to the distribution of k distinct objects to n identical recipients. While there is a formula that we shall eventually learn for this number, it requires more machinery than we now have available. However, there is a good method for computing this number that is similar to Pascal’s equation. Now that we have studied recurrences in one variable, we will point out that Pascal’s equation is in fact a recurrence in two variables; that is, it lets us compute (nk) in terms of values of (mi) in which either m<n or i<k or both. It was the fact that we had such a recurrence and knew (n0) and (nn) that let us create Pascal’s triangle.
3.2.1: Stirling Numbers of the Second Kind
We use the notation S(k,n) to stand for the number of partitions of a k element set with n blocks. For historical reasons, S(k,n) is called a Stirling Number of the second kind.
→∙ Exercise 134
In a partition of the set [k], the number k is either in a block by itself, or it is not. How does the number of partitions of [k] with n parts in which k is in a block with other elements of [k] compare to the number of partitions of [k−1] into n blocks? Find a two-variable recurrence for S(k,n), valid for k and n larger than one. (Hint).
Exercise 135
What is S(k,1)? What is S(k,k)? Create a table of values of S(k,n) for k between 1 and 5 and n between 1 and k. This table is sometimes called Stirling’s Triangle (of the second kind). How would you define S(k,0) and S(0,n)? (Note that the previous question includes S(0,0).) How would you define S(k,n) for n>k? Now for what values of k and n is your two variable recurrence valid?
Exercise 136
Extend Stirling’s triangle enough to allow you to answer the following question and answer it. (Don’t fill in the rows all the way; the work becomes quite tedious if you do. Only fill in what you need to answer this question.) A caterer is preparing three bag lunches for hikers. The caterer has nine different sandwiches. In how many ways can these nine sandwiches be distributed into three identical lunch bags so that each bag gets at least one?
Exercise 137
The question in Problem 136 naturally suggests a more realistic question; in how many ways may the caterer distribute the nine sandwiches into three identical bags so that each bag gets exactly three? Answer this question. (Hint).
⋅ Exercise 138
What is S(k,k−1)? (Hint).
∙ Exercise 139
In how many ways can we partition k (distinct) items into n blocks so that we have ki blocks of size i for each i? (Notice that ∑ki−1ki=n and ∑ki−1iki=k.) The sequence k1,k2,...,kn is called the type vector of the partition. (Hint).
+ Exercise 140
Describe how to compute S(n,k) in terms of quantities given by the formula you found in Problem 139.
→ Exercise 141
Find a recurrence for the Lah numbers L(k,n) similar to the one in Problem 134. (Hint).
⋅ Exercise 142
(Relevant in Appendix C.) The total number of partitions of a k-element set is denoted by B(k) and is called the k-th Bell number. Thus B(1)=1 and B(2)=2.
- Show, by explicitly exhibiting the partitions, that B(3)=5.
- Find a recurrence that expresses B(k) in terms of B(n) for n<k and prove your formula correct in as many ways as you can. (Hint).
- Find B(k) for k=4,5,6.
3.2.2: Stirling Numbers and Onto Functions
∘ Exercise 143
Given a function f from a k-element set K to an n-element set, we can define a partition of K by putting x and y in the same block of the partition if and only if f(x)=f(y). How many blocks does the partition have if f is onto? How is the number of functions from a k-element set onto an n-element set related to a Stirling number? Be as precise in your answer as you can. (Hint).
→ Exercise 144
How many labeled trees on n vertices have exactly 3 vertices of degree one? Note that this problem has appeared before in Chapter 2. (Hint).
∙ Exercise 145
Each function from a k-element set K to an n-element set N is a function from K onto some subset of N. If J is a subset of N of size j, you know how to compute the number of functions that map onto J in terms of Stirling numbers. Suppose you add the number of functions mapping onto J over all possible subsets J of N. What simple value should this sum equal? Write the equation this gives you. (Hint).
∘ Exercise 146
In how many ways can the sandwiches of Problem 136 be placed into three distinct bags so that each bag gets at least one?
∘ Exercise 147
In how many ways can the sandwiches of Problem 137 be placed into distinct bags so that each bag gets exactly three?
∙ Exercise 148
distinct labels (numbered 1 through n) so that label i is used ji times? (If we think of the labels as y1,y2,...,yn, then we can rephrase this question as follows. How many functions are there from a k-element set K to a set N={y1,y2,...,yn} so that each yi is the image of ji elements of K?) This number is called a multinomial coefficient and denoted by (kj1,j2,...,jn). (Hint).
Exercise 149
Explain how to compute the number of functions from a k-element set K to an n-element set N by using multinomial coefficients. (Hint).
Exercise 150
Explain how to compute the number of functions from a k-element set K onto an n-element set N by using multinomial coefficients. (Hint).
∙ Exercise 151
What do multinomial coefficients have to do with expanding the kth power of a multinomial x1+x2+···+xn? This result is called the multinomial theorem. (Hint).
3.2.3: Stirling Numbers and Bases for Polynomials
⋅ Exercise 152
- Find a way to express nk in terms of kj_ for appropriate values j. You may use Stirling numbers if they help you. (Hint).
- Notice that xj_ makes sense for a numerical variable x (that could range over the rational numbers, the real numbers, or even the complex numbers instead of only the nonnegative integers, as we are implicitly assuming n does), just as xj does. Find a way to express the power xk in terms of the polynomials xj_ for appropriate values of j and explain why your formula is correct. (Hint).
You showed in Problem 152b how to get each power of x in terms of the falling factorial powers xj_. Therefore every polynomial in x is expressible in terms of a sum of numerical multiples of falling factorial powers. Using the language of linear algebra, we say that the ordinary powers of x and the falling factorial powers of x each form a basis for the “space” of polynomials, and that the numbers S(k,n) are “change of basis coefficients.” If you are not familiar with linear algebra, a basis for the space of polynomials is a set of polynomials such that each polynomial, whether in that set or not, can be expressed in one and only one way as a sum of numerical multiples of polynomials in the set.
∘ Exercise 153
Show that every power of x+1 is expressible as a sum of numerical multiples of powers of x. Now show that every power of x (and thus every polynomial in x) is a sum of numerical multiples (some of which could be negative) of powers of x+1. This means that the powers of x+1 are a basis for the space of polynomials as well. Describe the change of basis coefficients that we use to express the binomial powers (x+1)n in terms of the ordinary xj explicitly. Find the change of basis coefficients we use to express the ordinary powers xn in terms of the binomial powers (x+1)k. (Hint).
→⋅ Exercise 154
By multiplication, we can see that every falling factorial polynomial can be expressed as a sum of numerical multiples of powers of x. In symbols, this means that there are numbers s(k,n) (notice that this s is lower case, not upper case) such that we may write xk_=∑kn=0s(k,n)xn. These numbers s(k,n) are called Stirling Numbers of the first kind. By thinking algebraically about what the formula
xk_=xk−1_(x−k+1)
means, we can find a recurrence for Stirling numbers of the first kind that gives us another triangular array of numbers called Stirling’s triangle of the first kind. Explain why Equation ??? is true and use it to derive a recurrence for s(k,n) in terms of s(k−1,n−1) and s(k−1,n). (Hint).
Exercise 155
Write down the rows of Stirling’s triangle of the first kind for k=0 to 6.
By definition, the Stirling numbers of the first kind are also change of basis coefficients. The Stirling numbers of the first and second kind are change of basis coefficients from the falling factorial powers of x to the ordinary factorial powers, and vice versa.
→ Exercise 156
Explain why every rising factorial polynomial xˉk can be expressed as a sum of multiples of the falling factorial polynomials xn_. Let b(k,n) stand for the change of basis coefficients that allow us to express xˉk in terms of the falling factorial polynomials xn_; that is, define b(k,n) by the equations
xˉk=k∑n=0b(k,n)xn_.
- Find a recurrence for b(k,n). (Hint).
- Find a formula for b(k,n) and prove the correctness of what you say in as many ways as you can. (Hint).
- Is b(k,n) the same as any of the other families of numbers (binomial coefficients, Bell numbers, Stirling numbers, Lah numbers, etc.) we have studied?
- Say as much as you can (but say it precisely) about the change of basis coefficients for expressing xk_ in terms of xˉn. (Hint).