3.2: Partitions and Stirling Numbers

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 \(\binom{n}{k}\) in terms of values of \(\binom{m}{i}\) in which either \(m < n\) or \(i < k\) or both. It was the fact that we had such a recurrence and knew \(\binom{n}{0}\) and \(\binom{n}{n}\) 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.

\(\rightarrow \; \bullet\) 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).

\(\cdot\) Exercise \(138\)

What is \(S(k, k − 1)\)? (Hint).

\(\bullet\) Exercise \(139\)

In how many ways can we partition \(k\) (distinct) items into \(n\) blocks so that we have \(k_i\) blocks of size \(i\) for each \(i\)? (Notice that \(\sum^{k}_{i-1}k_{i} = n\) and \(\sum^{k}_{i-1}ik_{i} = k\).) The sequence \(k_{1}, k_{2}, . . . , k_{n}\) 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.

\(\rightarrow\) Exercise \(141\)

Find a recurrence for the Lah numbers \(L(k, n)\) similar to the one in Problem 134. (Hint).

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

1. Show, by explicitly exhibiting the partitions, that \(B(3) = 5\).
2. 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).
3. Find \(B(k)\) for \(k = 4, 5, 6\).

3.2.2: Stirling Numbers and Onto Functions

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

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

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

\(\circ\) 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?

\(\circ\) Exercise \(147\)

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

\(\bullet\) Exercise \(148\)

distinct labels (numbered \(1\) through \(n\)) so that label \(i\) is used \(j_i\) times? (If we think of the labels as \(y_{1}, y_{2}, . . . , y_{n}\), then we can rephrase this question as follows. How many functions are there from a \(k\)-element set \(K\) to a set \(N = \{y_{1}, y_{2}, . . . ,y_{n}\}\) so that each \(y_{i}\) is the image of \(j_{i}\) elements of \(K\)?) This number is called a multinomial coefficient and denoted by \(\binom{k}{j_{1},j_{2}, . . . ,j_{n}}\). (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).

\(\bullet\) Exercise \(151\)

What do multinomial coefficients have to do with expanding the \(k^{\text{th}}\) power of a multinomial \(x_{1} + x_{2} + · · · + x_{n}\)? This result is called the multinomial theorem. (Hint).

3.2.3: Stirling Numbers and Bases for Polynomials

\(\cdot\) Exercise \(152\)

1. Find a way to express \(n^{k}\) in terms of \(k^{\underline{j}}\) for appropriate values \(j\). You may use Stirling numbers if they help you. (Hint).
2. Notice that \(x^{\underline{j}}\) 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 \(x^{j}\) does. Find a way to express the power \(x^{k}\) in terms of the polynomials \(x^{\underline{j}}\) 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 \(x^{\underline{j}}\). 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.

\(\circ\) 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 \(x^{j}\) explicitly. Find the change of basis coefficients we use to express the ordinary powers \(x^n\) in terms of the binomial powers \((x + 1)^k\). (Hint).

\(\rightarrow \; \cdot\) 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 \(x^{\underline{k}} = \sum^{k}_{n=0}s(k,n)x^{n}\). These numbers \(s(k, n)\) are called Stirling Numbers of the first kind. By thinking algebraically about what the formula

\[x^{\underline{k}} = x^{\underline{k-1}}(x-k+1) \label{3.2.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 \(\ref{3.2.1}\) 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.

\(\rightarrow\) Exercise \(156\)

Explain why every rising factorial polynomial \(x^{\bar{k}}\) can be expressed as a sum of multiples of the falling factorial polynomials \(x^{\underline{n}}\). Let \(b(k, n)\) stand for the change of basis coefficients that allow us to express \(x^{\bar{k}}\) in terms of the falling factorial polynomials \(x^{\underline{n}}\); that is, define \(b(k, n)\) by the equations

\[x^{\bar{k}} = \sum^{k}_{n=0}b(k,n)x^{\underline{n}}\].

1. Find a recurrence for \(b(k, n)\). (Hint).
2. Find a formula for \(b(k, n)\) and prove the correctness of what you say in as many ways as you can. (Hint).
3. 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?
4. Say as much as you can (but say it precisely) about the change of basis coefficients for expressing \(x^{\underline{k}}\) in terms of \(x^{\bar{n}}\). (Hint).