Counting Multisets

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?

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

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.

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: \[3112\], which represents the outcome in which the first kid gets 3 cookies, the second and third kids 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\). We need the sum of the numbers to be 7.

Another way we might represent outcomes is to write a string of seven letters: \[\text{ABAADCD}\], 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 oneA 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\), because here order does not matter. In fact, another way to write the same outcome is \[\text{AAABCDD}\].

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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

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 \[\{A, A, A, B, C, D, D\}\] we have a number sequence representation as \[3,1,1,2\]. Well, instead of individual numbers, write each as a sequence of that many 1s. So this example becomes \[111,1,1,11\]. 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 \[111,1,1,11\] becomes \[\o\o\o|\o|\o|\o\o\]. 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\).

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 \[\o\o\o|\o|\o|\o\o\] 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).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.