Investigate!10
Suppose you have some number of identical Rubik's cubes to distribute to your friends. Imagine you start with a single row of the cubes.
-
Find the number of different ways you can distribute the cubes provided:
You have 3 cubes to give to 2 people.
You have 4 cubes to give to 2 people.
You have 5 cubes to give to 2 people.
You have 3 cubes to give to 3 people.
You have 4 cubes to give to 3 people.
You have 5 cubes to give to 3 people.
Make a conjecture about how many different ways you could distribute 7 cubes to 4 people. Explain.
What if each person were required to get at least one cube? How would your answers change?
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.
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.
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*}
which 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 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*}
\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 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*}
\mbox{AAABCDD} .
\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.
Now think about how you could specify such an outcome. 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 stars and bars charts there are. But a stars and bars chart is just a string of symbols, some stars and some bars. If instead of stars and bars we would use 0's and 1's, it would just be a bit string. We know how to count those.
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 cookies 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}\mbox{ ways to distribute 7 cookies to 4 kids.}
\end{equation*}
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 stars and bars charts? The charts must start and end with at least one star (so that kids A and D) get cookies, and also no two bars can be adjacent (so that kids B and C are not skipped). One way to assure this is to only place bars in the spaces between the stars. With 7 stars, there are 6 spots between the stars, 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 stars and 3 bars 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.
Stars and bars can be used in counting problems other than kids and cookies. Here are a few examples:
Example1.5.1
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.
SolutionWe 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}.
\end{equation*}
Example1.5.2
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.
SolutionWe 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*}
Example1.5.3
How many integer solutions are there to the equation
\begin{equation*}
x_1 + x_2 + x_3 + x_4 + x_5 = 13.
\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{?}\)
SolutionThis 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.
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}.
\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).
SubsectionExercises
¶1
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.
How many sets of size 5 can be made using the 10 numeric digits 0 through 9?
How many multisets of size 5 can be made using the 10 numeric digits 0 through 9?
Solution
- \({10\choose 5}\) sets. We must select 5 of the 10 digits to put in the set.
Use stars and bars: each star represents one of the 5 elements of the set, each bar represents a switch between digits. So there are 5 stars and 9 bars, giving us \({14 \choose 9}\) sets.
2
Each of the counting problems below can be solved with stars and bars. For each, say what outcome the diagram
\begin{equation*}
***|*||**|
\end{equation*}
represents, if there are the correct number of stars and bars for the problem. Otherwise, say why the diagram does not represent any outcome, and what a correct diagram would look like.
How many ways are there to select a handful of 6 jellybeans from a jar that contains 5 different flavors?
How many ways can you distribute 5 identical lollipops to 6 kids?
How many 6-letter words can you make using the 5 vowels?
How many solutions are there to the equation \(x_1 + x_2 + x_3 + x_4 = 6\text{.}\)
Solution
You take 3 strawberry, 1 lime, 0 licorice, 2 blueberry and 0 bubblegum.
-
This is backwards. We don't want the stars to represent the kids because the kids are not identical, but the stars are. Instead we should use 5 stars (for the lollipops) and use 5 bars to switch between the 6 kids. For example,
\begin{equation*}
**||***|||
\end{equation*}
would represent the outcome with the first kid getting 2 lollipops, the third kid getting 3, and the rest of the kids getting none.
This is the word AAAEOO.
-
This doesn't represent a solution. Each star should represent one of the 6 units that add up to 6, and the bars should switch between the different variables. We have one too many bars. An example of a correct diagram would be
\begin{equation*}
*|**||***,
\end{equation*}
representing that \(x_1 = 1\text{,}\) \(x_2 = 2\text{,}\) \(x_3 = 0\text{,}\) and \(x_4 = 3\text{.}\)
3
After gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins.
How many ways can you do this if there are no restrictions?
How many ways can you do this if each bin must contain at least one dodgeball?
Solution
- \({18 \choose 4}\) ways. Each outcome can be represented by a sequence of 14 stars and 4 bars.
- \({13 \choose 4}\) ways. First put one ball in each bin. This leaves 9 stars and 4 bars.
4
How many integer solutions are there to the equation \(x + y + z = 8\) for which
- \(x\text{,}\) \(y\text{,}\) and \(z\) are all positive?
- \(x\text{,}\) \(y\text{,}\) and \(z\) are all non-negative?
- \(x\text{,}\) \(y\text{,}\) and \(z\) are all greater than \(-3\text{.}\)
Solution
- \({7 \choose 2}\) solutions. After each variable gets 1 star for free, we are left with 5 stars and 2 bars.
- \({10 \choose 2}\) solutions. We have 8 stars and 2 bars.
- \({19 \choose 2}\) solutions. This problem is equivalent to finding the number of solutions to \(x' + y' + z' = 17\) where \(x'\text{,}\) \(y'\) and \(z'\) are non-negative. (In fact, we really just do a substitution. Let \(x = x'- 3\text{,}\) \(y = y' - 3\) and \(z = z' - 3\)).
5
Using the digits 2 through 8, find the number of different 5-digit numbers such that:
Digits cannot be repeated and must be written in increasing order. For example, 23678 is okay, but 32678 is not.
Digits can be repeated and must be written in non-decreasing order. For example, 24448 is okay, but 24484 is not.
Solution
There are \({7 \choose 5}\) numbers. We simply choose five of the seven digits and once chosen put them in increasing order.
This requires stars and bars. Use a star to represent each of the 5 digits in the number, and use their position relative to the bars to say what numeral fills that spot. So we will have 5 stars and 6 bars, giving \({11 \choose 6}\) numbers.
6
When playing Yahtzee, you roll five regular 6-sided dice. How many different outcomes are possible from a single roll? The order of the dice does not matter.
7
Your friend tells you she has 7 coins in her hand (just pennies, nickels, dimes and quarters). If you guess how many of each kind of coin she has, she will give them to you. If you guess randomly, what is the probability that you will be correct?
8
How many integer solutions to \(x_1 + x_2 + x_3 + x_4 = 25\) are there for which \(x_1 \ge 1\text{,}\) \(x_2 \ge 2\text{,}\) \(x_3 \ge 3\) and \(x_4 \ge 4\text{?}\)
9
Solve the three counting problems below. Then say why it makes sense that they all have the same answer. That is, say how you can interpret them as each other.
How many ways are there to distribute 8 cookies to 3 kids?
How many solutions in non-negative integers are there to \(x+y+z = 8\text{?}\)
How many different packs of 8 crayons can you make using crayons that come in red, blue and yellow?
10
Consider functions \(f:\{1,2,3,4,5\} \to \{0,1,2,\ldots,9\}\text{.}\)
How many of these functions are strictly increasing? Explain. (A function is strictly increasing provided if \(a \lt b\text{,}\) then \(f(a) \lt f(b)\text{.}\))
How many of the functions are non-decreasing? Explain. (A function is non-decreasing provided if \(a \lt b\text{,}\) then \(f(a) \le f(b)\text{.}\))
11
Conic, your favorite math themed fast food drive-in offers 20 flavors which can be added to your soda. You have enough money to buy a large soda with 4 added flavors. How many different soda concoctions can you order if:
You refuse to use any of the flavors more than once?
You refuse repeats but care about the order the flavors are added?
You allow yourself multiple shots of the same flavor?
You allow yourself multiple shots, and care about the order the flavors are added?
Solution
- \({20 \choose 4}\) sodas (order does not matter and repeats are not allowed).
- \(P(20, 4) = 20\cdot 19\cdot 18 \cdot 17\) sodas (order matters and repeats are not allowed).
- \({23 \choose 19}\) sodas (order does not matter and repeats are allowed; 4 stars and 19 bars).
- \(20^4\) sodas (order matters and repeats are allowed; 20 choices 4 times).
