You are staring at a counting problem. It asks how many ways to distribute ten identical candies among four children. Or maybe it asks for the number of non-negative integer solutions to x + y + z = 7. Your first instinct might be to list every possibility. That works for small numbers, but it falls apart fast. This is where the stars and bars combinatorics technique saves the day. It turns messy distribution problems into a simple combination formula. Once you learn it, you will see it everywhere: in math competitions, in probability homework, even in computer science algorithm analysis.

What Exactly Is Stars and Bars Combinatorics?

The name comes from the visual representation. You draw stars to represent the identical items you are distributing, and bars to represent the dividers between bins. If you have three children, you need two bars to separate them. The stars go in between and around the bars. Every arrangement of stars and bars corresponds to one distribution.

For example, suppose you have 5 stars and 3 bins. That means 2 bars. One possible arrangement is:

** * | * * | * *

This means the first bin gets 2 stars, the second gets 2 stars, and the third gets 1 star. Another arrangement is:

| * * * * * |

This means the first bin gets 0, the second gets 5, and the third gets 0. The bars act as walls. The stars are identical, so only the counts matter, not which star is which.

The Two Core Theorems

You need two versions of the formula. The first handles cases where bins can be empty. The second handles cases where each bin must have at least one item.

Theorem 1: Non-Negative Integer Solutions

The number of ways to distribute n identical items into k distinct bins, allowing empty bins, is:

C(n + k – 1, k – 1)

This is also the number of non-negative integer solutions to x1 + x2 + … + xk = n.

Theorem 2: Positive Integer Solutions

The number of ways to distribute n identical items into k distinct bins, where each bin gets at least one item, is:

C(n – 1, k – 1)

This is the number of positive integer solutions to x1 + x2 + … + xk = n, where each xi >= 1.

When to Use Each Theorem

How to Apply the Method in Three Steps

Follow these steps every time. They prevent the most common mistakes.

1. Identify the items and the bins. Are the items identical? Are the bins distinct? If items are not identical, stars and bars does not apply. If bins are identical, you need a different method (integer partitions). For most competition problems, items are identical and bins are distinct.

2. Check the condition on the bins. Can a bin be empty? Must it have at least one? Does it have a different lower bound? Adjust the total number of items accordingly. If each bin must have at least 2, subtract 2 from each bin first, then use Theorem 1 on the remainder.

3. Apply the correct formula. Use C(n + k – 1, k – 1) for non-negative, or C(n – 1, k – 1) for positive. Then compute the combination.

Common Mistakes and How to Avoid Them

Even experienced students slip up on these points.

• Mistaking distinct for identical bins. If the problem says “three identical boxes,” stars and bars does not apply directly. You would need a different counting method.
• Forgetting to adjust for lower bounds. If each bin must have at least 2, you cannot just plug n and k into Theorem 2. Subtract the mandatory items first.
• Using the wrong formula for non-negative vs positive. This is the most frequent error. Always check whether zero is allowed.

A helpful trick: if the problem says “how many ways to distribute” without specifying “at least one,” assume zero is allowed unless stated otherwise.

Practical Examples from SASMO and Competitions

Let us walk through three problems that show the technique in action.

Example 1: Distributing Cookies

You have 12 identical cookies to give to 5 distinct students. How many ways can you do this?

• Items: 12 cookies (identical). Bins: 5 students (distinct). No restriction on zero. Use Theorem 1.
• n = 12, k = 5. C(12 + 5 – 1, 5 – 1) = C(16, 4) = 1820.

Example 2: Each Student Gets at Least One Cookie

Same cookies, same students, but now each student must get at least one cookie.

• n = 12, k = 5. Use Theorem 2. C(12 – 1, 5 – 1) = C(11, 4) = 330.

Example 3: Lower Bound Greater Than One

You have 20 identical marbles to put into 4 distinct jars. Each jar must contain at least 3 marbles. How many ways?

• Subtract the mandatory marbles: 3 marbles per jar for 4 jars = 12 mandatory marbles. 20 – 12 = 8 remaining marbles.
• Now distribute 8 identical marbles into 4 distinct jars with no restriction (zero allowed). Use Theorem 1.
• n = 8, k = 4. C(8 + 4 – 1, 4 – 1) = C(11, 3) = 165.

The Visual Proof That Makes It Click

Why does the formula work? Imagine you have n stars and k – 1 bars. You are arranging all n + k – 1 symbols in a line. The number of distinct arrangements is the number of ways to choose positions for the stars (or for the bars). That is C(n + k – 1, n) or equivalently C(n + k – 1, k – 1). Each arrangement corresponds to exactly one distribution. This is the core insight.

Expert advice: Draw the stars and bars for small cases. For n = 3 and k = 3, list all C(5, 2) = 10 arrangements. Write down the corresponding distributions. This hands-on practice builds intuition faster than memorizing formulas alone. Once you see the pattern, you will never forget it.

When Stars and Bars Does Not Work

This method has limits. It only works when:

• The items are identical.
• The bins are distinct.
• The order of bins matters (which it does when bins are distinct).

If you have distinct items, use the multiplication principle or permutations. If you have identical bins, you need partition theory, which is more complex. For example, “how many ways to put 5 identical balls into 3 identical boxes” is a partition problem, not a stars and bars problem.

A Handy Reference Table

Building Your Problem-Solving Toolkit

Stars and bars is one piece of the puzzle. To excel in competitions like SASMO, you need a full set of counting tools. If you are preparing for the SASMO exam, you should also master the multiplication principle and the pigeonhole principle. These three techniques cover a large portion of counting problems.

For more practice, check out our guide on combinatorics made simple: counting principles for SASMO success. It walks through other essential methods. You might also find our article on how to tackle SASMO combinatorics problems when you’re completely stuck helpful for building confidence.

Putting It All Together

Stars and bars combinatorics is not a trick. It is a logical transformation of a counting problem into a simpler one. You take a distribution problem, turn it into an arrangement problem, and solve it with a combination. The hardest part is recognizing when to use it. Once you identify the identical items and distinct bins, the rest is formula work.

Practice with these problems:

• How many non-negative integer solutions does x + y + z = 10 have?
• How many positive integer solutions does a + b + c + d = 15 have?
• You have 30 identical stickers to distribute among 6 distinct notebooks. Each notebook must get at least 2 stickers. How many ways?

The answers are 66, 364, and C(30 – 12 + 6 – 1, 6 – 1) = C(23, 5) = 33649. If you got those, you have mastered the technique.

Now go apply this to your next problem set. You will be surprised how often stars and bars shows up. And when it does, you will be ready.