How is the Binomial coefficient simplified to a falling factorial?

726 Views Asked by At

I'm learning how to take the derivative of the binomial coefficient and found a blog post that was quite useful. However I am unclear as to how the first step bellow was simplified to the second step and thus simplifies to the falling factorial in the third step:

$$\displaystyle {n\choose k}=\frac{1\cdot2\cdot3\cdots(n-1)n}{(1\cdot2\cdot3\cdots(k-1)k)(1\cdot2\cdot3\cdots(n-k-1)(n-k))}$$

$$\displaystyle {n\choose k}=\frac{(n-k+1)(n-k+2)\cdots(n-1)n}{(1\cdot2\cdot3\cdots(k-1)k)}$$

$$\displaystyle {n\choose k}=\frac{n^{\underline{k}}}{k!}$$

1

There are 1 best solutions below

0
On BEST ANSWER

I'll use the Pochhammer symbols for ascending and descending factorials in this answer.


$$\binom{n}{k}=\frac{n!}{k! (n-k)!} = \frac{(n)_k}{k!}$$

Here, $(n)_k$ is the falling factorial

$$(n)_k = n \cdot (n-1) \cdots (n-k+1)$$


The simplification from the first to the second line in your question comes from the cancellation of the first $n-k$ terms of the numerator with the first $n-k$ terms (all of the terms) of $(n-k)!$ in the denominator. More explicitly, writing out the numerator like this and clearly distinguishing the two parts of the denominator might help you see it. The red numbers cancel out.

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{\color{red}{1 \cdot 2 \cdot 3 \cdots (n-k-1)(n-k)}(n-k+1)\cdots (n-1) \cdot n}{1 \cdot 2 \cdots (k-1) \cdot k \qquad\!\!\!\! \cdot \qquad\!\!\!\! \color{red}{1 \cdot 2 \cdots (n-k-1)(n-k)}}$$