Subsection Section Preview
Investigate!
Skittles come in five “flavors”. How many different handfuls of 8 skittles are possible?
Suppose you have baked 8 identical cupcakes to give to your top five favorite discrete math teachers. How many ways can you distribute the cupcakes?
Why are the answers to the two counting questions above the same?
We know how to solve lots of types of counting problems now. If each outcome in a set of outcomes we are counting can be represented by a sequence, we count it as a permutation (if the terms in the sequence don’t repeat) or use the product principle (if they do). If we are counting outcomes for which we don’t distinguish between different arrangements of the terms (if order doesn’t matter) then we think of the outcome as a set and count it as a combination. However, sets never allow an element to be repeated; each element is either in a set or not.
So we have a glaring hole in our counting repertoire. What if we want to count outcomes that are collections of terms for which we do not distinguish between the order the terms appear in, but can contain terms more than once? In other words, how can we complete the following table?
|
Distinguished Arrangements? |
|
Yes |
No |
| Repeats OK |
Sequences
Prod. Principle
\(n^k\)
|
|
| No repeats |
Sequences
Permutations
\(P(n,k)\)
|
Sets
Combinations
\(\binom{n}{k}\)
|
What we want to count are some sort of set-like structure but one that does permit elements in the set to appear more than once. Such structures are called multiset.
Definition 3.5.1.
A multiset is an unordered collection of elements, each of which can appear any number of times. The number of times an element appears is called its multiplicity.
Multisets are written using the same notation as sets as a comma-separated list in braces, such as \(\{1, 2, 2, 5\}\)
In this section, we will explore how multisets can be used to represent a wide range of counting problems. We will then develop a way to translate multisets into a special type of bit-string so that we can use the numbers in Pascal’s triangle to count the number of multisets.
Worksheet Preview Activity
1.
Subsection Have some cookies
Consider the following counting problem:
You have 7 cookies to give to 4 kids. How many ways can you do this?
Take a moment to think about how you might solve this problem. You may assume that it is acceptable to give a kid no cookies. Also, the cookies are all identical and the order in which you give out the cookies does not matter (so giving cookies to the second kid before the first kid does not count as a separate outcome as the other way around).
Before solving the problem, here is a wrong answer: You might guess that the answer should be \(4^7\) because, for each of the 7 cookies, there are 4 choices of kids to which you can give the cookie. This is reasonable, but wrong. To see why, consider a few possible outcomes: we could assign the first six cookies to kid A, and the seventh cookie to kid B. Another outcome would assign the first cookie to kid B and the six remaining cookies to kid A. Both outcomes are included in the \(4^7\) answer. But for our counting problem, both outcomes are really the same – kid A gets six cookies and kid B gets one cookie. This would have been the correct answer if the cookies were all different, but they are not.
What do outcomes actually look like? How can we represent them? One approach would be to write an outcome as a string of four numbers like this:
\begin{equation*}
3112\text{,}
\end{equation*}
which represents the outcome in which the first kid gets 3 cookies, the second and third kid each get 1 cookie, and the fourth kid gets 2 cookies. Represented this way, the order in which the numbers occur matters. 1312 is a different outcome, because the first kid gets one cookie instead of 3. Each number in the string can be any integer between 0 and 7. But the answer is not \(7^4\text{.}\) We need the sum of the numbers to be 7.
Another way we might represent outcomes is to write a string of seven letters:
\begin{equation*}
\text{ABAADCD}\text{,}
\end{equation*}
which represents that the first cookie goes to kid A, the second cookie goes to kid B, the third and fourth cookies go to kid A, and so on. In fact, this outcome is identical to the previous one—A gets 3 cookies, B and C get 1 each, and D gets 2. Each of the seven letters in the string can be any of the 4 possible letters (one for each kid), but the number of such strings is not \(4^7\text{,}\) because here order does not matter. In fact, another way to write the same outcome is
\begin{equation*}
\text{AAABCDD}\text{.}
\end{equation*}
This will be the preferred representation of the outcome. Since we can write the letters in any order, we might as well write them in alphabetical order for the purposes of counting. So we will write all the A’s first, then all the B’s, and so on. In fact, since we do not distinguish between the different arrangements, it is like we are writing a set, just that this multiset can contain an element more than one time.
So we now have two useful ways to think of the outcomes.
As a multiset containing 7 elements, each of which is one of the four kids (or letter representing their names). For example,
\begin{equation*}
\{A, A, A, B, C, D, D\}\text{.}
\end{equation*}
Each time a kid is in the multiset, it means that kid gets a cookie, so the multiplicity of the kid in the multiset is the number of cookies the kid gets.
As a string of 4 non-negative numbers with a sum of 7. For example,
\begin{equation*}
3112\text{.}
\end{equation*}
The position of the number in the string represents the kid, and the number itself represents the number of cookies that kid gets.
Before we think about how to count the number of outcomes represented this way, here are a couple more examples of counting problems we can represent in these ways.
Example 3.5.2.
You grab a handful of ten jelly beans from a bag that contains six flavors. Write down three possible outcomes using both multisets and strings of numbers.
Solution.
Multisets are the more natural way to think of this problem since each handful is a multiset of flavors. So for example we could have,
\begin{equation*}
\{R, R, G, G, G, B, B, B, B, Y\}
\end{equation*}
meaning you got two red, three green, four blue, and one yellow jelly bean (and no purple, or orange), or
\begin{equation*}
\{R, R, R, R, R, R, R, R, R, R\}
\end{equation*}
which means you got ten red jelly beans. You could also have
\begin{equation*}
\{R, G, B, Y, P, O, O, O, O, O\}
\end{equation*}
meaning you have one each of red, green, blue, and yellow, and five orange jelly beans.
The corresponding sequences of six numbers summing to 10 are
\begin{equation*}
2,3,4,1,0,0; \qquad 10,0,0,0,0,0; \qquad 1,1,1,1,1,5\text{.}
\end{equation*}
(We added commas between numbers since not every number is a single digit.) Notice that for this representation we need to agree on a fixed order of the flavors, which was not alphabetical in this case, but the same order we used when listing the multisets.
Example 3.5.3.
You have 12 identical copies of your favorite Discrete Math book that you want to put on 5 bookshelves. Write down three possible outcomes using both multisets and strings of numbers.
Solution.
Here the sequences of numbers are more natural, since we can just say how many books go on each shelf. We will need 5 numbers that add up to 12. For example, we could have
\(3,3,3,2,1\) meaning 3 books on the first shelf, 3 on the second, 3 on the third, 2 on the fourth, and 1 on the fifth.
\(0,0,12,0,0\) meaning all 12 books are on the middle shelf.
\(1,1,1,1,8\) meaning one book on each of the first four shelves and 8 on the last.
The corresponding multisets are
\(\{1,1,1,2,2,2,3,3,3,4,4,5\}\) meaning shelf 1 is assigned a book three times, shelf 2 is assigned a book three times, etc. Notice that there are 12 elements in the multiset, one for each book. The numbers here represent the shelves, the multiplicity of the number is the number of books on that shelf.
\(\{3,3,3,3,3,3,3,3,3,3,3,3\}\text{.}\) The only shelf in the multiset is shelf 3, with multiplicity 12, meaning that shelf 3 gets 12 books.
\(\{1,2,3,4,5,5,5,5,5,5,5,5\}\text{.}\) Here shelf 1 gets one book, shelf 2 gets one book, shelf 3 gets one book, shelf 4 gets one book, and shelf 5 gets the rest.
This last example could also have been asked as a question about solving equations with non-negative integer solutions. In particular, we could have asked for solutions to the equation \(a+b+c+d+e = 12\text{.}\) Think of each variable as saying how many books go on each shelf. We will ask questions directly like this, but realizing how to represent other questions as such an equation can be useful.
Subsection Representing multisets with bit strings
Now let’s return to the original problem of distributing 7 cookies to 4 kids and actually count the number of outcomes.
When we were counting plain old sets, we saw that the numbers in Pascal’s triangle gave us the counts. In fact, we saw this was true because we could represent each set as a bit string. Whenever an element was in the set, we would denote that with a 1, and if the element was not in the set, we would mark its absence with a 0.
This is essentially what we did with multisets but had to use strings of non-negative numbers beyond just 0 and 1, since an element in a multiset can appear more than 0 or 1 times. But if we could translate those strings of numbers into some other sort of bit string, then we could use Pascal’s triangle to count the number of multisets.
Here is how we can do this. Given a multiset such as
\begin{equation*}
\{A, A, A, B, C, D, D\}
\end{equation*}
we have a number sequence representation as
\begin{equation*}
3,1,1,2\text{.}
\end{equation*}
Well, instead of individual numbers, write each as a sequence of that many 1s. So this example becomes
\begin{equation*}
111,1,1,11\text{.}
\end{equation*}
This is slightly awkward since we are using commas to separate the numbers. To make this clearer, let’s switch to two different symbols. We will call them sticks and stones, where the stone represents a 1 and the stick represents a comma. So the sequence
\begin{equation*}
111,1,1,11
\end{equation*}
becomes
\begin{equation*}
\o\o\o|\o|\o|\o\o\text{.}
\end{equation*}
This is a string of ten symbols, 7 of which are stones and 3 of which are sticks.
This is fantastic! Whatever two symbols we use (you might also see these called stars and bars or balls and bins), we can use Pascal’s triangle to count the number of ways to arrange them. The number of 10-bit strings of weight 3 (or weight 7) is \(\binom{10}{3} = 120\text{.}\)
In terms of cookies, we can view this sticks and stones diagram as saying after how many cookies we stop giving cookies to the first kid and start giving cookies to the second kid. And then after how many do we switch to the third kid? And after how many do we switch to the fourth? So
\begin{equation*}
\o\o\o|\o|\o|\o\o
\end{equation*}
means three cookies go to the first kid, then we switch and give one cookie to the second kid, then switch, one to the third kid, switch, two to the fourth kid. Notice that we need 7 stones and 3 sticks – one stone for each cookie, and one stick for each switch between kids, so one fewer sticks than there are kids (we don’t need to switch after the last kid – we are done).
While we are at it, we can also answer a related question: how many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie? What can you say about the corresponding sticks and stones charts? The charts must start and end with at least one stone (so that kids A and D) get cookies, and also no two sticks can be adjacent (so that kids B and C are not skipped). One way to ensure this is to place sticks only in the spaces between the stones. With 7 stones, there are 6 spots between the stones, so we must choose 3 of those 6 spots to fill with bars. Thus there are \({6 \choose 3}\) ways to distribute 7 cookies to 4 kids giving at least one cookie to each kid.
Another (and more general) way to approach this modified problem is to first give each kid one cookie. Now the remaining 3 cookies can be distributed to the 4 kids without restrictions. So we have 3 stones and 3 sticks for a total of 6 symbols, 3 of which must be bars. So again we see that there are \({6 \choose 3}\) ways to distribute the cookies.
Sticks and stones can be used in counting problems other than kids and cookies. Here are a few examples:
Example 3.5.4.
Your favorite mathematical ice cream parlor offers 10 flavors. How many milkshakes could you create using exactly 6, not necessarily distinct scoops? The order you add the flavors does not matter (they will be blended up anyway) but you are allowed repeats. So one possible shake is triple chocolate, double cherry, and mint chocolate chip.
Solution.
We get six scoops, each of which could be one of ten possible flavors. Represent each scoop as a star. Think of going down the counter one flavor at a time: you see vanilla first, and skip to the next, chocolate. You say yes to chocolate three times (use three stones), then switch to the next flavor. You keep skipping until you get to cherry, which you say yes to twice. Another switch and you are at mint chocolate chip. You say yes once. Then you keep switching until you get past the last flavor, never saying yes again (since you already have said yes six times). There are ten flavors to choose from, so we must switch from considering one flavor to the next nine times. These are the nine bars.
Now that we are confident that we have the right number of sticks and stones, we answer the question simply: there are 6 stones and 9 bars, so 15 symbols. We need to pick 9 of them to be bars, so the number of milkshakes possible is
\begin{equation*}
\binom{15}{9}\text{.}
\end{equation*}
Example 3.5.5.
How many 7 digit phone numbers are there in which the digits are non-increasing? That is, every digit is less than or equal to the previous one.
Solution.
We need to decide on 7 digits so we will use 7 stones. The sticks will represent a switch from each possible single-digit number down to the next smaller one. So the phone number 866-5221 is represented by the sticks and stones chart
\begin{equation*}
|\o||\o\o|\o|||\o\o|\o|\text{.}
\end{equation*}
There are 10 choices for each digit (0-9) so we must switch between choices 9 times. We have 7 stones and 9 bars, so the total number of phone numbers is
\begin{equation*}
{16 \choose 9}\text{.}
\end{equation*}
Example 3.5.6.
How many integer solutions are there to the equation
\begin{equation*}
x_1 + x_2 + x_3 + x_4 + x_5 = 13\text{.}
\end{equation*}
(An integer solution to an equation is a solution in which the unknown must have an integer value.)
where \(x_i \ge 0\) for each \(x_i\text{?}\)
where \(x_i > 0\) for each \(x_i\text{?}\)
where \(x_i \ge 2\) for each \(x_i\text{?}\)
Solution.
This problem is just like giving 13 cookies to 5 kids. We need to say how many of the 13 units go to each of the 5 variables. In other words, we have 13 stones and 4 bars (the sticks are like the “+” signs in the equation).
If \(x_i\) can be 0 or greater, we are in the standard case with no restrictions. So 13 stones and 4 sticks can be arranged in \({17 \choose 4}\) ways.
Now each variable must be at least 1. So give one unit to each variable to satisfy that restriction. Now there are 8 stones left, and still 4 bars, so the number of solutions is \({12 \choose 4}\text{.}\)
Now each variable must be 2 or greater. So before any counting, give each variable 2 units. We now have 3 remaining stones and 4 bars, so there are \({7 \choose 4}\) solutions.
Counting with Functions.
Many of the counting problems in this section might at first appear to be examples of counting functions. After all, when we try to count the number of ways to distribute cookies to kids, we are assigning each cookie to a kid, just like you assign elements of the domain of a function to elements in the codomain. However, the number of ways to assign 7 cookies to 4 kids is \({10 \choose 7} = 120\text{,}\) while the number of functions \(f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}\) is \(4^7 = 16384\text{.}\) What is going on here?
When we count functions, we consider the following two functions, for example, to be different:
\begin{equation*}
f = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{a \amp b \amp c \amp c \amp c \amp c \amp c} \qquad g = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{b \amp a \amp c \amp c \amp c \amp c \amp c}\text{.}
\end{equation*}
But these two functions would correspond to the same cookie distribution: kids \(a\) and \(b\) each get one cookie, kid \(c\) gets the rest (and none for kid \(d\)).
The point: elements of the domain are distinguished, cookies are indistinguishable. This is analogous to the distinction between permutations (like counting functions) and combinations (not).
