Vandermonde's identity, hockey stick, and stars and bars
Some of the neatest proofs in mathematics just count the same thing two different ways.
Set m, n, and k, then slide j to split the committee into j from one group and k-j from the other. The splits add up to C(m+n, k).
Choosing k people from n+m splits into: j from Group A and k-j from Group B, summed over all valid j.
Binomial coefficients satisfy a rich web of identities. The most elegant proofs are combinatorial proofs: rather than manipulating algebra, we show that both sides count the same thing in different ways. This approach often reveals the deeper structure behind the identity.
Vandermonde's identity states: C(m+n, k) = Σ C(m, j) · C(n, k-j). The combinatorial proof: choosing k people from a room of m men and n women can be broken down by how many men (j) versus women (k-j) are selected. Each split contributes C(m, j) · C(n, k-j) ways.
Key insight: Vandermonde's identity is equivalent to the convolution identity for generating functions: (1+x)ᵐ · (1+x)ⁿ = (1+x)ᵐ⁺ⁿ. Each side's xᵏ coefficient gives one side of the identity.
Click cells to trace your own hockey stick: the shaft runs down a diagonal and its sum lands at the blade.
Click a cell to start, then click further down the same diagonal to extend. The bright cell is the "blade" — the sum.
The hockey stick identity says that the sum of entries along a diagonal in Pascal's triangle equals the entry one step further along the adjacent diagonal: C(r, r) + C(r+1, r) + ... + C(n, r) = C(n+1, r+1). In the triangle, the summed entries form the "shaft" and the result is the "blade" of a hockey stick. Click cells to trace your own hockey stick.
Key insight: The hockey stick identity follows by telescoping Pascal's rule: C(n+1, r+1) = C(n, r+1) + C(n, r), and then expanding C(n, r+1) the same way, unwinding down the diagonal until reaching C(r, r) = 1.
Choose how many stars and bins, then step through or autoplay every distribution and its star-and-bar string.
Distributing n identical objects into k bins is equivalent to placing k-1 bars among n+k-1 positions: C(n+k-1, k-1).
How many ways can n identical objects be distributed among k distinct bins? The stars and bars method encodes each distribution as a binary string of n stars (objects) and k-1 bars (dividers). The number of such strings is C(n+k-1, k-1). This elegant technique reduces distribution problems to counting combinations.
Key insight: Stars and bars gives a bijection between distributions and binary strings. The formula C(n+k-1, k-1) counts the positions for the k-1 bars among n+k-1 total symbols. This also counts multisets of size n from a k-element set.
Spot a mistake or have an idea?