(related to Proposition: Closed Formula For Binomial Coefficients)
We have to show that the closed formula for the binomial coefficient. \[\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 2\cdot 1}\] can be interpreted as the number of subsets with exactly \(k\) elements of a given finite set \(X\) with exactly \(n\) elements \((|X|=n)\).
We enumerate each element of \(X\) and get an index set \(I=\{1,2,\cdots n\}\). Instead of counting the subsets of \(X\) with \(k\) elements, in which the order of elements does not count, we start to count the subsequences of length \(k\), which can be built from \(I\), in which the order of sequence elements does count.
There are \(n\) choices for the first element of the sequence; for each, there are \(n-1\) choices for the second; and so on, until there are \(n - k +1\) choices for the \(k\)-th. This gives the falling factorial power \(n^{\underline{k}}=n(n-1)\cdots(n-k+1)\) of choices for a sequence with \(k\) sequence elements.
Observe that the definition of factorial \(k(k-1)\cdots 2\cdot 1\) gives the number of possibilities, we can arrange a sequence with \(k\) sequence elements. This number of possible orderings of sequences counts each subset exactly \(k!\) times. To get our answer, we simply divide by \(k!\) and get
\[\frac{n^{\underline{k}}}{k!}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 2\cdot 1}=\binom nk.\]
