Skip to content
Mastering
AMC 8
Combinatorics · Chapter 8

Stars and Bars

Share identical things among different people by lining them up as stars and dropping in bars.

What's this chapter about?
You'll need
open on YouTube
8.10%

Stars and Bars Fundamentals

In this section you will be able to share identical objects among different people by placing bars between stars.

A teacher has 8 identical computers to share with 3 students. One student might get 5, another 2, another 1. Or one student gets all 8! How many different ways are there?

The computers all look the same. So only how many each student gets matters, not which computer.

Line the computers up as stars and drop in bars to split them. Everything left of the first bar goes to student 1, and so on. Each way of placing the bars is one way to share.

Exploreplay first, formulas later

8 computers into 3 students: C(10, 2) = 45 layouts

computers8
students3
  • student 1
    2
  • student 2
    5
  • student 3
    1
45 layouts

CC|CCCCC|C gives student 1: 2, student 2: 5, student 3: 1. 45 layouts in all.

Name it

Theorem 8.1.1 · Stars and Bars

The number of ways to place nn indistinguishable objects into kk distinguishable bins is

(n+k−1n).\binom{n+k-1}{n}.

Remark 8.1.3

Make sure to remember: Stars and Bars only works if the objects being distributed are identical!

Watch itpredict, then reveal

Example 8.1

How many ways are there to distribute 8 identical computers amongst 3 students?

8 computers into 3 students: C(10, 2) = 45 layouts

computers8
students3
  • student 1
    2
  • student 2
    5
  • student 3
    1
45 layouts

CC|CCCCC|C gives student 1: 2, student 2: 5, student 3: 1. 45 layouts in all.

  1. 1

    If the computers were not identical, how many ways would there be?

    Predict first:

Example 8.2

How many ways are there to distribute 8 identical pencils amongst 3 people?

8 pencils into 3 people: C(10, 2) = 45 layouts

pencils8
people3
  • person 1
    3
  • person 2
    3
  • person 3
    2
45 layouts

✎✎✎|✎✎✎|✎✎ gives person 1: 3, person 2: 3, person 3: 2. 45 layouts in all.

  1. 1

    Are the pencils identical or different?

    Predict first:
open on YouTube

Try it

Problem 8.3.1

How many ways are there to distribute 5 identical candies to 3 children?

Problem 8.3.6(additional)

How many positive 5 digit integers exist such that each digit is greater than or equal to the previous digit?

Contest cornerreal contest problems

Problem 8.3.3

AMC 10

Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?

Checkpoint for section 8.1

Get 2 of 3 right to master this section. One try each, no hints.
1

In how many ways can you put 4 identical balls into 3 different boxes? Boxes may be empty.

2

How many solutions in non-negative integers does x+y+z+w=5x + y + z + w = 5 have?

3

How many positive 5 digit integers exist such that each digit is greater than or equal to the previous digit?

8.20%

Stars and Bars with Constraints

In this section you will be able to handle rules like at least 1 each, at most 5 each, or less than 13 by changing the problem into plain stars and bars.

Seven astronauts are stuck in space with 10 identical meals. Every astronaut needs at least 1 meal. Plain stars and bars would let someone get 0. How do you stop that?

The trick: hand out the minimum first. Give each astronaut 1 meal. Now the leftover meals can go anywhere, and plain stars and bars counts them.

Other rules bend the same way. An upper limit? Count everything, then subtract the layouts that break it. A “less than” sign? Add an extra variable that soaks up what is left over.

Exploreplay first, formulas later

Give 7 meals first, 3 left for 7 astronauts: C(9, 6) = 84 ways

meals10
astronauts7
Still to hand out
  • astronaut 1 (at least 1)
    0
  • astronaut 2 (at least 1)
    0
  • astronaut 3 (at least 1)
    0
  • astronaut 4 (at least 1)
    0
  • astronaut 5 (at least 1)
    0
  • astronaut 6 (at least 1)
    0
  • astronaut 7 (at least 1)
    0
First hand out 7then 3 meals go anywhere

10 meals, 7 astronauts. Press "Give one to each".

Name it

Concept 8.2.1 · Give One First

Stars and bars is extremely useful and can often be adapted to the situation. For example, if each bin has to have at least 1 object in it, give each bin 1 object to start with. Then apply the formula with n−kn-k objects and kk distinguishable bins:

((n−k)+k−1k−1)=(n−1k−1).\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}.

Watch itpredict, then reveal

Example 8.3

7 astronauts are stranded in space with only 10 identical meals left. Every astronaut must receive at least 1 meal or else, they will starve. How many ways are there to distribute meals under this constraint?

Give 7 meals first, 3 left for 7 astronauts: C(9, 6) = 84 ways

meals10
astronauts7
Still to hand out
  • astronaut 1 (at least 1)
    0
  • astronaut 2 (at least 1)
    0
  • astronaut 3 (at least 1)
    0
  • astronaut 4 (at least 1)
    0
  • astronaut 5 (at least 1)
    0
  • astronaut 6 (at least 1)
    0
  • astronaut 7 (at least 1)
    0
First hand out 7then 3 meals go anywhere

10 meals, 7 astronauts. Press "Give one to each".

  1. 1

    How can we deal with the condition that every astronaut must get at least 1 meal? After that, how many meals are left?

    Predict first:

Example 8.4

What's the probability that the sum of the top faces on five regular 6-sided dice is 24?

6 minus-ones into 5 dice: C(10, 4) = 210 layouts; at most 5 each: 210 − 5 = 205

  • die 1
    2
    shows 4
  • die 2
    1
    shows 5
  • die 3
    1
    shows 5
  • die 4
    1
    shows 5
  • die 5
    1
    shows 5
210 layouts5 break the limit of 5, so 205 are allowed

−1−1|−1|−1|−1|−1 gives die 1: 2, die 2: 1, die 3: 1, die 4: 1, die 5: 1. 210 layouts in all, 205 within the limit.

  1. 1

    How can we use stars and bars for this problem?

    Predict first:

Example 8.5

How many ways are there to choose positive integers aa, bb, cc, and dd such that a+b+c+d<13a + b + c + d < 13?

Give 4 ones first, 8 left for 5 variables: C(12, 4) = 495 ways

ones12
variables5
Still to hand out
  • a (at least 1)
    0
  • b (at least 1)
    0
  • c (at least 1)
    0
  • d (at least 1)
    0
  • extra e (at least 0)
    0
First hand out 4then 8 ones go anywhere

12 ones, 5 variables. Press "Give the minimums first".

  1. 1

    The sum is a whole number less than 13. What is the biggest it can be?

    Predict first:
open on YouTube

Example 8.6

How many ways are there for 7 people to sit in a line if 3 of them are enemies and refuse to sit next to each other?

Give 2 friendly people first, 2 left for 4 gaps: C(5, 3) = 10 ways

Still to hand out
  • w: left end (at least 0)
    0
  • x: gap 1 (at least 1)
    0
  • y: gap 2 (at least 1)
    0
  • z: right end (at least 0)
    0
First hand out 2then 2 friendly people go anywhere

4 friendly people, 4 gaps. Press "Give the minimums first".

  1. 1

    We'll worry about the order of the people later. Without the condition, how many ways are there to choose 3 seats for the enemies?

    Predict first:

Example 8.7

Omega Learn

You have 11 apples and 5 bananas. You place them into 3 baskets. How many ways are there to do this if each basket must have more apples than bananas and at least 1 of any fruit?

Give 8 apples first, 3 left for 3 baskets: C(5, 2) = 10 ways

Still to hand out
  • basket 1 (2 bananas) (at least 3)
    0
  • basket 2 (2 bananas) (at least 3)
    0
  • basket 3 (1 banana) (at least 2)
    0
First hand out 8then 3 apples go anywhere

11 apples, 3 baskets. Press "Give the minimums first".

  1. 1

    Each basket has more apples than bananas. Can a basket end up with no fruit at all?

    Predict first:
open on YouTube

Try it

Problem 8.3.7(additional)

Omega Learn

Find the number of solutions to a+b+c+d<19a + b + c + d < 19 where a,b,c,da, b, c, d are positive integers, aa and cc must be odd, and bb and dd must be even.

Contest cornerreal contest problems

Problem 8.3.4

AMC 8

Alice has 24 apples. In how many ways can she share them with Becky and Chris so that each of the three people has at least two apples?

Problem 8.3.2

AMC 10

When 7 fair standard 6-sided dice are thrown, the probability that the sum of the numbers on the top faces is 10 can be written as

n67,\frac{n}{6^7},

where nn is a positive integer. What is nn?

Checkpoint for section 8.2

Get 2 of 3 right to master this section. One try each, no hints.
1

In how many ways can you give 6 identical candies to 3 children if every child gets at least 1?

2

In how many ways can you give 12 identical stickers to 4 kids if every kid gets at least 2?

3

How many solutions in positive integers does a+b+c≤6a + b + c \le 6 have?

8.3

Practice Problems

In this section you will be able to mix every stars and bars trick on contest problems.

Time to mix it all up! These problems need stars and bars plus a twist, like odd and even numbers. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 8.3.5

Omega Learn Math Contest

Three squirrels have to distribute 19 identical acorns amongst themselves.

  • The first squirrel demands to have a positive odd number of acorns.
  • The second squirrel is fine with any non-negative even number of acorns.
  • The third squirrel insists he must get an even number of acorns greater than or equal to 4.

How many different ways can they distribute the acorns?