2.5 Stars and Bars

Investigate!

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:
1. You have 3 cubes to give to 2 people.
2. You have 4 cubes to give to 2 people.
3. You have 5 cubes to give to 2 people.
4. You have 3 cubes to give to 3 people.
5. You have 4 cubes to give to 3 people.
6. 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 to the power 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 to the power 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:

$3112$

, 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 to the power 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:

$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 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 to the power 7$ , because here order does not matter. In fact, another way to write the same outcome is

$AAABCDD$

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:

$∗ ∗ ∗ vertical bar ∗ vertical bar ∗ vertical bar ∗ ∗$

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:

$vertical bar ∗ ∗ ∗ vertical bar vertical bar ∗ ∗ ∗ ∗$

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:

$∗ ∗ ∗ ∗ ∗ ∗ vertical bar ∗ vertical bar vertical bar$

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:

$There are (\binom{10}{3}) ways to distribute 7 cookies to 4 kids$

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 place bars only 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 $(\binom{6}{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 $(\binom{6}{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 1

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.

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 stars), 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 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 the number of milkshakes possible is

$(\binom{15}{9})$

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

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 to the next smaller one. So the phone number 866-5221 is represented by the stars and bars chart

$vertical bar ∗ vertical bar vertical bar ∗ ∗ vertical bar ∗ vertical bar vertical bar vertical bar ∗ ∗ vertical bar ∗ vertical bar$

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

$(\binom{16}{9})$

Example 3

How many integer solutions are there to the equation

$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 13$

(An integer solution to an equation is a solution in which the unknown must have an integer value.)

where $x sub i greater than or equal to 0$ for each $x_{i}$ ?
where $x sub i greater than 0$ for each $x_{i}$ ?
where $x sub i greater than or equal to 2$ for each $x_{i}$ ?

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 $(\binom{17}{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 $(\binom{12}{4})$ .
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 $(\binom{7}{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 $(\binom{10}{7}) = 120$ , while the number of functions $f: open brace 1, 2, 3, 4, 5, 6, 7 close brace → open brace a, b, c, d close brace$ is $4^{7} = 16384$ . What is going on here?

When we count functions, we consider the following two functions, for example, to be different:

$f = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ a & b & c & c & c & c & c \end{matrix}) g = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ b & a & c & c & c & c & c \end{matrix})$

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

Each of the counting problems below can be solved with stars and bars. For each, say what outcome the diagram

$∗ ∗ ∗ vertical bar ∗ vertical bar vertical bar ∗ ∗ vertical bar$

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 in alphabetical order?
How many solutions are there to the equation $x_{1} + x_{2} + x_{3} + x_{4} = 6$ .

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,
$∗ ∗ vertical bar vertical bar ∗ ∗ ∗ vertical bar vertical bar vertical bar$
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
$∗ vertical bar ∗ ∗ vertical bar vertical bar ∗ ∗ ∗$
, representing that $x sub 1 equals 1$ , $x sub 2 equals 2$ , $x sub 3 equals 0$ , and $x sub 4 equals 3$ .

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$ ?
How many different packs of 8 crayons can you make using crayons that come in red, blue and yellow?

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.