Stars and Bars Method

Combinatorics · Axiom Academy

Learn how to count distributions of identical objects into distinct bins using a powerful visual technique We want to count the number of ways to distribute n identical objects into k distinct bins . For example: How many ways can we distribute 5 identical candies to 3 children? 2. Visual Representation with Stars and Bars We represent each object as a star () and use bars (|) as dividers between bins. Notice that we need k-1 bars to create k bins. The bars divide our sequence into k sections, each section representing one bin. The key insight: we have n stars and k-1 bars to arrange, giving us a total of n + k - 1 positions. We need to choose which positions will hold bars (or equivalently, which positions will hold stars). This is a combinations problem! We can choose k-1 positions for the bars out of n+k-1 total positions, or equivalently, choose n positions for the stars . Let's solve our original problem: 5 identical candies to 3 children. Given: n = 5 (candies), k = 3 (children) The basic stars and bars method has several important variations for different constraints:

This is the written version of the interactive lesson above. See the full Combinatorics course.