Nested-subset binomial identity
= Nested-subset binomial identity
{title2=$\binom nk\binom k\ell=\binom n\ell\binom{n-\ell}{k-\ell}$}
For $0\le\ell\le k\le n$, count pairs of <subsets> $L\subseteq K\subseteq X$ with $|X|=n$, $|L|=\ell$ and $|K|=k$. Choosing $K$ before $L$ gives the left product of <binomial coefficients>. Choosing $L$ and then the $k-\ell$ additional elements of $K$ gives the right product. This <double counting> proof explains the identity without division by factorials.