Theorem 1 ( 24.1.1 formula A. II.).
For any and and any with ,
Let and be disjoint sets with and . Then the left-hand side of Equation (*) is equal to the number of subsets of of size . To build a subset of of size , we first decide how many elements, say with , we will select from . We can then select those elements in ways. Once we have done so, we must select the remaining elements from , which we can do in ways. Thus there are ways to select a subset of of size subject to the restriction that exactly elements come from . Summing over all possible completes the proof. ∎
- 1 Abramowitz, M., and I. A. Stegun, eds. Handbook of Mathematical Functions. National Bureau of Standards, Dover, New York, 1974.