Discrete Math · Undergraduate
Stars and Bars: Combinations with Repetition
Quick answer
Sharing n identical objects among k people, or counting nonnegative integer solutions of x₁ + … + xₖ = n, is the same as arranging n stars and k − 1 bars in a row. The bars split the stars into k groups, so the count is C(n + k − 1, k − 1). If every group must get at least one, hand one to each first and count the rest, giving C(n − 1, k − 1). The same count gives the number of ways to choose n items from k types when repeats are allowed and order does not matter.
What you'll learn
- Model a distribution problem with stars and bars
- Count nonnegative integer solutions of x₁ + … + xₖ = n
- Handle lower bounds by giving out the minimum first
- Count selections with repetition
Stars for objects, bars for walls
To share identical candies among kids, line up stars and bars. The bars cut the row into groups, read left to right:
Every way of placing the bars is one sharing, and every sharing is one placement. With objects and groups, there are symbols and we choose where the bars go:
If each group must get at least one, the count is .
Why the bars capture every case
A sharing is fully described by how many objects each group gets. In the row, the stars before the first bar are group ‘s, the stars between the bars are group ‘s, and so on. Two bars side by side mean an empty group. Reading the row gives the sharing, and writing the sharing as stars and bars gives the row, so the two are counted by the same number. Counting rows is a combination: choose of the spots for bars.
Worked examples
Common mistakes
Practice problems
-
In how many ways can identical balls go into boxes?
Answer
Full solution
.
-
In how many ways can identical cookies go to kids?
Answer
Full solution
.
-
In how many ways can identical cookies go to kids if each gets at least one?
Answer
Full solution
.
-
Count the nonnegative integer solutions of .
Answer
Full solution
.
-
Count the positive integer solutions of .
Answer
Full solution
.
-
A shop sells flavors of donut. In how many ways can you pick donuts, with repeats allowed?
Answer
Full solution
, : .
-
Count the integer solutions of with each variable at least .
Answer
Full solution
Set and so on: , so .
-
A student counts the ways to put identical balls into boxes as . What is the correct count?
Answer
Full solution
The balls are identical, so only the split matters: , the splits through .
Frequently asked questions
What is the stars and bars formula?
The number of ways to put n identical objects into k groups is C(n + k − 1, k − 1).
What if every group must get at least one?
Give one to each group first, leaving n − k objects. The count becomes C(n − 1, k − 1).
How does it count combinations with repetition?
Choosing n items from k types with repeats allowed is the same as deciding how many of each type, so the count is C(n + k − 1, k − 1).
Does it work for different objects?
No. Stars and bars needs identical objects. With different objects, each one picks a group, giving kⁿ ways.