Nested-subset binomial identity
ID: nested-subset-binomial-identity
For , count pairs of subsets with , and . Choosing before gives the left product of binomial coefficients. Choosing and then the additional elements of gives the right product. This double counting proof explains the identity without division by factorials.
New to topics? Read the docs here!