Stars and Bars

Section 1.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^{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:

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^{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^{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:

* * * | * | * | * * .

🔗

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:

| * * * | | * * * * .

🔗

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:

* * * * * * | * | | .

🔗

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

🔗

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

🔗

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

| * | | * * | * | | | * * | * | .

🔗

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 1.5.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_{i} \geq 0$ for each $x_{i} ?$
🔗

🔗
where $x_{i} > 0$ for each $x_{i} ?$
🔗

🔗
where $x_{i} \geq 2$ for each $x_{i} ?$
🔗

🔗

🔗

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 $(\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 : {1, 2, 3, 4, 5, 6, 7} \to {a, b, c, d}

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

🔗

Exercises Exercises

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 7 can be made using the 10 numeric digits 0 through 9?
🔗

🔗
How many multisets of size 7 can be made using the 10 numeric digits 0 through 9?
🔗

🔗

🔗

2.

Using the digits 2 through 8, find the number of different 4-digit numbers such that:

Digits cannot be repeated and must be written in increasing order. (Increasing means strictly increasing. For example, the digits of 134 are increasing, but the digits of 133 are not.)
🔗

🔗
Digits can be repeated and must be written in non-decreasing order. (Now the digits don’t need to be strictly increasing; 133 has digits non-decreasing.)
🔗

🔗

🔗

3.

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

* * * | * | | * * |

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 .$
🔗

🔗

🔗

4.

After gym class you are tasked with putting the 28 identical dodgeballs away into 9 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?
🔗

🔗

🔗

5.

How many integer solutions are there to the equation

x + y + z = 14

for which

$x,$ $y,$ and $z$ are all positive?
🔗

🔗
$x,$ $y,$ and $z$ are all non-negative?
🔗

🔗
$x,$ $y,$ and $z$ are all greater than or equal to $- 3 .$
🔗

🔗

🔗

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.

🔗

When playing Super-Yahtzee, you roll 7 regular 4-sided dice. Now how any different outcomes are possible from a single roll?

🔗

7.

Your friend tells you she has 5 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} = 28

are there for which

x_{1} \geq 3,

x_{2} \geq 4,

x_{3} \geq 5,

and

x_{4} \geq 6 ?

🔗

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 ?$
🔗

🔗
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} \to {0, 1, 2, 3, 4, 5, 6, 7} .

How many of these functions are strictly increasing? Explain. (A function is strictly increasing provided if $a < b,$ then $f (a) < f (b) .$ )
🔗

🔗
How many of the functions are non-decreasing? Explain. (A function is non-decreasing provided if $a < b,$ then $f (a) \leq f (b) .$ )
🔗

🔗

🔗

11.

Conic, your favorite math themed fast food drive-in offers 22 flavors which can be added to your soda. You have enough money to buy a large soda with 6 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 in which the flavors are added?
🔗

🔗
You allow yourself multiple shots of the same flavor?
🔗

🔗
You allow yourself multiple shots, and care about the order in which the flavors are added?
🔗

🔗

🔗

You have attempted 1 of 10 activities on this page.

🔗

Prev Top Next