Stars and Bars

This formula counts the number of nonnegative integer solutions to x1 + x2 + ... + xk = n, where each xi is the number of identical items placed in group i. It works by imagining the n items as stars and using k - 1 dividers to split them into k groups; arranging n stars and k - 1 bars in a line gives a unique distribution, and the number of such arrangements is the binomial coefficient shown. Because only the positions of the bars matter, the count is choose n + k - 1 positions from the total n + k - 1 slots, or equivalently choose where the k - 1 separators go.

Use this when you are counting ways to split identical objects among distinct categories, such as assigning candies to children, placing balls into boxes, or distributing identical tasks across teams. It is especially useful in combinatorics, integer partition-style counting, and problems that ask for nonnegative whole-number solutions.

• Using this formula for distinct items instead of identical items
• Forgetting that the groups are distinct, so swapping two groups counts as a different arrangement
• Using k instead of k - 1 in the binomial coefficient