Stars and bars

This chapter applies to all AMC 8/10/12 test takers.

The stars and bars method is a combinatorics technique for counting how many ways you can distribute identical items into groups, or how many combinations are possible when repetition is allowed.

The idea is simple:

• The items you’re distributing are the stars.
• The dividers that separate groups are the bars.

Once you translate a problem into stars and bars, the counting question becomes:

• “How many different ways can I place the bars among the stars?”

That’s often much easier than counting the distributions directly.

Here’s a simple example. Suppose you have 10 dollars to give to two children. If each child gets at least one dollar, how many ways can you split the money?

Start by laying out 10 identical dollars as 10 stars:

$\ast \ast \ast \ast \ast \ast \ast \ast \ast \ast$

To split the stars into two groups, we use one bar. Stars to the left go to the first child, and stars to the right go to the second:

$\ast \ast \ast \ast \ast |\ast \ast \ast \ast \ast$

That split gives each child 5 dollars. Another valid split is:

$\ast |\ast \ast \ast \ast \ast \ast \ast \ast \ast$

Because each child must get at least one dollar, the bar can’t go at either end. That leaves 9 possible positions for the bar (between adjacent stars), so there are 9 ways to split the money.

Now suppose there are three children. We need two bars to split the 10 stars into three groups. The question is still “How many ways can we place the bars among the stars?”

There are still 9 gaps between stars, and we choose 2 of them for the bars. That’s $9C2$, which equals $36$.

Try this similar AMC question using the same method.

Example: The question below is from 2004 AMC 8

Three friends have a total of $6$ identical pencils, and each one has at least one pencil. In how many ways can this happen?
A. $1$
B. $3$
C. $6$
D. $10$
E. $12$

This method is also useful for counting combinations with repetition. For example, imagine you want a bowl with four scoops of ice cream, and there are three flavors to choose from. You can choose anywhere from zero to four scoops of each flavor. How many different flavor combinations are possible?

In the money example, each star was a dollar, and the bar(s) determined how many dollars each person received. Here:

• Each star is a scoop.
• The bars split the scoops into three groups, one group per flavor.

Start with four stars:

$\ast \ast \ast \ast$

We need two bars to create three flavor groups. Since a flavor is allowed to have zero scoops, bars can go at the edges, and the two bars can even be adjacent.

Here are some valid arrangements:

$\ast |\ast \ast |\ast$

$ ||$

$||\ast \ast \ast \ast$

Now count the total symbols being arranged:

• 4 stars
• 2 bars

That’s 6 total positions. Choosing where the 2 bars go determines the whole arrangement, so the count is $6C2$, which equals $15$.

More complex combinatorial identities will be discussed later in the Advanced topics unit.

Common themes

• This method is most likely necessary when a question a question is about distributing or assigning things among people or bins, when you are selecting a group of items among different categories of things, or when you are choosing n-digit integers when the digits are in ascending or descending order.
• When a problem says “at least 1”, recognize that the arrangement must allow for at least one star to the left and right of each bar.
• Recognize that the stars and bars method cannot be applied to groups of all distinct items or when the order is important. Stars and bars are useful for combinations, not permutations.