Theorem 3.1.2
There are \(n^k\) functions from a \(k\)-element set to an \(n\)-element set.
Section 3.1 The idea of a distribution
¶Many of the problems we solved in Chapter 1 may be thought of as problems of distributing objects (such as pieces of fruit or ping-pong balls) to recipients (such as children). Some of the ways of viewing counting problems as distribution problems are somewhat indirect. For example, in Problem 37 you probably noticed that the number of ways to pass out \(k\) ping-pong balls to \(n\) children so that no child gets more than one is the number of ways that we may choose a \(k\)-element subset of an \(n\)-element set. We think of the children as recipients and objects we are distributing as the identical ping-pong balls, distributed so that each recipient gets at most one ball. Those children who receive an object are in our set. It is helpful to have more than one way to think of solutions to problems. In the case of distribution problems, another popular model for distributions is to think of putting balls in boxes rather than distributing objects to recipients. Passing out identical objects is modeled by putting identical balls into boxes. Passing out distinct objects is modeled by putting distinct balls into boxes.
Subsection 3.1.1 The twentyfold way
¶When we are passing out objects to recipients, we may think of the objects as being either identical or distinct. We may also think of the recipients as being either identical (as in the case of putting fruit into plastic bags in the grocery store) or distinct (as in the case of passing fruit out to children). We may restrict the distributions to those that give at least one object to each recipient, or those that give exactly one object to each recipient, or those that give at most one object to each recipient, or we may have no such restrictions. If the objects are distinct, it may be that the order in which the objects are received is relevant (think about putting books onto the shelves in a bookcase) or that the order in which the objects are received is irrelevant (think about dropping a handful of candy into a child's trick or treat bag). If we ignore the possibility that the order in which objects are received matters, we have created \(2\cdot2\cdot4=16\) distribution problems. In the cases where a recipient can receive more than one distinct object, we also have four more problems when the order objects are received matters. Thus we have 20 possible distribution problems.
| The Twentyfold Way: A Table of Distribution Problems | ||
| \(k\) objects and conditions on how they are received |
\(n\) recipients and mathematical model for distribution |
|
| Distinct | Identical | |
| 1. Distinct no conditions |
\(n^k\) functions |
? set partitions (\(\le n\) parts) |
| 2. Distinct Each gets at most one |
\(n^{\underline{k}}\) \(k\)-element permutations |
1 if \(k\le n\text{;}\) 0 otherwise |
| 3. Distinct Each gets at least one |
\(?\) onto functions |
\(?\) set partitions (\(n\) parts) |
| 4. Distinct Each gets exactly one |
\(k!=n!\) permutations |
1 if \(k=n\text{;}\) 0 otherwise |
| 5. Distinct, order matters |
? ? |
? ? |
| 6. Distinct, order matters Each gets at least one |
? ? |
? ? |
| 7. Identical no conditions |
? ? |
? ? |
| 8. Identical Each gets at most one |
\(\binom{n}{k}\) subsets |
1 if \(k\le n\text{;}\) 0 otherwise |
| 9. Identical Each gets at least one |
? ? |
? ? |
| 10. Identical Each gets exactly one |
1 if \(k=n\text{;}\) 0 otherwise |
1 if \(k=n\text{;}\) 0 otherwise |
We describe these problems in Table 3.1.1. Since there are twenty possible distribution problems, we call the table the “Twentyfold Way,” adapting terminology suggested by Joel Spencer for a more restricted class of distribution problems. In the first column of the table we state whether the objects are distinct (like people) or identical (like ping-pong balls) and then give any conditions on how the objects may be received. The conditions we consider are whether each recipient gets at most one object, whether each recipient gets at least one object, whether each recipient gets exactly one object, and whether the order in which the objects are received matters. In the second column we give the solution to the problem and the name of the mathematical model for this kind of distribution problem when the recipients are distinct, and in the third column we give the same information when the recipients are identical. We use question marks as the answers to problems we have not yet solved and models we have not yet studied. We give explicit answers to problems we solved in Chapter 1 and problems whose answers are immediate. The goal of this chapter is to develop methods that will allow us to fill in the table with formulas or at least quantities we know how to compute, and we will give a completed table at the end of the chapter. We will now justify the answers that are not question marks and replace some question marks with answers as we cover relevant material.
If we pass out \(k\) distinct objects (say pieces of fruit) to \(n\) distinct recipients (say children), we are saying for each object which recipient it goes to. Thus we are defining a function from the set of objects to the recipients. We saw the following theorem in Problem 13.b.
We proved it in Problem 13.b and in another way in Problem 75. If we pass out \(k\) distinct objects (say pieces of fruit) to \(n\) indistinguishable recipients (say identical paper bags) then we are dividing the objects up into disjoint sets; that is we are forming a partition of the objects into some number, certainly no more than the number \(k\) of objects, of parts. Later in this chapter (and again in the next chapter) we shall discuss how to compute the number of partitions of a \(k\)-element set into \(n\) parts. This explains the entries in row one of our table.
If we pass out \(k\) distinct objects to \(n\) recipients so that each gets at most one, we still determine a function, but the function must be one-to-one. The number of one-to-one functions from a \(k\)-element set to an \(n\) element set is the same as the number of one-to-one functions from the set \([k] =\{1,2,\ldots,k\}\) to an \(n\)-element set. In Problem 20 we proved the following theorem.
Theorem 3.1.3
If \(0\le k\le n\text{,}\) then the number of \(k\)-element permutations of an \(n\)-element set is
\begin{equation*}
n^{\underline{k}} = n(n-1)\cdots(n-k+1) =
n!/(n-k)!.
\end{equation*}
If \(k>n\) there are no one-to-one functions from a \(k\) element set to an \(n\) element, so we define \(n^{\underline{k}}\) to be zero in this case. Notice that this is what the indicated product in the middle term of our formula gives us. If we are supposed to distribute \(k\) distinct objects to \(n\) identical recipients so that each gets at most one, we cannot do so if \(k>n\text{,}\) so there are 0 ways to do so. On the other hand, if \(k\le n\text{,}\) then it doesn't matter which recipient gets which object, so there is only one way to do so. This explains the entries in row two of our table.
If we distribute \(k\) distinct objects to \(n\) distinct recipients so that each recipient gets at least one, then we are counting functions again, but this time functions from a \(k\)-element set onto an \(n\)-element set. At present we do not know how to compute the number of such functions, but we will discuss how to do so later in this chapter and in the next chapter. If we distribute \(k\) identical objects to \(n\) recipients, we are again simply partitioning the objects, but the condition that each recipient gets at least one means that we are partitioning the objects into exactly \(n\) blocks. Again, we will discuss how compute the number of ways of partitioning a set of \(k\) objects into \(n\) blocks later in this chapter. This explains the entries in row three of our table.
If we pass out \(k\) distinct objects to \(n\) recipients so that each gets exactly one, then \(k=n\) and the function that our distribution gives us is a bijection. The number of bijections from an \(n\)-element set to an \(n\)-element set is \(n!\) by Theorem 3.1.3. If we pass out \(k\) distinct objects of \(n\) identical recipients so that each gets exactly 1, then in this case it doesn't matter which recipient gets which object, so the number of ways to do so is 1 if \(k=n\text{.}\) If \(k\not=n\text{,}\) then the number of such distributions is zero. This explains the entries in row four of our table.
We now jump to row eight of our table. We saw in Problem 37 that the number of ways to pass out \(k\) identical ping-pong balls to \(n\) children is simply the number of \(k\)-element subsets of an \(n\)-element set. In Problem 39 we proved the following theorem.
Theorem 3.1.4
If \(0\le k \le n\text{,}\) the number of \(k\)-element subsets of an \(n\)-element set is given by
\begin{equation*}
\binom{n}{k} = \frac{n^{\underline{k}}}{k!}
= \frac{n!}{k!(n-k)!}.
\end{equation*}
We define \(\binom{n}{k}\) to be 0 if \(k>n\text{,}\) because then there are no \(k\)-element subsets of an \(n\)-element set. Notice that this is what the middle term of the formula in the theorem gives us. This explains the entries of row 8 of our table. For now we jump over row 9.
In row 10 of our table, if we are passing out \(k\) identical objects to \(n\) recipients so that each gets exactly one, it doesn't matter whether the recipients are identical or not; there is only one way to pass out the objects if \(k=n\) and otherwise it is impossible to make the distribution, so there are no ways of distributing the objects. This explains the entries of row 10 of our table. Several other rows of our table can be computed using the methods of Chapter 1.
Subsection 3.1.2 Ordered functions
¶Problem 122
Suppose we wish to place \(k\) distinct books onto the shelves of a bookcase with \(n\) shelves. For simplicity, assume for now that all of the books would fit on any of the shelves. Also, let's imagine pushing the books on a shelf as far to the left as we can, so that we are only thinking about how the books sit relative to each other, not about the exact places where we put the books. Since the books are distinct, we can think of a the first book, the second book and so on.
(a)
How many places are there where we can place the first book?
(b)
When we place the second book, if we decide to place it on the shelf that already has a book, does it matter if we place it to the left or right of the book that is already there?
(c)
How many places are there where we can place the second book?
Hint
If you decide to put it on a shelf that already has a book, you have two choices of where to put it on that shelf.
(d)
Once we have \(i-1\) books placed, if we want to place book \(i\) on a shelf that already has some books, is sliding it in to the left of all the books already there different from placing it to the right of all the books already or between two books already there?
(e)
In how many ways may we place the \(i\)th book into the bookcase?
Hint
Among all the places you could put books, on all the shelves, how many are to the immediate left of some book? How many other places are there?
(f)
In how many ways may we place all the books?
Problem 123
Suppose we wish to place the books in Problem 122 (satisfying the assumptions we made there) so that each shelf gets at least one book. Now in how many ways may we place the books?
Hint
How can you make sure that each shelf gets at least one book before you start the process described in Problem 122?
The assignment of which books go to which shelves of a bookcase is simply a function from the books to the shelves. But a function doesn't determine which book sits to the left of which others on the shelf, and this information is part of how the books are arranged on the shelves. In other words, the order in which the shelves receive their books matters. Our function must thus assign an ordered list of books to each shelf. We will call such a function an ordered function. More precisely, an ordered function from a set \(S\) to a set \(T\) is a function that assigns an (ordered) list of elements of \(S\) to some, but not necessarily all, elements of \(T\) in such a way that each element of \(S\) appears on one and only one of the lists. 1 The phrase ordered function is not a standard one, because there is as yet no standard name for the result of an ordered distribution problem. (Notice that although it is not the usual definition of a function from \(S\) to \(T\text{,}\) a function can be described as an assignment of subsets of \(S\) to some, but not necessarily all, elements of \(T\) so that each element of \(S\) is in one and only one of these subsets.) Thus the number of ways to place the books into the bookcase is the entry in the middle column of row 5 of our table. If in addition we require each shelf to get at least one book, we are discussing the entry in the middle column of row 6 of our table. An ordered onto function is one which assigns a list to each element of \(T\text{.}\) In Problem 122 you showed that the number of ordered functions from a \(k\)-element set to an \(n\)-element set is \(\displaystyle \prod_{i=1}^k (n+i-1)\text{.}\) This product occurs frequently enough that it has a name; it is called the \(k\)\/th rising factorial power of \(n\) and is denoted by \(n^{\overline{k}}\text{.}\) It is read as ``\(n\) to the \(k\) rising.'' (This notation is due to Don Knuth, who also suggested the notation for falling factorial powers.) We can summarize with a theorem that adds two more formulas for the number of ordered functions.
Theorem 3.1.5
The number of ordered functions from a \(k\)-element set to an \(n\)-element set is
\begin{equation*}
n^{\overline{k}}=\prod_{i=1}^k (n+i-1) = \frac{(n+i-1)!}{(n-1)!} =
(n+k-1)^{\underline{k}}.
\end{equation*}
Ordered functions explain the entries in the middle column of rows 5 and 6 of our table of distribution problems.
Subsection 3.1.3 Multisets
¶In the middle column of row 7 of our table, we are asking for the number of ways to distribute \(k\) identical objects (say ping-pong balls) to \(n\) distinct recipients (say children).
Problem 124
In how many ways may we distribute \(k\) identical books on the shelves of a bookcase with \(n\) shelves, assuming that any shelf can hold all the books?
Hint
What is the relationship between the number of ways to distribute identical books and the number of ways to distribute distinct books?
Problem 125
A multiset chosen from a set \(S\) may be thought of as a subset with repeated elements allowed. For example the multiset of letters of the word Mississippi is \(\{i,i,i,i,m,p,p,s,s,s,s\}\text{.}\) To determine a multiset we must say how many times (including, perhaps, zero) each member of \(S\) appears in the multiset. The number of times an element appears is called its multiplicity. The size of a multiset chosen from \(S\) is the total number of times any member of \(S\) appears. For example, the size of the multiset of letters of Mississippi is 11. What is the number of multisets of size \(k\) that can be chosen from an \(n\)-element set?
Hint
Look for a relationship between a multiset of shelves and a way of distributing identical books to shelves
Problem 126
Your answer in the previous problem should be expressible as a binomial coefficient. Since a binomial coefficient counts subsets, find a bijection between subsets of something and multisets chosen from a set \(S\text{.}\)
Hint
Note that \(\binom{n+k-1}{k} = \binom{n+k-1}{n-1}\text{.}\) So we have to figure out how choosing either \(k\) elements or \(n - 1\) elements out of \(n + k - 1\) elements constitutes the choice of a multiset. We really have no idea what set of \(n + k - 1\) objects to use, so why not use \([n + k - 1]\text{?}\) If we choose \(n - 1\) of these objects, there are \(k\) left over, the same number as the number of elements of our multiset. Since our multiset is supposed to be chosen from an \(n\)-element set, perhaps we should let the \(n\)-element set be \([n]\text{.}\) From our choice of \(n - 1\) numbers, we have to decide on the multiplicity of 1 through \(n\text{.}\) For example with \(n = 4\) and \(k = 6\text{,}\) we have \(n+k-1=9\text{.}\) Here, shown with underlines, is a selection of \(3=n-1\) elements from \([9]\text{:}\) \(1, 2, \underline{3}, 4 \underline{5}, 6, 7, \underline{8}, 9\text{.}\) How do the underlined elements give us a multiset of size 6 chosen from an [4]-element set? In this case, 1 has multiplicity 2, 2 has multiplicity 1, 3 has multiplicity 2, and 4 has multiplicity 1.
Problem 127
How many solutions are there in nonnegative integers to the equation \(x_1+x_2+ \cdots +x_m = r\text{,}\) where \(m\) and \(r\) are constants?
Hint
A solution to the equations assigns a nonnegative number to each of \(1,2,\ldots, m\) so that the nonnegative numbers add to \(r\text{.}\) Does such an assignment have a combinatorial meaning?
Problem 128
In how many ways can we distribute \(k\) identical objects to \(n\) distinct recipients so that each recipient gets at least \(m\text{?}\)
Hint
Can you think of some way of guaranteeing that each recipient gets \(m\) objects (assuming \(k \ge mn\)) right at the beginning of the process of passing the objects out?
Multisets explain the entry in the middle column of row 7 of our table of distribution problems.
Subsection 3.1.4 Compositions of integers
¶Problem 129
In how many ways may we put \(k\) identical books onto \(n\) shelves if each shelf must get at least one book?
Hint
We already know how to place \(k\) distinct books onto \(n\) distinct shelves so that each shelf gets at least one. Suppose we replace the distinct books with identical ones. If we permute the distinct books before replacement, does that affect the final outcome? There are other ways to solve this problem.
Problem 130
A composition of the integer \(k\) into \(n\) parts is a list of \(n\) positive integers that add to \(k\text{.}\) How many compositions are there of an integer \(k\) into \(n\) parts?
Hint
Do you see a relationship between compositions and something else we have counted already?
Problem 131
Your answer in Problem 130 can be expressed as a binomial coefficient. This means it should be possible to interpret a composition as a subset of some set. Find a bijection between compositions of \(k\) into \(n\) parts and certain subsets of some set. Explain explicitly how to get the composition from the subset and the subset from the composition.
Hint
If we line up \(k\) identical books, how many adjacencies are there in between books?
Problem 132
Explain the connection between compositions of \(k\) into \(n\) parts and the problem of distributing \(k\) identical objects to \(n\) recipients so that each recipient gets at least one.
The sequence of problems you just completed should explain the entry in the middle column of row 9 of our table of distribution problems.
Subsection 3.1.5 Broken permutations and Lah numbers
¶Problem 133
In how many ways may we stack \(k\) distinct books into \(n\) identical boxes so that there is a stack in every box? The hints may suggest that you can do this problem in more than one way!
Hint 1
Hint 2
Imagine taking a stack of \(k\) books, and breaking it up into stacks to put into the boxes in the same order they were originally stacked. If you are going to use \(n\) boxes, in how many places will you have to break the stack up into smaller stacks, and how many ways can you do this?
How many different bookcase arrangements correspond to the same way of stacking \(k\) books into \(n\) boxes so that each box has at least one book?
We can think of stacking books into identical boxes as partitioning the books and then ordering the blocks of the partition. This turns out not to be a useful computational way of visualizing the problem because the number of ways to order the books in the various stacks depends on the sizes of the stacks and not just the number of stacks. However this way of thinking actually led to the first hint in Problem 133. Instead of dividing a set up into nonoverlapping parts, we may think of dividing a permutation (thought of as a list) of our \(k\) objects up into \(n\) ordered blocks. We will say that a set of ordered lists of elements of a set \(S\) is a broken permutation of \(S\) if each element of \(S\) is in one and only one of these lists. 2 The phrase broken permutation is not standard, because there is no standard name for the solution to this kind of distribution problem. The number of broken permutations of a \(k\)-element set with \(n\) blocks is denoted by \(L(k,n)\text{.}\) The number \(L(k,n)\) is called a Lah Number and, from our solution to Problem 133, is equal to \(k!\binom{k-1}{n-1}/n!\text{.}\)
The Lah numbers are the solution to the question ``In how many ways may we distribute \(k\) distinct objects to \(n\) identical recipients if order matters and each recipient must get at least one?" Thus they give the entry in row 6 and column 3 of our table. The entry in row 5 and column 3 of our table will be the number of broken permutations with less than or equal to \(n\) parts. Thus it is a sum of Lah numbers.
We have seen that ordered functions and broken permutations explain the entries in rows 5 and 6 of our table.
In the next two sections we will give ways of computing the remaining entries.