Proof of binomial coefficient formula.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

Perhaps it is worth mentioning a method of solution that might appear a bit far-fetched, but which is an excellent introductory example to the theory of generating functions, for which the book generatingfunctionology by Herbert S. Wilf is highly recommended.

Write $\dbinom{n}{k}$ for the number of choosing $k$ objects out of $n$. Consider the polynomial $$ (1 + x_{1}) (1 + x_{2}) \cdots (1 + x_{n}) $$ in the $n$ indeterminates $x_{1}, \dots, x_{n}$. It is easy to convince oneself that this polynomial has exactly $\dbinom{n}{k}$ monomials of degree $k$. If one now sets $x_{1} = \dots = x_{n} = x$, where $x$ is another indeterminate, each such monomial reduces to $x^{k}$, so that one obtains that $$ (1 + x)^{n} = \sum_{k = 0}^{n} \dbinom{n}{k} x^{k}. $$ Now use Taylor's theorem for polynomials to obtain the required formula.

Let me stress that this might look totally overkill in this relatively simple setting. But the method has tremendous potential.

Answer 7

Let $X$ be a nonempty finite set with $n$ elements. For the integer $s$ define

$$ \mathcal{P_s} (X) = \{ A \subset X \mid |A| = s\}$$

and for integer $r$ satisfying $0 \le r \lt n$ define

$$ \mathcal{B_r} (X) = \{ (A, b) \mid A \subset X \; \land \; |A| = r \; \land \; \displaystyle b \in A^{\complement }\}$$

Observe that $|\mathcal{B_r} (X)| =\, _n C _r \times (n-r)$.

Consider the function $\beta:\mathcal{B_r} (X) \to \mathcal{P_{r+1}} (X)$ defined by

$$ (A,b) \mapsto A \cup \{b\}$$

Now given any $B \in \mathcal{P_{r+1}} (X)$ we can write

$$ \beta^{-1}(B) = \{ (B\setminus\{b\},b) \mid b \in B\}$$

and so $\beta$ is a surjective function with a

$$ (r + 1) \text{ : } 1$$

mapping correspondence.

Therefore

$$\tag 1 |\mathcal{P_{r+1}} (X)| =\, _n C _{r+1} = \frac{_n C _r \times (n-r)}{r+1}$$

Since $_n C _0 = 1$, you can use induction to show that the number of subsets with $k$ elements from a set with $n$ elements $(0 \le k \le n)$ is given by this formula:

$$ _n C _k = \prod_{i=0}^{k-1} \frac{n-i}{i+1} \quad\text{(equal to } 1 \text{ when } k = 0 \text{)} $$

To complete the proof, fix $n$ and observe that

$ _n C_0 = \frac{n!}{0!(n-0)!}$

For $0 \le r \lt n$ assume that

$ _n C_r = \frac{n!}{r!(n-r)!}$

From $\text{(1)}$, all that is required to complete the (finite) induction is to show that

$$ \frac{n!}{(r+1)!\,(n-(r+1))!} = (\frac{n!}{r!\,(n-r)!})(\frac{n-r}{r+1})$$

But using the fact that $t! = t \times (t-1)!$,

$ (\frac{n!}{r!\,(n-r)!})(\frac{n-r}{r+1}) = \frac{(n-r)\,n!}{(r+1)\,r!\,(n-r)\,(n-r-1)!} = \frac{n!}{(r+1)!\,(n-(r+1))!}$

and we get the desired result.

Answer 8

If you have 5 people (A, B, C, D & E) but wants to build a team of three people, the most number of ways you can do is 5x4x3= 60 ways. But realize that team ABC and CBA is basically same team.

So for three people, you can have 3x2x1=6 different combinations.

Meaning that, making a team with 5 poeple with 3 positions, you can have total (5x4x3) / (1x2x3) = 10 different combinations. This number 10 is the 3rd number on 5th row of Pascal's triangle. This basically tells us the number of combination we can have.

And (5x4x3) / (1x2x3) = 5! / (3! x 2!) = C (5, 3)