Stars and Bars

Math for CS · Axiom Academy

Distributing identical objects into distinct bins Stars and bars is a technique for counting ways to distribute n identical objects into k distinct bins. The insight: represent objects as stars and use bars to separate them into groups. Each arrangement of n stars and k-1 bars represents one distribution. The number of stars between consecutive bars (or before the first/after the last) gives the count for each bin. Why: We have n + k - 1 total symbols ( n stars and k - 1 bars). We need to choose which k - 1 positions are bars (the rest are stars). That's a combination. Stars and bars is equivalent to counting non-negative integer solutions to an equation. What if every bin must have at least one object? Use a change of variable. Why: Set y_i = x_i - 1 so each y_i 0 . Then y_1 + y_2 + + y_k = n - k , and we apply the standard formula: k - 1 = k-1 . When variables have upper bounds (e.g., x_i c ), stars and bars alone isn't enough. Combine it with inclusion-exclusion. Let A_i = solutions where x_i 6 . Set y_i = x_i - 6 , get 2 = 15 solutions per set |A_i A_j| : need x_i 6 and x_j 6 , leaving x_1+x_2+x_3 = 10 - 12 = -2 , which is impossible (0 solutions) By inclusion-exclusion: 66 - 3(15) + 0 = 66 - 45 = 21

This is the written version of the interactive lesson above. See the full Math for CS course.