Skip to main content

Section 2.3 Partitions of Sets

Partitions are one of the core ideas in discrete mathematics. Recall that a partition of a set \(S\) is a collection of mutually disjoint subsets of \(S\) whose union is all of \(S\text{.}\) In other words, every element of \(S\) belongs to exactly one of the subsets of the partition. We call the subsets that make up the partition blocks or parts of the partition.

The integers can be naturally partitioned into evens and odds. In fact, this is just a specific case of partitioning the integers by their reminder when divided by a fixed constant; another example is that every integer has remainder 0, 1, or 2 when divided by 3.

Finite sets also have natural partitions: the set of all 4-bit strings can be partitioned according to weight:

\begin{equation*} \B^4_0 \cup \B^4_1 \cup \B^4_2 \cup \B^4_3 \cup \B^4_4 = \B^4\text{.} \end{equation*}

Using the sum principle on these disjoint sets leads directly to the identity \(\binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4} = 2^4\) (and of course the 4 can be replaced with any \(n\) here).

In fact, many of the identities we established in Section 1.2 using a combinatorial proof work precisely because we can count a set of outcomes all at once and also by counting the size of each block in a particular partition. For example, in Exercise 39 we proved that

\begin{equation*} \binom{n}{0} d_{0} + \binom{n}{1} d_{1} + \binom{n}{2} d_{2} + \ldots + \binom{n}{n} d_{n} = n! \end{equation*}

by partitioning the \(n!\) permutations of \([n]\) into blocks according to how many are fixed in position while the rest are deranged.

Even the formula for binomial coefficients, \(\binom{n}{k} = \frac{n!}{(n-k)!k!}\text{,}\) comes from partitioning the \(k\)-permutations of \([n]\) into blocks according to which subset of \([n]\) is selected (and then \(\binom{n}{k}\) is precisely the number of blocks).

In this section we will abstract this fundamental idea of partitions by one level. Instead of using particular partitions to answer counting questions, we will ask counting questions about partitions themselves. As we will see, this helps us solve yet more counting questions.

In Section 1.3 we considered some ways to distribute items to recipients. Most basic counting formulas can be thought of as counting the number of ways to distribute either distinct or identical items to distinct recipients. For example, distributing \(k\) distinct items to \(n\) distinct recipients can be done in \(n^k\) ways, if recipients can receive any number of items, or \(P(n,k)\) ways if recipients can receive at most one item. If the items are identical, the corresponding number of ways to distribute them are \(\mchoose{n}{k}\) and \(\binom{n}{k}\text{.}\)

What if the recipients are not distinct? Say we wish to distribute \(k\) books (either distinct or identical) to \(n\) identical boxes. This is a perfectly natural extension, but we will see the answer is not. First, let's get a feel for what this might look like for some small values of \(k\) and \(n\text{.}\)

Activity 191.

Suppose you have \(3\) distinct books you want to put into \(5\) identical boxes.

(a)

How many ways can you do this if each box can have at most one book?

(b)

How many ways can you do this if any box can have any number of books? You might want to consider three cases: one, two, or three boxes are used. Assume we do not care about the order in which the books are placed inside boxes.

(c)

Describe the outcomes we are counting in abstract mathematical terms. What sort of mathematical objects are we counting?

Activity 192.

Suppose you have \(3\) identical books you want to put in \(5\) identical boxes.

(a)

How many ways can you do this if each box can have at most one book?

(b)

How many ways can you do this if any box can have any number of books? Again, you should consider three cases.

(c)

What mathematical objects are we counting here?

Both of the previous two activities can be solved by counting partitions. The difference comes down to whether we partition a set of distinct objects or identical objects. It is not immediately clear how to model partitioning identical objects, and we will put this off until Section 2.4. Partitioning distinct objects simply means finding a partition of a set, the topic of the current section.

Subsection 2.3.1 Stirling Numbers of the Second Kind

We would like to count the number of ways to partition a set.

Definition 2.3.1.

Denote by \(S(k,n)\) the number of partitions of \([k]\) into exactly \(n\) subsets. We call \(S(k,n)\) a Stirling number (of the second kind).

Note that we write \(S(k,n)\) instead of \(S(n,k)\) here because we try to use \(k\) for the number of elements being distributed and \(n\) for the number of recipients. When other books use \(S(n,k)\text{,}\) they mean the number of partitions of \([n]\) into exactly \(k\) blocks. This is the same definition as we give, but with our renamed variables the formulas we get might look different.

For example, consider how to partition \([3]\) into exactly two sets:

\begin{equation*} \{1,2\}, \{3\} \qquad \qquad \{1,3\},\{2\} \qquad \qquad \{2,3\},\{1\} \end{equation*}

and that is all, so \(S(3,2) = 3\text{.}\) We do not care about the order the elements appear in each block, nor the order in which the blocks appear. Thus we see the Stirling numbers count the number of ways to distribute \(k\) distinct items to \(n\) identical recipients so that each recipient gets at least one item.

Activity 193.

Get to know the Stirling numbers by finding some. List the set of partitions and count them.

(a)

Find \(S(3,1)\text{,}\) \(S(4,1)\) and \(S(k,1)\text{.}\)

(b)

Compute \(S(2,2)\text{,}\) \(S(3,2)\) and \(S(4,2)\text{.}\) Find a formula for \(S(k,2)\) and prove it is correct.

(c)

Compute \(S(3,3)\text{,}\) and \(S(4,3)\text{.}\)

(d)

Find formulas and give proofs for \(S(k,k)\) and \(S(k,k - 1)\text{.}\)

Hint

What are the possible sizes of parts?

We can arrange the Stirling numbers into a triangle (called Stirling's second triangle). The first five rows are shown below. The entries are indexed differently than in Pascal's triangle: the top 1 represents \(S(1,1)\text{,}\) so for example, \(S(5,2) = 15\text{.}\)

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1

How were these found? Sure, we could have written out all 25 of the partitions of \([5]\) into exactly \(3\) blocks, but we didn't. Could there be some way to get 25 from the entries above it? That is, what is the recurrence relation among the Stirling numbers?

Activity 194.

Write down (if you haven't already) all 6 partitions of \([4]\) into \(3\) blocks. Break these into two cases by where 4 is: is 4 in solitary confinement (in a singleton set) or does he have a cellmate?

Now that you have some experience with listing the \(S(4,3)\) partitions of \([4]\text{,}\) the next example will help us to generalize.

Example 2.3.2.

Let's see how to take \(S(4,2) = 7\) and \(S(4,3) = 6\) to compute \(S(5,3) = 25\text{.}\)

First, here are the partitions of \([4]\) into 2 blocks (group A) or 3 blocks (group B), side by side:

Group A:

\begin{align*} \{1\}, ~ \{2,3,4\}\qquad \amp \{1,2\}, ~ \{3, 4\}\\ \{2\}, ~ \{1,3,4\}\qquad \amp \{1,3\}, ~ \{2, 4\}\\ \{3\}, ~ \{1,2,4\} \qquad \amp \{2,3\}, ~ \{1, 4\}\\ \{4\}, ~ \{1,2,3\} \qquad\amp \end{align*}

Group B:

\begin{gather*} \{3\}, ~ \{1,2\}, ~ \{4\}\\ \{2\}, ~ \{1,3\}, ~ \{4\}\\ \{2\}, ~ \{1,4\}, ~ \{3\}\\ \{1\}, ~ \{2,3\}, ~ \{4\}\\ \{1\}, ~ \{2,4\}, ~ \{3\}\\ \{1\}, ~ \{3,4\}, ~ \{2\} \end{gather*}

(Notice the \(\binom{4}{2}\) ways of listing the middle column in group B.)

Now, to list the \(S(5,3)\) partitions of \([5]\) into \(3\) parts, we need to add 5 somewhere. We can either

  1. Let 5 be a singleton block, along with any of the partitions from group A; or

  2. Let 5 join any of the blocks in any of the partitions of group B.

The second option can be accomplished in \(3\cdot 6\) ways. Thus \(S(5,3) = 7 + 3\cdot 6\text{.}\)

Activity 195.

Now generalize. In a partition of the set \([k]\text{,}\) the number \(k\) is either in a block by itself, or it is not. Find a two variable recurrence for \(S(k,n)\text{,}\) valid for \(k\) and \(n\) larger than one.

Hint

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.

Exercise 196.

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

Hint

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

Exercise 197.

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?

We have often thought of counting problems as asking about how many functions there are from a \(k\)-elements set to an \(n\)-element set. The answer to this question is \(n^k\) for all functions and \(P(n,k)\) for injective functions. What about surjective functions? There is a reason we haven't asked this question yet, but now we can at least get an expression for the number of surjections in terms of Stirling numbers.

Exercise 198.

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

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?

We do not have an explicit formula for either the number of surjections or for \(S(k,n)\) yet, but note that if we could find either, we would now have both. We will see one approach to this soon.

Exercise 199.

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.

Hint

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?

Exercise 200.

In how many ways can the sandwiches of Exercise 197 be placed into three distinct bags so that each bag gets at least one?

We will further investigate Stirling numbers in the rest of this section, but first, notice that we have not looked at the number of ways to partition a set into any number of blocks.

Definition 2.3.3.

The total number of partitions of a \(k\)-element set is denoted by \(B_k\) and is called the \(k\)-th Bell number.

Example 2.3.4.

There are five partitions of \([3]\text{:}\)

\begin{gather*} \{1\}, \{2\},\{3\}\\ \{1,2\},\{3\} \qquad \{1,3\},\{2\} \qquad \{1\}, \{2,3\}\\ \{1,2,3\} \end{gather*}

Note that \(B_3 = S(3,1)+S(3,2)+S(3,3) = 1 + 3 + 1\text{.}\)

Activity 201.
(a)

Why is \(B_k = \sum_{n=1}^{k} S(k,n)\text{,}\) but \(n^k \ne \sum_{n=1}^k S(k,n)n!\text{?}\) Why is this a meaningful question?

Hint

As to why this is a reasonable question, think of distributing \(k\) items to \(n\) recipients. All four expressions count the number of ways to do this under different restrictions.

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

Hint

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=1,2,4,5,6\text{.}\)

The Bell numbers are interesting in their own right, and we will look at them more in Subsection 2.3.4.

Subsection 2.3.2 Formulas for Stirling Numbers (of the second kind)

Here is a brief summary of what we have already discovered.

Directly from the definition, we see that \(S(k,1) = 1\) and \(S(k,k) = 1\text{.}\) From these we can compute the remaining Stirling numbers using the recursion

\begin{equation*} S(k,n) = nS(k-1,n) + S(k-1, n-1). \end{equation*}

This recursion is justified by dividing the partitions of \([k]\) into those which contain \(k\) as a singleton set (there are \(S(k-1, n-1)\) of these) and those that don't (there are \(n\) choices for where \(k\) could be for each of the \(S(k-1, n)\) partitions of \([k-1]\) into \(n\) blocks).

From this, we generated Stirling's second triangle.

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
Exercise 202.

Use the recursion to find the 6th row of the triangle.

Let's consider some ways to compute Stirling numbers directly.

While we might not have a nice closed formula for all Stirling numbers in terms of \(k\) and \(n\text{,}\) we can give closed formulas for those Stirling numbers close to the edges of the triangle. We have already considered some of these in Activity 193. To get back into the right mindset, start by reproving one of these.

Exercise 203.

Prove \(S(k, k-1) = \binom{k}{2}\text{.}\)

Hint

What are the possible sizes of parts?

The proof of the formula above suggests that looking at the sizes of the blocks might be helpful. Let's see what this might look like with an example.

Activity 204.

How many ways are there to partition \([5]\) into three sets?

(a)

How many partitions of \([5]\) have two blocks of size 1 and one block of size 3?

(b)

How many partitions of \([5]\) have one block of size 1 and two of size 2?

Hint

Careful here. The answer is NOT \(\binom{5}{2}\binom{3}{2}\text{.}\) Do you see why?

(c)

Are there any other types of partitions we need to consider? What is \(S(5,3)\text{?}\)

(d)

Generalize! Find a formula for \(S(k, k-2)\text{.}\)

(e)

A friend tells you that \(S(k,k-2) = \binom{k}{3} + 3 \binom{k}{4}\text{.}\) Prove this is correct also. If this is the formula you found for the previous part, see the hint.

Hint

If you found this formula for \(S(k,k-2)\) in part (e), then pretend your friend claims that \(S(k, k-2) = \binom{k}{3} + \frac{1}{2}\binom{k}{2}\binom{k-2}{2}\) and prove why that is correct too.

Whenever we want to partition \(k\) items in \(n\) blocks, we can consider cases. We will represent each type of case with a type vector consisting of a sequence \((a_1, a_2, \ldots, a_k)\) where each \(a_i\) is the number of blocks that have size \(i\text{.}\) For example, in partitioning \([5]\) into 3 blocks, the previous activity first asked for the number of partitions with type vector \((2,0,1,0,0)\text{,}\) two blocks of size 1 and one of size 3, and then for the number of partitions with type vector \((1,2,0,0,0)\text{,}\) one block of size 1 and two of size 2. Note that \(\sum_{i=1}^k a_i = n\) and \(\sum_{i=1}^k ia_i = k\text{.}\)

Activity 205.
(a)

How many partitions of \([6]\) are there into 3 blocks? List all the type vectors and the number of partitions for each.

(b)

Generalize to find a formula for \(S(k,k-3)\text{.}\) Then clean up the formula so it is a linear combination of \(\binom{k}{4}\text{,}\) \(\binom{k}{5}\text{,}\) and \(\binom{k}{6}\text{.}\)

Hint

While you might not get this formula by conisdering type vectors, you should be shooting to prove \(S(k, k-3) = \binom{k}{4} + 10 \binom{k}{5} + 15 \binom{k}{6}\)

Activity 206.

In how many ways can we partition \(k\) items into \(n\) blocks so that we have \(a_i\) blocks of size \(i\) for each \(i\text{?}\) That is, given the type vector \((a_1, a_2, \ldots, a_k)\text{,}\) how many partitions of \([k]\) into \(n\) blocks have that type vector.

Hint

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

Activity 207.

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

Activity 208.

Explain why \(S(k, 2) = 2^{k-1} - 1\text{.}\) Then find another expression for \(S(k,2)\) using type vectors to establish an interesting identity.

Interlude: Multinomial Coefficients.

Recall that the Stirling numbers counted the number of ways to distribute 9 distinct sandwiches to three identical sandwich bags. This suggests a more realistic question.

Activity 209.

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

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

Activity 210.

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

This is an example of a multinomial coefficient. Although these are not directly related to Stirling numbers, we can use the ideas of type vectors to investigate them. Let's do that now.

Activity 211.

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*}
Hint 1

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

Hint 2

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

Activity 212.

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

The sum principle will help here.

Activity 213.

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

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

Activity 214.

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.

Hint

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 2.3.3 Identities with Stirling Numbers

The entries in the Pascal Triangle, \(\binom{n}{k}\text{,}\) satisfy the nice recursion \(\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}\) and also have a closed formula: \(\binom{n}{k} = \frac{n!}{k!(n - k)!}\text{.}\) Activity 195 gives us a recursion for the Stirling numbers \(S(k,n)\) and, unfortunately, the best we can do for a “closed” formula is the following. 7 

This is not really a closed formula since the number of terms in the summation is not fixed.

We will prove this following an approach due to Polya. The idea is to compare Stirling numbers to surjections, which we know how to count using the principle of inclusion and exclusion (see Subsection 2.1.4).

Activity 215.

Suppose you wished to paint \(k\) houses and you have \(n\) different colors available. Each house will get a single color, but you want to ensure that each color is used at least once.

(a)

Use the principle of inclusion and exclusion to write a formula for the number of ways to paint the houses.

Hint

In what way is this problem like counting functions?

(b)

What about the paint colors and the houses does \(S(k,n)\) count? Why does this NOT answer the question? By what factor are we off?

(c)

Conclude that a formula for the Stirling numbers is

\begin{equation*} S(k,n) = \frac{1}{n!}\sum_{s=0}^n (-1)^s\binom{n}{s}(n-s)^k.\text{.} \end{equation*}
Activity 216.

What does Theorem 2.3.5 tell us about \(S(k, 2)\) (which we already know)? What do we get for \(S(k,3)\text{?}\)

Here is another identity involving Stirling numbers.

Exercise 217.

Prove Theorem 2.3.6

Hint

You have already done this as well, although not with \(x\text{.}\)

It is in this form that James Stirling originally developed these numbers. \(S(k,n)\) is used to convert from powers to binomial coefficients as shown in the following:

As an example of the previous two theorems, consider how to write \(x^3\text{.}\)

Using Theorem 2.3.6, we can write

\begin{equation*} x^3 = S(3,1)x + S(3,2)x(x-1) + S(3,3)x(x-1)(x-2) = x + 3x(x-1) + x(x-1)(x-2)\text{.} \end{equation*}

Recognizing that the factors that involve \(x\) look like a factorial, we can convert them into binomial coefficients, which is what Theorem 2.3.7 says:

\begin{equation*} x^3 = \binom{x}{1} + 3\binom{x}{2}2! + \binom{x}{3}3! = \binom{x}{1} + 6\binom{x}{2} + 6 \binom{x}{3}. \end{equation*}

Less we think this is nothing more than an interesting factoid, we can use it to establish the following.

Example 2.3.8.

Prove that \(1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2\text{.}\) In other words, the square of any triangular number is the sum of cubes!

Solution

We recognize that each cube on the left-hand side can be expressed as \(\binom{x}{1} + 6 \binom{x}{2} + 6\binom{x}{3}\text{.}\) Thus

\begin{align*} 1^3 + 2^3 + \cdots + n^3 = \amp \sum_{x=1}^n \left(\binom{x}{1} + 6 \binom{x}{2} + 6\binom{x}{3}\right)\\ = \amp \sum_{x=1}^n \binom{x}{1} + 6 \sum_{x=1}^n \binom{x}{2} + 6 \sum_{x=1}^n \binom{x}{3}\text{.} \end{align*}

Now each of the three sums of binomial coefficients can be simplified using the Hockey Stick Theorem, to get

\begin{align*} = \amp \binom{n+1}{2} + 6 \binom{n+1}{3} + 6 \binom{n+1}{4} \\ = \amp \binom{n+1}{2} + 6\left(\binom{n+1}{3}+\binom{n+1}{4}\right) \\ = \amp \binom{n+1}{2} + 6\binom{n+2}{4} \end{align*}

where the last step uses the Pascal triangle recurrence.

Finally, write these last two binomial coefficients using the factorial formula and simplify:

\begin{equation*} \frac{n(n+1)}{2} + \frac{(n+2)(n+1)n(n-1)}{4} = \left(\frac{n(n+1)}{2}\right)^2\text{.} \end{equation*}

The remainder of this section contains some additional activities related to the identities above and Stirling numbers in general.

Exercise 219.

List the sequence of elements that are row sums of the Stirling Triangle.

Exercise 220.

How many subsets \(\{a,b,c\}\) are there of \(\{2,3,4,\ldots\}\) such that \(abc = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17\text{?}\)

Exercise 221.

Let \(S = \{2,3,4,\ldots\}\text{.}\) How many ordered triples \((a,b,c)\) are there in \(S\times S \times S\) such that \(abc = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17\text{?}\)

Exercise 222.

Determine the following:

(a)

\(a, b, c\) so that \(n^4 = 24\binom{n}{4} + 6a\binom{n}{3}+2b\binom{n}{2} + c \binom{n}{1}\text{.}\)

(b)

\(a, b, c, d\) so that \(n^5 = 5!\binom{n}{5} + a\binom{n}{4} + b\binom{n}{3} + c \binom{n}{2} + d \binom{n}{1}\text{.}\)

Exercise 223.

Express \(1^4 + 2^4 + 3^4 + \cdots + n^4\) as a polynomial in \(n\text{.}\)

Exercise 224.

Why is \(4^k - 4\cdot 3^k + 6\cdot 2^k - 4\) always divisible by 24?

Subsection 2.3.4 Bell Numbers

The Bell number, \(B_{k}\text{,}\) denotes the number of ways that a set of \(k\) objects can be partitioned into nonempty subsets. We have already seen how to partition a set of \(k\) objects into exactly \(n\) subsets: \(S(k,n)\text{.}\) So then \(B_k = \sum_{n=1}^kS(k,n)\text{.}\) We take \(B_0 = 1\text{.}\)

The sequence of Bell numbers starts

\begin{equation*} 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, \ldots \end{equation*}

Notice that the first four numbers look like Catalan numbers. In fact, one of the many things the Catalan numbers count are non-crossing set partitions. 8  So if \(C_n\) counts only some of the set partitions, then it must be that \(C_n \le B_n\) for all \(n\text{.}\)

A set partition is said to be non-crossing as long as whenever \(a,b\) belong to one block and \(c,d\) belong to another, we have that \(a\) and \(b\) are both either larger or smaller than both of \(c\) and \(d\text{.}\)

The Bell numbers can be generated by constructing what is called the Bell Triangle. To construct this triangle, begin with a 1 at the top and a 1 below it. Add these two numbers together and put the sum 2, to the right of the 1 in the second column. This 2 is also the first entry of the third row. The second entry in the third row is found by adding the 2 to the number 1 above it. This sum is 3 and goes to the right of the 2. The 3 is now below a 2. Adding these two numbers produces the last number, 5, in the third row. Since 5 has no number above it, the third row is complete. 5 now becomes the first number in the fourth row and the process continues.

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877

To summarize, construction of the triangle follows two basic rules:

  1. The last number of each row is the first number of the next row.

  2. All other numbers are found by adding the number to the left of the missing number to the number directly above this same number.

When the triangle is extended, as above, the Bell Numbers are found down the first column as well as along the outside diagonal.

Exercise 225.

Why does this triangle construction give you the Bell numbers? Explain in terms of set partitions.

As with Pascal's Triangle, the Bell triangle has several interesting properties.

Exercise 226.

If the sum of a row is added to the Bell number at the end of that row, the next Bell number is obtained. For example, the sum of the fourth row plus the Bell number at the end of the row: \(15 + 20 + 27 + 37 + 52 + 52\) is 203, the next Bell number. Why does this happen?

Exercise 227.

Another pattern you might notice: the numbers of the second diagonal \(1, 3, 10, 37, 151, 674, \ldots\) are the sums of the horizontal rows. Prove this!

Rotating the triangle slightly creates a difference triangle analogous to Pascal's Triangle. The entries that are formed recursively by adding in Pascal's Triangle are now differences of the two numbers above them in the Bell triangle.

1 2 5 15 52 203 877 \(\ldots\)
1 3 10 37 151 674 \(\ldots\)
2 7 27 114 523 \(\ldots\)
5 20 87 409 \(\ldots\)
15 67 322 \(\ldots\)
52 255 \(\ldots\)
203 \(\ldots\)
Exercise 228.

Explain why the differences work as they do in the rotated triangle.

Finally, rewriting the Bell triangle recursively indicates a nice connection of the Bell Numbers to Pascal's triangle.

\(B_{0} = B_{1}\)
\(B_{1}\) \(B_{0} + B_{1} = B_{2}\)
\(B_{2}\) \(B_{1} + B_{2}\) \(B_{0} + 2B_{1} + B_{2} = B_{3}\)
\(B_{3}\) \(B_{2} + B_{3}\) \(B_{1} + B_{2} + B_{2} + B_{3}\) \(B_{0} + 3B_{1} + 3B_{2} + B_{3} = B_{4}\)

This pattern suggests the \({(n + 1)}^{\text{th}}\) Bell Number can be represented recursively by \(B_{n + 1} = \binom{n}{0} B_{0} + \binom{n}{1} B_{1} + \binom{n}{2}B_{2} + \ldots + \binom{n}{n} B_{n}\text{.}\) The coefficients of this equation are the entries of the \(n\)th row of Pascal's triangle.

Exercise 229.

Prove the recurrence

\begin{equation*} B_{k + 1} = \binom{k}{0} B_{0} + \binom{k}{1} B_{1} + \binom{k}{2}B_{2} + \ldots + \binom{k}{k} B_{k} \end{equation*}

The Bell numbers are related to the Stirling numbers and can be defined as the sum of the Stirling numbers of the second kind. That is, \(B_{k} = S(k,1) + S(k,2) + \cdots + S(k,k)\text{,}\) where \(S(k,n)\) represents the number of ways of grouping \(k\) elements into \(n\) subsets. So \(B_{3} = S(3,1) + S(3,2) + S(3,3) = 1 + 3 + 1 = 5\text{.}\) Since the Bell numbers count the partitions of a set of elements, they are used in prime-number theory to enumerate the number of ways to factor a number with distinct prime factors. For example, 42 has three distinct prime factors: 2, 3, and 7. Since \(B_{3} = 5\) , we know there are five ways of factoring 42. These are \(2 \times 3 \times 7\text{,}\) \(2 \times 21\text{,}\) \(3 \times 14\text{,}\) \(6 \times 7\text{,}\) and \(42\text{.}\) So the number \(210\text{,}\) which has 4 distinct factors, 2, 3, 5, and 7, can be factored in \(B_{4} = 15\) ways.

The Bell numbers can be used to model many real-life situations. For example, the number of different ways two people can sleep in unlabeled twin beds is \(B_{2} = 2\) ways: They can sleep in the same bed or in separate beds. The number of ways of serving a dinner consisting of three items, such as a salad, bread, and fish is \(B_{3} = 5\) ways: each could be served on a separate plate, salad and bread could be on one plate and fish on another, salad and fish on one plate and bread on another, or all three items could be on the same plate. This example serves as a model for the five ways three people can occupy three unlabeled beds, the five ways three prisoners can be handcuffed together, the five ways three nations can be form alliances, or any situation of partitioning three distinct elements into non-empty subsets.

One interesting application of Bell numbers is in counting the number of rhyme schemes possible for a stanza in poetry. There are \(B_{2} = 2\) possibilities for a two-line stanza: the lines can either rhyme or not rhyme. The possible rhyme schemes of a three-line stanza can be described as aaa, aab, aba, abb, and abc: thus there are 5 or \(B_{3}\) possible rhyme schemes. The Japanese used diagrams depicting possible rhyme schemes of a five-line stanza \(B_{5} = 52\) as early as 1000 A.D. in the Tale of the Genji by Lady Shikibu Murasaki.

Exercise 230.

List all 15 rhyme schemes for a four-line stanza. Identify the \(C_4 = 14\) such schemes that are “planar” (and say what this means).

Exercise 231.

List all 15 set partitions of \([4]\text{.}\) Identify the \(C_4 = 14\) such partitions that are “non-crossing” (and say what this means).

We conclude with an interesting exercise.

Exercise 232.

The set \(\{u_{0}, u_{1}, u_{2}, \ldots \}\) where \(u_{0} = 1\text{,}\) \(u_{1} = x\text{,}\) \(u_{2} = x(x - 1)\text{,}\) \(u_{3} = x(x - 1)(x - 2)\text{,}\) etc., is a basis for the vector space \(V\) of all polynomials with real coefficients. Let \(P(x) = c_{0}u_{0} + c_{1}u_{1} + c_{2}u_{2} + \cdots\) be any element of \(V\text{,}\) and define the functional \(L\) as follows: \(L\lbrack P(x)\rbrack = c_{0} + c_{1} + \cdots\text{.}\)

  1. Prove that \(L\left\lbrack P\left( x \right) + Q\left( x \right) \right\rbrack = L\left\lbrack P\left( x \right) \right\rbrack + L\left\lbrack Q\left( x \right) \right\rbrack.\)

  2. Prove that \(L\left\lbrack rP \left( x \right) \right\rbrack = rL\lbrack P\left( x \right)\rbrack\) for \(r \in \R\) (the Reals).

  3. Prove that \(B_{n} = L\lbrack x^{n}\rbrack\) .

  4. Prove that \(L\left\lbrack x^{n + 1} \right\rbrack = L\lbrack\left( x + 1 \right)^{n}\rbrack\) .

  5. Derive the recursion in Exercise 229 using the previous part.

login