Combinatorics path · C05

Before this lesson: Combinations and binomial coefficients, Counting with bijections

Your goal: Count repeated selections with clearly stated object and box types.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Names you may know: multisets; stars-and-bars method.

Combinations with Repetition: Stars and Bars: the key idea

Choosing k objects from n types with repetition allowed is equivalent to choosing nonnegative counts x₁+⋯+xₙ=k. Place k identical stars and n−1 separators in a line; the stars between separators record each count. This gives C(k+n−1,n−1) multisets for n≥1,k≥0. Zero counts are allowed, so separators may be adjacent or at the ends. If every type is required, subtract one from each count first. Upper bounds require additional casework or inclusion–exclusion.

A worked example

How many ways can four scoops be chosen from three flavours if only the number of each flavour matters?

The counts x+y+z=4 are nonnegative. Four stars and two bars occupy six positions, so there are C(6,2)=15 choices. Scoop order is irrelevant.

Your turn: change one thing

How many choices use every flavour?

Try this on paper before opening the explanation.

Compare your reasoning

Write x=1+u,y=1+v,z=1+w. Then u+v+w=1 with nonnegative counts, giving C(3,2)=3 choices.

Pause and check

A trap to avoid: Confusing indistinguishable objects with distinguishable ones.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove stars and bars counts nonnegative solutions to x₁+⋯+xₙ=k.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Map a solution to x₁ stars, a bar, x₂ stars, and so on through xₙ stars. There are k stars and n−1 bars. Conversely, any such string recovers the counts between successive bars, including zeros. This reversible map gives C(k+n−1,n−1).

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. Choosing a multiset ignores what?

Foundation

  1. The order of the chosen objects
  2. The count of each type
  3. Whether repetition occurs
  4. The total size
Hint

Only multiplicities matter.

Answer and reasoning

The order of the chosen objects. Two orders with the same type counts represent the same multiset.

2. Adjacent bars in stars and bars represent what?

Foundation

  1. A zero count
  2. An invalid object
  3. Two extra stars
  4. A negative count
Hint

There are no stars between them.

Answer and reasoning

A zero count. The corresponding type is chosen zero times.

3. Four scoops from three flavours, order ignored and repetition allowed: how many?

Core

  1. 24
  2. 15
  3. 12
  4. 81
Hint

Choose two bar positions among six.

Answer and reasoning

15. C(6,2)=15.

4. How many of those choices use all three flavours?

Core

  1. 3
  2. 6
  3. 9
  4. 15
Hint

Reserve one scoop of each flavour.

Answer and reasoning

3. One remaining scoop can use any of the three flavours.

5. How is a lower bound xᵢ≥cᵢ removed?

Stretch

  1. Set yᵢ=xᵢ+cᵢ
  2. Ignore it
  3. Multiply xᵢ by cᵢ
  4. Set yᵢ=xᵢ−cᵢ
Hint

Subtract the required minimum.

Answer and reasoning

Set yᵢ=xᵢ−cᵢ. Then yᵢ≥0 and the required total decreases by ∑ci\sum c_{i}.

6. Can unrestricted stars and bars directly enforce upper bounds?

Stretch

  1. Only when n is prime
  2. Upper bounds never matter
  3. No, extra restrictions must be counted
  4. Yes always
Hint

The basic encoding permits arbitrary nonnegative block lengths.

Answer and reasoning

No, extra restrictions must be counted. Capacity restrictions require removing or separately counting forbidden lengths.

7. Stars represent what in the standard stars-and-bars model?

Foundation

  1. Identical chosen objects
  2. Distinct recipients
  3. Only negative values
  4. Mandatory nonempty boxes
Hint

Bars separate the type counts.

Answer and reasoning

Identical chosen objects. Each star contributes one unit to an occupancy count.

8. Choose three items from two types with repetition, order ignored. Count?

Core

  1. 3
  2. 4
  3. 8
  4. 6
Hint

List counts x+y=3.

Answer and reasoning

4. The pairs are (0,3),(1,2),(2,1),(3,0).

9. Why are end bars allowed for nonnegative counts?

Stretch

  1. They double the total
  2. The first or last type may have count zero
  3. They create new types
  4. They are always forbidden
Hint

A bar at an end borders no stars on that side.

Answer and reasoning

The first or last type may have count zero. It correctly represents a zero endpoint count.

Choose your next step

Continue to Permutations and arrangements. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.