Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How was the binomial coefficient of the binomial theorem derived? $$\frac{n!}{k!(n-k)!}$$

share|improve this question
    
Do you mean how was it derived historically? You might look at www-history.mcs.st-andrews.ac.uk/Biographies/Al-Karaji.html –  Robert Israel Mar 12 '12 at 23:19
1  
Originally the coefficients would have been expressed using Pascal's triangle. I don't know when the expression using factorials was discovered. –  Robert Israel Mar 12 '12 at 23:30
    
I also want to know when the factorial expression is discovered. –  FiniteA Mar 13 '12 at 3:50
add comment

4 Answers

up vote 7 down vote accepted

There are two possible questions here: (i) Why is $\binom{n}{k}$ ("$n$ choose $k$") given by the expression that you gave and (ii) Why is the coefficient of $x^k$ in the expansion of $(1+x)^n$ equal to $\binom{n}{k}$.

We answer question (i), giving two combinatorial arguments. For some reason, the first has been more standard in textbooks than the second.

First argument: Note that $\binom{n}{k}$ is the number of ways to choose $k$ people from $n$ people. We look at a different problem. How many ways are there to choose $k$ people and line them up in a row? We will calculate this number $N$ in two different ways.

Way $1$: Choose the $k$ people. This by definition can be done in $\binom{n}{k}$ ways. For every way of choosing the people, there are $k!$ ways to line them up. It follows that $$N=\binom{n}{k}k!.$$ Of course, we officially don't know a formula for $\binom{n}{k}$. But we soon will!

Way $2$: The first person for the lineup can be chosen in $n$ ways. For every one of these ways, the second person in the line can be chosen in $n-1$ ways. Continue, for a total of $k$ times. It follows that $$N=(n)(n-1)(n-2)\cdots(n-k+1)$$ Multiply "top" and "bottom" (which is invisible, it is $1$) by $(n-k)!$. We conclude that $$N=\frac{n!}{(n-k)!}$$

Way $1$ and Way $2$ of counting are both correct, so the answers must be the same. It follows that $$\binom{n}{k}k!=\frac{n!}{(n-k)!}.$$ Now dividing both sides by $k!$ gives us the formula you mentioned.

Second argument: We count in two different ways the number of ways to arrange $n$ people in a row. Let $n$, for example, be $100$.

First way: It is a standard fact that this number is $n!$, or in our concrete case, $100$!.

Second way: We count the same thing in a somewhat strange way. Pick once and for all an integer $k$, with $0\le k\le n$. In our concrete case with $n=100$, pick say $k=17$.

Choose the collection of people who will occupy the first $k$ positions. This can be done in $\binom{n}{k}$ ways. For each such choice, the $k$ chosen people can be lined up in $k!$ ways. And for every way of choosing and lining up the $k$ chosen people, there are $(n-k)!$ ways to line up the unchosen $n-k$ people in the $n-k$ positions in back of all the chosen people, for a total of $$\binom{n}{k}k!(n-k)!$$ ways. In the concrete case, it would be $\binom{100}{17}17!83!$.

Finally, compare the two answers. We conclude that $$n!=\binom{n}{k}k!(n-k)!,$$ and now dividing both sides by $k!(n-k)!$ gives the desired result.

Remark: Counting something in two different ways is a powerful method for obtaining combinatorial identities. There are many examples.

share|improve this answer
    
Exactly what I was looking for. –  user26649 Mar 13 '12 at 1:04
add comment

I don't know how the result was originally derived, but here is one calculation.

Let $f(x) = (1+x)^n$ and let us try and find the Maclaurin series for $f(x)$.

  • The $0$-th derivative $f^{(0)}(x)$ is just $f(x) = (1 + x)^n$ itself. The first derivative is $f^{(1)}(x) = n(1+x)^{n-1}$, the second is $f^{(2)}(x) = n(n-1)(1+x)^{n-2}$, and so on. The $k$-th derivative is $f^{(k)}(x) = n(n-1)\cdots (n-k+1)(1+x)^{n-k}$, and finally the $n$-th derivative is $f^{(n)}(x) = n(n-1)\cdots 2 \cdot 1 = n!$ which is a constant. Hence, the first $n+1$ terms of the Maclaurin series for $f(x)$ are $$f(x) = (1 + x)^n \approx \sum_{k=0}^n \frac{f^{(k)}(0)}{k!} x^k = \sum_{k=0}^n \frac{n(n-1)\cdots (n-k+1)}{k!} x^k.$$ In fact, since $f^{(n)}(x)$ is a constant, $f^{(k)}(x) = 0$ for all $k > n$. Thus, the above is the complete Maclaurin series for $f(x)$; there is no approximation.

  • The Maclaurin series for $(1+x)^n$ is called the binomial theorem expansion of $(1+x)^n$, and the coefficient of $x^k$ in the series called a binomial coefficient. We denote this coefficient by $\binom{n}{k}$ and write $$f(x) = (1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k.$$ Note that upon multiplying $\binom{n}{k}$ by $\frac{(n-k)!}{(n-k)!} = 1$ that $$\binom{n}{k}\times \frac{(n-k)!}{(n-k)!} = \frac{n(n-1)\cdots (n-k+1)}{k!}\times \frac{(n-k)!}{(n-k)!} = \frac{n!}{k!(n-k)!}.$$

share|improve this answer
add comment

For a good reading one should get the share of amusement from http://poncelet.math.nthu.edu.tw/disk5/js/geometry/binomial.pdf

share|improve this answer
add comment

Simple proof "by story":

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}a^nb^{n-k}$$

Left-hand side means in how many distinct ways you can give one gift to every of $n$ children having $a$ different candies and $b$ different lollipops, i.e. the number of functions $$\{1,\ldots,n\} \to \{1,\ldots,a\}\cup\{-1,\ldots,-b\}\,.$$

For right-hand side consider the term $$\binom{n}{k}a^nb^{n-k}\,.$$ This formula denotes the number of ways you could split $n$ children into two groups, first of size $k$ and the other of size $n-k$, and then distribute the gifts (candies in first and lollipops in the second) in each group separately. Then, if you sum that up by all the possible sizes of first group ($k$ ranges from $0$ to $n$) you will get all the possible assignments (of children to candies and lollipops), same as in the left-hand side.

Notice: this proof works only for $a,b,n \in \mathbb{N}$.

share|improve this answer
    
Whoops, it seems (by other answers) I misinterpreted the question... –  dtldarek Mar 12 '12 at 23:38
1  
Don't beat yourself up. It is OP's fault to write such an ambiguous question. –  Aryabhata Mar 13 '12 at 1:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.