Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Permutations and Combinations

Stars and Bars (Combinations with Repetition)

Count ways to distribute identical items into boxes and choose with repetition using the stars and bars method, with lower bounds and Python verification.

How many ways can you hand out 10 identical candies to 4 children? Or choose 5 scoops of ice cream from 3 flavours when you may repeat a flavour? These are combinations with repetition, and the answer comes from a neat picture called stars and bars.

The picture

Write each candy as a star *. To split them among 4 children, place 3 bars | between stars to mark the boundaries between children. Example for 10 candies:

**|***||***** means child 1 gets 2, child 2 gets 3, child 3 gets 0, child 4 gets 5.

Every distribution corresponds to exactly one string of 10 stars and 3 bars, and every such string is one distribution. That is a bijection. The strings have length 13, and you choose which 3 positions hold bars:

C(10 + 3, 3) = C(13, 3) = 286.

Stars and bars theorem. The number of ways to put n identical items into k distinct boxes (each box may be empty) is C(n + k - 1, k - 1), which also equals C(n + k - 1, n).

Python Stars and bars versus listing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing with repetition

Three flavours, 5 scoops, repeats allowed, order irrelevant. This is distributing 5 identical scoops into 3 flavour boxes: C(5 + 3 - 1, 3 - 1) = C(7, 2) = 21. This is exactly what itertools.combinations_with_replacement generates.

Python combinations_with_replacement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Integer solutions of equations

The number of non-negative integer solutions of x1 + x2 + ... + xk = n is the same count: C(n + k - 1, k - 1). For x + y + z = 10 it is C(12, 2) = 66.

For positive solutions (each variable at least 1), give each box one item first. That uses k items and leaves n - k to distribute freely: C(n - 1, k - 1). For x + y + z = 10 with all positive: C(9, 2) = 36.

For lower bounds like x >= 2, y >= 3, z >= 0 with sum 10, subtract the minimums first: x' + y' + z = 5, so C(7, 2) = 21.

Python Equations with lower bounds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Upper bounds need inclusion-exclusion

Suppose each box can hold at most m items. Stars and bars alone over-counts, and you must subtract the distributions in which some box exceeds the limit. That is a job for inclusion-exclusion, which this course reaches in chapter four. For small sizes you can still brute-force it.

Python At most 3 in each box

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart LR
    I["Identical items"] --> S["Draw stars"]
    S --> B["Insert k-1 bars"]
    B --> R["C(n+k-1, k-1)"]

Choosing the bar positions is a plain combination problem.

Which formula do I need?

Question Order matters? Repeats? Count
strings of length k yes yes n^k
k-permutations yes no n!/(n-k)!
k-subsets no no C(n, k)
k-multisets no yes C(n+k-1, k)

That 2 x 2 table is the full answer to the first two of the four questions from What Is Combinatorics?.

In "k items from n types", the roles of k and n can confuse you. In stars and bars with n items and k boxes, the answer is C(n + k - 1, k - 1). Think "stars plus bars choose bars".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many ways to distribute 7 identical balls into 3 boxes (empty allowed)?

    C(7 + 3 - 1, 2) = C(9, 2) = 36.
  2. 2. How many solutions in positive integers to x + y + z = 9?

    C(9 - 1, 3 - 1) = C(8, 2) = 28.
  3. 3. A bakery has 4 kinds of muffin. How many ways to buy 6 muffins (any mix)?

    C(6 + 4 - 1, 6) = C(9, 6) = 84.
  4. 4. What is the main new difficulty when each box has an upper limit?

    Plain stars and bars ignores the cap, so cases that break it must be removed.

Summary

  • Stars and bars: n identical items in k boxes gives C(n + k - 1, k - 1).
  • It counts k-multisets from n types and non-negative integer solutions.
  • Positive solutions use C(n - 1, k - 1); lower bounds are subtracted first.
  • Upper bounds require inclusion-exclusion.

Next: Inclusion-Exclusion for Two and Three Sets