3.2: Partitions and Stirling Numbers

We have seen how the number of partitions of a set of objects into blocks corresponds to the distribution of distinct objects to 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 in terms of values of in which either or or both. It was the fact that we had such a recurrence and knew and that let us create Pascal’s triangle.

3.2.1: Stirling Numbers of the Second Kind

We use the notation to stand for the number of partitions of a element set with blocks. For historical reasons, is called a Stirling Number of the second kind.

Exercise

In a partition of the set [], the number is either in a block by itself, or it is not. How does the number of partitions of [] with parts in which is in a block with other elements of [] compare to the number of partitions of [ ] into blocks? Find a two-variable recurrence for , valid for and larger than one. (Hint).

Exercise

What is ? What is ? Create a table of values of for between and and between and . This table is sometimes called Stirling’s Triangle (of the second kind). How would you define and ? (Note that the previous question includes .) How would you define for ? Now for what values of and is your two variable recurrence valid?

Exercise

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

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

What is ? (Hint).

Exercise

In how many ways can we partition (distinct) items into blocks so that we have blocks of size for each ? (Notice that and .) The sequence is called the type vector of the partition. (Hint).

Exercise

Describe how to compute in terms of quantities given by the formula you found in Problem 139.

Exercise

Find a recurrence for the Lah numbers similar to the one in Problem 134. (Hint).

Exercise

(Relevant in Appendix C.) The total number of partitions of a -element set is denoted by and is called the -th Bell number. Thus and .

1. Show, by explicitly exhibiting the partitions, that .
2. Find a recurrence that expresses in terms of for and prove your formula correct in as many ways as you can. (Hint).
3. Find for .

3.2.2: Stirling Numbers and Onto Functions

Exercise

Given a function from a -element set to an -element set, we can define a partition of by putting and in the same block of the partition if and only if . How many blocks does the partition have if is onto? How is the number of functions from a -element set onto an -element set related to a Stirling number? Be as precise in your answer as you can. (Hint).

Exercise

How many labeled trees on vertices have exactly vertices of degree one? Note that this problem has appeared before in Chapter 2. (Hint).

Exercise

Each function from a -element set to an -element set is a function from onto some subset of . If is a subset of of size , you know how to compute the number of functions that map onto in terms of Stirling numbers. Suppose you add the number of functions mapping onto over all possible subsets of . What simple value should this sum equal? Write the equation this gives you. (Hint).

Exercise

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

In how many ways can the sandwiches of Problem 137 be placed into distinct bags so that each bag gets exactly three?

Exercise

distinct labels (numbered through ) so that label is used times? (If we think of the labels as , then we can rephrase this question as follows. How many functions are there from a -element set to a set so that each is the image of elements of ?) This number is called a multinomial coefficient and denoted by . (Hint).

Exercise

Explain how to compute the number of functions from a -element set to an -element set by using multinomial coefficients. (Hint).

Exercise

Explain how to compute the number of functions from a -element set onto an -element set by using multinomial coefficients. (Hint).

Exercise

What do multinomial coefficients have to do with expanding the power of a multinomial ? This result is called the multinomial theorem. (Hint).

3.2.3: Stirling Numbers and Bases for Polynomials

Exercise

1. Find a way to express in terms of for appropriate values . You may use Stirling numbers if they help you. (Hint).
2. Notice that makes sense for a numerical variable (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 does), just as does. Find a way to express the power in terms of the polynomials for appropriate values of and explain why your formula is correct. (Hint).

You showed in Problem 152b how to get each power of in terms of the falling factorial powers . Therefore every polynomial in 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 and the falling factorial powers of each form a basis for the “space” of polynomials, and that the numbers 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

Show that every power of is expressible as a sum of numerical multiples of powers of . Now show that every power of (and thus every polynomial in ) is a sum of numerical multiples (some of which could be negative) of powers of . This means that the powers of are a basis for the space of polynomials as well. Describe the change of basis coefficients that we use to express the binomial powers in terms of the ordinary explicitly. Find the change of basis coefficients we use to express the ordinary powers in terms of the binomial powers . (Hint).

Exercise

By multiplication, we can see that every falling factorial polynomial can be expressed as a sum of numerical multiples of powers of . In symbols, this means that there are numbers (notice that this s is lower case, not upper case) such that we may write . These numbers are called Stirling Numbers of the first kind. By thinking algebraically about what the formula

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 in terms of and . (Hint).

Exercise

Write down the rows of Stirling’s triangle of the first kind for to .

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 to the ordinary factorial powers, and vice versa.

Exercise

Explain why every rising factorial polynomial can be expressed as a sum of multiples of the falling factorial polynomials . Let stand for the change of basis coefficients that allow us to express in terms of the falling factorial polynomials ; that is, define by the equations

.

1. Find a recurrence for . (Hint).
2. Find a formula for and prove the correctness of what you say in as many ways as you can. (Hint).
3. Is the same as any of the other families of numbers (binomial coefficients, Bell numbers, Stirling numbers, Lah numbers, etc.) we have studied?
4. Say as much as you can (but say it precisely) about the change of basis coefficients for expressing in terms of . (Hint).