Proof of binomial coefficient formula.

How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$? This is an accepted fact in every book but i couldn't find a proof.

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)!}.$$

• I understand where the $\frac{n!}{(n-k)!}$ and $k!$ come from I just do not understand logically speaking why you divide the two to switch from ordered to unordered. (+1) – usainlightning Feb 26 '15 at 22:30
• @usainlightning maybe try writing out all the ordered sequences for some small $n$ and $k$ and grouping them by those that have the same numbers. You will see that each group has $k!$ sequences, so dividing by $k!$ is like shrinking each group into one "element" (the set of numbers in the sequences in that group). Not sure if that makes sense – Casteels Feb 27 '15 at 7:02
• @usainlightning another way to think about it: we have (# ordered sequences) = (#groups)(size of each group) where a group is the set of sequences with the same set of numbers. You want to count #groups and you have $\frac{n!}{(n-k)!}=$(# groups)$k!$. – Casteels Feb 27 '15 at 21:01

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)!}.$$

if you have $k$ number of black and $n-k$ white balls what is your change of getting 1 white then 1 black then 1 white... it is $\frac{(n-k)!k!}{n!}$ and if your change of getting $1$ combination is $\frac{(n-k)!k!}{n!}$ how many combinations are there answer is $\frac{n!}{(n-k)!k!}$.this is how i think it but it can be flawed.