Advanced Counting

Beyond basic permutations and combinations, a few patterns recur in interview problems and are worth memorizing.

Stars and bars counts the number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_k = n$:

Place $n$ identical "stars" and $k - 1$ "bars" in a row; the $k$ groups separated by bars give the values of the $x_i$.

Catalan numbers $C_n = \frac{1}{n+1}\binom{2n}{n}$ count an astonishing variety of structures: balanced parentheses with $n$ pairs, monotonic lattice paths that don't cross the diagonal, binary trees with $n$ internal nodes, and triangulations of a convex polygon. If a counting problem feels like it should be $\binom{2n}{n}$ but is mysteriously about half that, try Catalan.

Many counting problems factor cleanly into recurrences. Count by conditioning on the last move, the smallest element, or any natural structural choice. The classic example is the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ for tilings of a $2 \times n$ board or for binary strings with no two consecutive 1s.

Inclusion–exclusion generalizes the union formula to any number of overlapping sets: alternating sum of intersections of all sizes. Use it whenever a "none of these" or "at least one" question doesn't reduce neatly to independence.