Proof of binomial coefficient formula.

Well, let's first make sequences (ordered lists of distinct elements) of length $k$ from the $n$ element set.There are $n$ ways of picking the first element, $n-1$ ways of picking the second, ..., $n-k+1$ ways of picking the $k$th element. So there are $$n(n-1)\cdots (n-k+1) = \frac{n!}{(n-k)!}$$ such sequences.

But we want to count unordered lists, i.e., for each sequence, we want to identify the $k!$ permutations of its elements (each of which was counted separately above) as the same list. Hence the number of unordered lists is $$\frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!(n-k)!}.$$

Notice that given $n$ objects $\{a_i\}$ and $n$ positions, there are $n$ possible positions for $a_n$. Once we have placed $a_n$, there are $n-1$ remaining positions for $a_{n-1}$. Once we have placed $a_n$ and $a_{n-1}$, there are $n-2$ positions left for $a_{n-2}$, and so forth. Thus, there are $$ n(n-1)(n-2)\cdots3\cdot2\cdot1=n! $$ possible ways to arrange the $n$ items.

Suppose we divide the $n$ items into $k$ white objects and $n-k$ black objects. For each arrangement of the white and black objects that looks the same, there are $k!$ rearrangements of the white objects and $(n-k)!$ rearrangements of the black objects. Since there are $n!$ rearrangements of the $n$ objects, there must be $$ \frac{n!}{k!(n-k)!}=\binom{n}{k} $$ arrangements of the $k$ white and $n-k$ black objects that look different.

Perhaps it will help you go over the permutation formula first $\frac {n!}{\left( n-k \right)!}$ and then thinking about the adaptation we need if we are to disregard order. It is easier this way.

First, for $k\leq n$ we must construct a $k$-permutation from an $n$-element set. We can choose the first item in $n$ ways, the second item in $n-1$ ways, whatever the choice of the first item,..., and the $k$th item in $n-(k-1)$ ways, whatever the choice of the first $k-1$ items. By the Multiplication Principle the $k$ items can be chosen in $n(n-1)\cdots (n-k+1)$ ways. We can rewrite this as $${n(n-1)\cdots (n-k+1)(n-k)!\over (n-k)!}={n!\over (n-k)!}.$$ Thus $P(n,k)={n!\over (n-k)!}$. By a $k$-permutation from a set $S$ of $n$ elements, we have an ordered arrangement of $k$ of the $n$ elements. Since we are concerned with the number of ways we can choose $k$ of the $n$ elements we want the number of unordered arrangements (subsets). Since each arrangement has length $k$ we can permute them in $k!$ ways. So the number of unordered arrangements of the elements of S is ${n!\over k!(n-k)!}$. Thus for $k\leq n$ $$C(n,k)={n!\over k!(n-k)!}.$$