Sign in to watch this lesson
Algorithms - Recursion, Backtracking and Combinatorics · 4:08
Stars and Bars
How many ways can 10 identical shares be split across 4 desks? Lay the shares out as stars and cut the row with bars: every arrangement is one split, so the count is a binomial, C(n+k-1, k-1) (56 for 5 shares and 4 desks, 286 for 10 and 4). We extend it to equations, to boxes that must be non-empty (bars only in the gaps, C(n-1, k-1)), to minimums per box (hand them out first), and to disguises like non-decreasing sequences and three identical dice, whose 56 outcomes are not equally likely.
You will learn
- Count distributions of n identical items into k labelled boxes as C(n+k-1, k-1) with the stars-and-bars bijection
- Count positive solutions with C(n-1, k-1) and handle lower bounds by substitution, returning 0 when they exceed n
- Recognise stars and bars in disguise: non-negative equations, non-decreasing sequences, multisets, identical dice
- Avoid the traps: unlabelled boxes (partitions), negative remainders, and factorial tables that are too small