CTGD Partitions and Stirling Numbers

Skip to main content

\(\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section 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\lt n\) or \(i\lt 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.

Subsection 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.

Problem 134

In a partition of the set \([k]\text{,}\) 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(n,k)\text{,}\) valid for \(n\) and \(k\) larger than one.

The number of partitions of \([k]\) into \(n\) parts in which \(k\) is not in a block relates to the number of partitions of \(k-1\) into some number of blocks in a way that involves \(n\text{.}\) With this in mind, review how you proved Pascal's (recurrence) equation.

Problem 135

What is \(S(k,1)\text{?}\) What is \(S(k,k)\text{?}\) Create a table of values of \(S(k,n)\) for \(k\) between 1 and 5 and \(n\) between 1 and \(k\text{.}\) This table is sometimes called Stirling's Triangle (of the second kind) How would you define \(S(k,n)\) for the nonnegative values of \(k\) and \(n\) that are not both positive? Now for what values of \(k\) and \(n\) is your two variable recurrence valid?

Problem 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?

Problem 137

The question in Problem 136 naturally suggests a more realistic question; in how many ways may the caterer distribute the nine sandwich's into three identical bags so that each bag gets exactly three? Answer this question.

What if the question asked about six sandwiches and two distinct bags? How does having identical bags change the answer?

Problem 138

What is \(S(k,k-1)\text{?}\)

What are the possible sizes of parts?

Problem 139

In how many ways can we partition \(k\) items into \(n\) blocks so that we have \(k_i\) blocks of size \(i\) for each \(i\text{?}\) (Notice that \(\sum_{i=1}^k k_i = n\) and \(\sum_{i=1}^k ik_i = k\text{.}\)) The sequence \(k_1,k_2,\ldots,k_n\) is called the type vector of the partition.

Suppose we make a list of the \(k\) items. We take the first \(k_1\) elements to be the blocks of size 1. How many elements do we need to take to get \(k_2\) blocks of size two? Which elements does it make sense to choose for this purpose?

Problem 140

Describe how to compute \(S(k,n)\) in terms of quantities given by the formula you found in Problem 139.

Problem 141

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

To see how many broken permutations of a \(k\) element set into \(n\) parts do not have \(k\) is a part by itself, ask yourself how many broken permutations of \([7]\) result from adding 7 to the one of the two permutations in the broken permutation \(\{14, 2356\}\text{.}\)

Problem 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\text{.}\)

(a)

Show, by explicitly exhibiting the partitions, that \(B(3)=5\text{.}\)

(b)

Find a recurrence that expresses \(B(k)\) in terms of \(B(n)\) for \(n\lt k\) and prove your formula correct in as many ways as you can.

Here it is helpful to think about what happens if you delete the entire block containing \(k\) rather than thinking about whether \(k\) is in a block by itself or not.

(c)

Find \(B(k)\) for \(k=4,5,6\text{.}\)

Subsection 3.2.2 Stirling Numbers and onto functions

Problem 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)\text{.}\) 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.

You can think of a function as assigning values to the blocks of its partition. If you permute the values assigned to the blocks, do you always change the function?

Problem 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.

The Prüfer code of a labeled tree is a sequence of \(n-2\) entries that must be chose from the vertices that do not have degree 1. The sequence can be though of as a function from the set \([n-2]\) to the set of vertices that do not have degree 1. What is special about this function?

Problem 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\text{.}\) If \(J\) is a subset of \(N\) of size \(j\text{,}\) 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\text{.}\) What simple value should this sum equal? Write the equation this gives you.

When you add the number of functions mapping onto \(J\) over all possible subsets \(J\) of \(N\text{,}\) what is the set of functions whose size you are computing?

Problem 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?

Problem 147

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

Problem 148

In how many ways may we label the elements of a \(k\)-element set with \(n\) 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, \ldots, y_n\text{,}\) 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,\ldots y_n\}\) so that \(y_i\) is the image of \(j_i\) elements of \(K\text{?}\)) This number is called a multinomial coefficient and denoted by

\begin{equation*} \binom{k}{j_1,j_2,\ldots, j_n}. \end{equation*}

What if the \(j_i\)'s don't add to \(k\text{?}\)

Think about listing the elements of the \(k\)-element set and labeling the first \(j_1\) elements with label number 1.

Problem 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.

The sum principle will help here.

Problem 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.

How are the relevant \(j_i\)'s in the multinomial coefficients you use here different from the \(j_i\)'s in the previous problem.

Problem 151

What do multinomial coefficients have to do with expanding the \(k\)th power of a multinomial \(x_1+x_2+\cdots+x_n\text{?}\) This result is called the multinomial theorem.

Think about how binomial coefficients relate to expanding a power of a binomial and note that the binomial coefficient \(\binom{n}{k}\) and the multinomial coefficient \(\binom{n}{k,n-k}\) are the same.

Subsection 3.2.3 Stirling Numbers and bases for polynomials

Problem 152

(a)

Find a way to express \(n^k\) in terms of \(k^{\underline{j}}\) for appropriate values \(j\text{.}\) You may use Stirling numbers if they help you.

We have related Stirling numbers to powers \(n^k\text{.}\) How are binomial coefficients related to falling factorial powers?

(b)

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.

In the equation \(\sum_{j=0}^n n^{\underline{j}}S(k,j) = n^k\text{,}\) we might try substituting \(x\) for \(n\text{.}\) However we don't know what \(\sum_{j=0}^x\) means when \(x\) is a variable. Is there anything other than \(n\) that makes a suitable upper limit for the sum? (Think about what you know about \(S(k,j)\text{.}\)

You showed in Problem 152 how to get each power of \(x\) in terms of the falling factorial powers \(x^{\underline{j}}\text{.}\) 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³The space of polynomials is just another name for the set of all 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.

Problem 153

Show that every power of \(x+1\) is expressible as a sum of numerical multiples of powers of \(x\text{.}\) 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\text{.}\) 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\text{.}\)

For the last question, you might try taking advantage of the fact that \(x = x + 1 - 1\text{.}\)

Problem 154

By multiplication, we can see that every falling factorial polynomial can be expressed as a sum of numerical multiples of powers of \(x\text{.}\) 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_{n=0}^k s(k,n)x^n\text{.}\) These numbers \(s(k,n)\) are called Stirling Numbers of the first kind. By thinking algebraically about what the formula

\begin{equation} x^{\underline{k}} = x^{\underline{k-1}}(x-k+1)\label{stirling1}\tag{3.3} \end{equation}

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 (3.3) 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)\text{.}\)

What does induction have to do with Equation (3.3)?

What could you assume inductively about \(x^{\underline{k-1}}\) if you were trying to prove \(x^{\underline{k}} = \sum_{n=0}^k s(k,n)x^n\text{?}\)

Problem 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.

Problem 156

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

\begin{equation*} x^{\overline{k}}=\sum_{n=0}^k b(k,n) x^{\underline{n}}. \end{equation*}

(a)

Find a recurrence for \(b(k,n)\text{.}\)

There is a solution for this problem similar to the solution to Problem 154.

(b)

Find a formula for \(b(k,n)\) and prove the correctness of what you say in as many ways as you can.

Is the recurrence you got familiar?

(c)

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?

(d)

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^{\overline{n}}\text{.}\)

Show that \((-x)^{\underline{k}} = (-1)^k x^{\overline{k}}\) and \((-x)^{\overline{k}} = (-1)^k x^{\underline{k}}\text{.}\)

The first hint lets you write an equation for \((-1)^k x^{\underline{k}}\) as a rising factorial of something else and then use what you know about expressing rising factorials in terms of falling factorials, after which you have to convert back to factorial powers of \(x\text{.}\)