In Section 2.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{.}\)
Activity196
Suppose you have \(3\) distinct 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? 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?
Activity197
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.
Recall that a partition of a set \(A\) is a set of subsets of \(A\) such that every element of \(A\) is in exactly one of the subsets. Sometimes we will call the subsets that make up a partition blocks.
Definition3.1.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 renamed variables, formulas might look different.
For example, consider how to partition \([3]\) into exactly two sets:
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.
Activity198
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{.}\)
We can arrange the Stirling numbers into a triangle (called Stirlings 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, I could have written out all 25 of the partitions of \([5]\) into exactly \(3\) blocks, but I 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?
Activity199
(a)
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 is solitary confinement (in a singleton set) or does he have a cellmate?
(b)
How could you take the \(S(4,2) = 7\) partitions of \([4]\) into 2 sets and the \(S(4,3) = 6\) partitions of \([4]\) into 3 sets and form all the \(S(5,3) = 25\) partitions of \([5]\) into \(3\) sets?
Activity200
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(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.
Activity201
Find a recurrence for the Lah numbers \(L(k,n)\) similar to the one in Activity 200.
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{.}\)
Activity202
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.
Activity203
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.
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 in Section 3.2.
Activity204
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?
Activity205
In how many ways can the sandwiches of Activity 202 be placed into three distinct bags so that each bag gets at least one?
We will further investigate Stirling numbers in Section 3.4. Before leaving set partitions though, notice that we have not looked at the number of ways to partition a set into any number of blocks.
Definition3.1.2
The total number of partitions of a \(k\)-element set is denoted by \(B_k\) and is called the \(k\)-th Bell number.
Activity206
(a)
Show, by explicitly exhibiting the partitions, that \(B_1 = 1\text{,}\) \(B_2 = 2\text{,}\) and \(B_3 = 5\text{.}\)
(b)
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?
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.
(c)
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.
(d)
Find \(B_k\) for \(k=4,5,6\text{.}\)
The Bell numbers are interesting in their own right, and we will look at them more in Section 3.5.
In Activity 128, we counted the compositions of an integer \(n\text{,}\) by counting the number of solutions to the equation \(x_1 + x_2 + \cdots + x_k = n\) where each \(x_i\) is a positive integer. Put another way, we asked how many lists of \(k\) positive integers have sum \(n\text{.}\) The order in which we listed the sum mattered. What if it didn't?
A multiset of positive integers that add to \(n\) is called a partition of \(n\text{.}\) Thus the partitions of 3 are 1+1+1, 1+2 (which is the same as 2+1) and 3. The number of partitions of \(k\) is denoted by \(p(k)\text{;}\) in computing the partitions of 3 we showed that \(p(3) = 3\text{.}\) It is traditional to use Greek letters like \(\lambda\) to stand for partitions; we might write \(\lambda = 1,1,1\text{,}\) \(\gamma= 2,1\) and \(\tau = 3\) to stand for the three partitions we just described. We also write \(\lambda = 1^3\) as a shorthand for \(\lambda = 1,1,1\text{,}\) and we write \(\lambda \dashv 3\) as a shorthand for “\(\lambda\) is a partition of three.”
Activity207
Find all partitions of 4 and find all partitions of 5, thereby computing \(p(4)\) and \(p(5)\text{.}\)
A partition of the integer \(k\) into \(n\) parts is a multiset of \(n\) positive integers that add to \(k\text{.}\) We use \(p_n(k)\) to denote the number of partitions of \(k\) into \(n\) parts. Thus \(p_n(k)\) is the number of ways to distribute \(k\) identical objects to \(n\) identical recipients so that each gets at least one.
Activity208
Find \(p_3(6)\) by finding all partitions of 6 into 3 parts. What does this say about the number of ways to put six identical apples into three identical bags so that each bag has at least one apple?
Activity209
How many solutions are there in the positive integers to the equation \(x_1+x_2+x_3 =7\) with \(x_1\ge x_2\ge x_3\text{?}\)
Activity210
Explain the relationship between partitions of \(k\) into \(n\) parts and lists \(x_1,x_2\text{,}\)…, \(x_n\) of positive integers with \(x_1\ge x_2\ge\ldots \ge x_n\text{.}\) Such a representation of a partition is called a decreasing list representation of the partition.
Activity211
Show that \(p_n(k)\) is at least \(\frac{1}{n!}\binom{k-1}{n-1}\text{.}\)
How many compositions are there of \(k\) into n parts? What is the maximum number of compositions that could correspond to a given partition of \(k\) into \(n\) parts?
Activity212
Describe the relationship between partitions of \(k\) and lists or vectors \((x_1,x_2,\ldots,x_n)\) such that \(x_1+2x_2+\ldots kx_k = k\text{.}\) Such a representation of a partition is called a type vector representation of a partition, and it is typical to leave the trailing zeros out of such a representation; for example \((2,1)\) stands for the same partition as \((2,1,0,0)\text{.}\) What is the decreasing list representation for this partition, and what number does it partition?
Activity213
How does the number of partitions of \(k\) relate to the number of partitions of \(k+1\) whose smallest part is one?
How can you start with a partition of \(k\) and make it into a new partition of \(k+1\) that is guaranteed to have a part of size one, even if the original partition didn't?
When we write a partition as \(\lambda = \lambda_1,\lambda_2,\ldots,\lambda_n\text{,}\) it is customary to write the list of \(\lambda_i\)s as a decreasing list. When we have a type vector \((t_1,t_2,\ldots,t_m)\) for a partition, we write either \(\lambda = 1^{t_1}2^{t_2}\cdots m^{t_m}\) or \(\lambda = m^{t_m}(m-1)^{t_{m-1}}\cdots 2^{t_2}1^{t_1}\text{.}\) Henceforth we will use the second of these. When we write \(\lambda=\lambda_1^{i_1}\lambda_2^{i_2}\cdots\lambda_n^{i_n}\text{,}\) we will assume that \(\lambda_i>\lambda_i+1\text{.}\)
The decreasing list representation of partitions leads us to a handy way to visualize partitions. Given a decreasing list \((\lambda_1,\lambda_2,\ldots \lambda_n)\text{,}\) we draw a figure made up of rows of dots that has \(\lambda_1\) equally spaced dots in the first row, \(\lambda_2\) equally spaced dots in the second row, starting out right below the beginning of the first row and so on. Equivalently, instead of dots, we may use identical squares, drawn so that a square touches each one to its immediate right or immediately below it along an edge. See Figure 3.1.3 for examples. The figure we draw with dots is called the Ferrers diagram of the partition; sometimes the figure with squares is also called a Ferrers diagram; sometimes it is called a Young diagram. At this stage it is irrelevant which name we choose and which kind of figure we draw; in more advanced work the squares are handy because we can put things like numbers or variables into them. From now on we will use squares and call the diagrams Young diagrams.
Figure3.1.3The Ferrers and Young diagrams of the partition (5,3,3,2)
Activity214
Just for practice, draw all the Young diagrams for the partitions of 4 and 5.
With the binomial coefficients, with Stirling numbers of the second kind, and with the Lah numbers, we were able to find a recurrence by asking what happens to our subset, partition, or broken permutation of a set \(S\) of numbers if we remove the largest element of \(S\text{.}\) Thus it is natural to look for a recurrence to count the number of partitions of \(k\) into \(n\) parts by doing something similar. Unfortunately, since we are counting distributions in which all the objects are identical, there is no way for us to identify a largest element. However if we think geometrically, we can ask what we could remove from a Young diagram to get a Young diagram. Two natural ways to get a partition of a smaller integer from a partition of \(n\) would be to remove the top row of the Young diagram of the partition and to remove the left column of the Young diagram of the partition. These two operations correspond to removing the largest part from the partition and to subtracting 1 from each part of the partition respectively. Even though these have some sort of geometric symmetry, the two operations are not symmetric with respect to the number of parts. Thus one might be much more useful than the other for finding a recurrence for the number of partitions of \(k\) into \(n\) parts.
Activity215
In this problem we will study the two operations and see which one seems more useful for getting a recurrence for \(p_n(k)\text{.}\)
(a)
How many parts does the remaining partition have when we remove the largest part (more precisely, we reduce its multiplicity by one) from a partition of \(k\) into \(n\) parts? What can you say about the number of parts of the remaining partition if we remove one from each part?
These two operations do rather different things to the number of parts, and you can describe exactly what only one of the operations does. Think about the Young diagram.
(b)
If we remove the largest part from a partition, what can we say about the integer that is being partitioned by the remaining parts of the partition? If we remove one from each part of a partition of \(k\) into \(n\) parts, what integer is being partitioned by the remaining parts? (Another way to describe this is that we remove the first column from the Young diagram of the partition.)
Think about the Young diagram. In only one of the two cases can you give an exact answer to the question.
(c)
The last two questions are designed to get you thinking about how we can get a bijection between the set of partitions of \(k\) into \(n\) parts and some other set of partitions that are partitions of a smaller number. These questions describe two different strategies for getting that set of partitions of a smaller number or of smaller numbers. Each strategy leads to a bijection between partitions of \(k\) into \(n\) parts and a set of partitions of a smaller number or numbers. For each strategy, use the answers to the last two questions to find and describe this set of partitions into a smaller number and a bijection between partitions of \(k\) into \(n\) parts and partitions of the smaller integer or integers into appropriate numbers of parts. (In one case the set of partitions and bijection are relatively straightforward to describe and in the other case not so easy.)
Here the harder part requires that, after removal, you consider a range of possible numbers being partitioned and that you give an upper bound on the part size. However it lets you describe the number of parts exactly.
(d)
Find a recurrence (which need not have just two terms on the right hand side) that describes how to compute \(p_n(k)\) in terms of the number of partitions of smaller integers into a smaller number of parts.
One of the two sets of partitions of smaller numbers from the previous part is more amenable to finding a recurrence than the other. The resulting recurrence does not have just two terms though.
(e)
What is \(p_1(k)\) for a positive integer \(k\text{?}\)
(f)
What is \(p_k(k)\) for a positive integer \(k\text{?}\)
(g)
Use your recurrence to compute a table with the values of \(p_n(k)\) for values of \(k\) between 1 and 7.
(h)
What would you want to fill into row 0 and column 0 of your table in order to make it consistent with your recurrence. What does this say \(p_0(0)\) should be? We usually define a sum with no terms in it to be zero. Is that consistent with the way the recurrence says we should define \(p_0(0)\text{?}\)
If there is a sum equal to zero, there may very well be a partition of zero.
It is remarkable that there is no known formula for \(p_n(k)\text{,}\) nor is there one for \(p(k)\text{.}\) We have seen some ways to compute values of \(p_n(k)\text{.}\) In Section 3.6 we will see more methods to compute values and find properties of these numbers even without ever knowing a formula for them.
