# Proof

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.$

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Graham L. Ronald, Knuth E. Donald, Patashnik Oren: "Concrete Mathematics", Addison-Wesley, 1994, 2nd Edition