Subsection 2.5.2 Combinations with Repetition
Suppose we don’t care about the order and items can be repeated or items are indistinguishable from each other.
Consider the following counting problem:
\begin{equation*}
\mbox{You have 7 identical cookies to give to 4 kids.}\\\mbox{ How many ways can you do this?}
\end{equation*}
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 order in which you give out the cookies does not matter.
You might guess that each cookie can be assigned to one of four possible kids and by
The Rule Of Products the answer should be
\(4^7\text{.}\) However, this doesn’t work. 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 because the cookies are identical, both of those outcomes are really the same, kid A gets six cookies and kid B gets one cookie.
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,
\end{equation*}
to represent 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 a one cookie instead of 3. Each number in the string can be any integer between 0 and 7. But we cannot use the
The Rule Of Products because the
sum of the numbers must be 7.
Another way we might represent outcomes is to write a string of seven letters:
\begin{equation*}
\mbox{ABAADCD} ,
\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 again we cannot use
The Rule Of Products because here order does
not matter. In fact, another way to write the same outcome is
\begin{equation*}
\mbox{AAABCDD} .
\end{equation*}
Now think about how you could specify such an outcome in general. All we really need to do is say when to switch from one letter to the next. In terms of cookies, we need to say after how many cookies do 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 yet another way to represent an outcome is like this:
\begin{equation*}
***|*|*|**
\end{equation*}
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 stars and 3 bars – one star for each cookie, and one bar for each switch between kids, so one fewer bars than there are kids (we don’t need to switch after the last kid – we are done).
Why have we done all of this? Simple: to count the number of ways to distribute 7 cookies to 4 kids, all we need to do is count how many different stars and bars charts there are.
Before we get too excited, we should make sure that really any string of (in our case) 7 stars and 3 bars corresponds to a different way to distribute cookies to kids. In particular consider a string like this:
\begin{equation*}
|***||****
\end{equation*}
Does that correspond to a cookie distribution? Yes. It represents the distribution in which kid A gets 0 cookies (because we switch to kid B before any stars), kid B gets three cookies (three stars before the next bar), kid C gets 0 cookies (no stars before the next bar) and kid D gets the remaining 4 cookies. No matter how the stars and bars are arranged, we can distribute cookies in that way. Also, given any way to distribute cookies, we can represent that with a stars and bars chart. For example, the distribution in which kid A gets 6 cookies and kid B gets 1 cookie has the following chart:
\begin{equation*}
******|*||
\end{equation*}
After all that work we are finally ready to count. Each way to distribute 7 cookies to 4 kids corresponds to a stars and bars chart with 7 stars and 3 bars. So there are 10 symbols, and we must choose 3 of them to be bars. Thus:
\begin{equation*}
\mbox{ There are } {10 \choose 3 } = \frac{10!}{(10-3)!3!} = \frac{10*9*8}{3*2*1} = 120 \mbox{ ways to distribute 7 cookies to 4 kids.}
\end{equation*}
We generalize this result in the following theorem:
Theorem 2.5.2. Combination with Repetition Formula.
This is just counting the number of combinations of positions for \(n-1\) bars (or \(k\) stars) in a sequence with \(n+k-1\) positions. It is the same as choosing \(n-1\) items from a set of \(n+k-1\) elements.
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?
Giving each kid one cookie is required and there is no choice. We only need to count how the remaining 3 cookies can be distributed to the 4 kids. So we have 3 stars and 3 bars for a total of 6 symbols, 3 of which must be bars. So we see that there are \({6 \choose 3}\) ways to distribute the cookies.
Stars and bars can be used in counting problems other than kids and cookies. Here are a few examples:
Example 2.5.3. Counting Pizzas with Repeated Toppings.
Your favorite mathematical pizza chain offers 10 toppings. How many pizzas can you make if you are allowed 6 toppings? The order of toppings does not matter but now you are allowed repeats. So one possible pizza is triple sausage, double pineapple, and onions.
Solution.
We get 6 toppings (counting possible repeats). Represent each of these toppings as a star. Think of going down the menu one topping at a time: you see anchovies first, and skip to the next, sausage. You say yes to sausage 3 times (use 3 stars), then switch to the next topping on the list. You keep skipping until you get to pineapple, which you say yes to twice. Another switch and you are at onions. You say yes once. Then you keep switching until you get to the last topping, never saying yes again (since you already have said yes 6 times. There are 10 toppings to choose from, so we must switch from considering one topping to the next 9 times. These are the bars.
Now that we are confident that we have the right number of stars and bars, we answer the question simply: there are 6 stars and 9 bars, so 15 symbols. We need to pick 9 of them to be bars, so there number of pizzas possible is
\begin{equation*}
{15 \choose 9} = \frac{15!}{(15-9)!9!} = \frac{15*14*13*12*11*10}{6*5*4*3*2*1} = 5005\text{.}
\end{equation*}
Example 2.5.4. Counting Phone Numbers with Non-Increasing Digits.
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 stars. The bars will represent a switch from each possible single digit number down the next smaller one. So the phone number 866-5221 is represented by the stars and bars chart
\begin{equation*}
|*||**|*|||**|*|
\end{equation*}
There are 10 choices for each digit (0-9) so we must switch between choices 9 times. We have 7 stars and 9 bars, so the total number of phone numbers is
\begin{equation*}
{16 \choose 9}.
\end{equation*}
Example 2.5.5. Counting Solutions to Equations.
How many solutions are there to the equation
\begin{equation*}
x_1 + x_2 + x_3 + x_4 + x_5 = 13.
\end{equation*}
if \(x_1, x_2, x_3, x_4\) and \(x_5\) are integers?
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 stars and 4 bars (the bars 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 stars and 4 bars 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 stars 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 stars and 4 bars, so there are \({7 \choose 4}\) solutions.
Subsection 2.5.3 Ordering Indistinguishable Objects
In the previous section, we examined how many ways we can choose from a limited number indistinguishable objects, where the order didn’t matter. If one child got four cookies, it didn’t matter if she was given one first and the other three after all the rest of the cookies were given out to the other children. What can we do if the order of choosing does matter?
Example 2.5.6. Counting Strings With Repeated Letters.
Suppose we wish to count the number of ways we can rearrange the letters in the word "PROCESSES". For this kind of counting problem we cannot apply the Permutation Formula because two letters, "S" and "E", are repeated. We also cannot use the Rule of Products because the repetition is limited, we only have three "S"s, two "E"s, and one each of "P", "R", "O" and "C" to choose.
We have nine positions to fill. We can first choose three of those positions for the "S"s: \(\binom{9}{3}\) (note we use the binomial formula because the "S"s are identical, the order of the "S"s doesn’t matter). Then we will have six positions left to fill. We can choose two of those for the "E"s: \(\binom{6}{2}\) That leaves four positions for "P", three for "R", two for "O" and one for "C": \(\binom{4}{1}\text{,}\) \(\binom{3}{1}\) , \(\binom{2}{1}\text{,}\) \(\binom{1}{1}\)
We can then apply the product rule to determine how many ways there are to do all of those:
\begin{align*}
\binom{9}{3} \binom{6}{2} \binom{4}{1} \binom{3}{1} \binom{2}{1} \binom{1}{1} \amp
= \frac{9!}{6!3!} * \frac{6!}{4!2!} * \frac{4!}{3!1!} * \frac{3!}{2!1!} * \frac{2!}{1!1!} * \frac{1!}{0!1!} \\
\amp \text{Most cancel or are 1}\\
\amp = \frac{9!}{3!2!1!1!1!}\\
\amp = 30240
\end{align*}
Definition 2.5.7. Multiset.
A multiset is a collection of objects, just like a set, but can contain an object more than once (the order of the elements still doesn’t matter). For example, \(\{1,1, 2, 5, 5, 7\}\) is a multiset of size 6.
Definition 2.5.8. Multiplicity.
The multiplicity of a particular type of object is the number of times objects of that type appear in a multiset. For example, in the word "PROCESSES", the letter "S" has multiplicity three, the letter "E" has multiplicity two, and "P", "R", "O" and "C" each have multiplicity one.
We can generalize the result from
Example 2.5.6 to the following theorem.
Theorem 2.5.9. Permutations Of Multisets.
The number of ordered \(n\)-tuples (or permutations with repetition) on a collection or multiset of \(n\) objects, where there are \(k\) kinds of objects and object kind 1 occurs with multiplicity \(n_1\text{,}\) object kind 2 occurs with multiplicity \(n_2\text{,}\) ... , and object kind \(k\) occurs with multiplicity \(n_k\) is:
\begin{equation*}
\frac{n!}{n_1!*n_2!*\dots * n_k!}
\end{equation*}
Example 2.5.10. Counting Bridge Hands.
We saw this example in
Subsection 2.4.3. Now we have a formula to solve it directly, though it might not seem like the same type of problem at first.
In bridge, the location of a hand in relation to the dealer has some bearing on the game. The number of possible hands takes into account the number each player’s possible hands depending on the order in which they are dealt. The player in the West position gets their 13 cards first, then the player in the North position gets 13 cards, then the player in the East gets 13 cards and finally the South gets 13 cards. We can apply
Theorem 2.5.9 to solve this.
In this case we have
\(n = 52\) items, the cards, and four "types" of items, West’s cards, North’s cards, East’s cards, and South’s cards, each with multiplicity 13. To see how we can use the
Theorem 2.5.9 to solve this: apply some ordering to the entire deck of cards, say the Ace of Hearts is first, the Two of Hearts is second, and so on, for all 52 cards. Then the cards dealt to West correspond to choosing positions for 13 cards (of type West’s cards), the cards dealt to North correspond to choosing positions for 13 cards of type North’s cards, and so on.
\begin{equation*}
\binom{52}{13}\binom{39}{13}\binom{26}{13}\binom{13}{13} = \frac{52!}{13!*13!*13!* 13!}
\end{equation*}
