I am relatively new to math.
I am confused as to the formula given is this wiki page on combination , where it states in the first paragraph
''nCk= [n(n-1)...(n-k+1)]/[k(k-1)....1] which can be written using factorials as {n!/[k!(n-k)!]}''
How do these two formulas equate to each other, in the first formula I understand the denominator is K!. But, what does this line mean 'n(n-1)...(n-k+1)' mean??
$\endgroup$ 02 Answers
$\begingroup$$n(n-1)\cdots(n-k+1)=\frac{n(n-1)\cdots(n-k+1)(n-k)(n-k-1)\cdots1}{(n-k)(n-k-1)\cdots1}=\frac{n!}{(n-k)!}$
hence:$$\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n!}{k!(n-k)!}$$
$\endgroup$ 1 $\begingroup$It means the product starting at $n$ and going backwards several times, multiplying each time along the way, until we get $k$ numbers. We thus get
$$n \times (n-1) \times (n-2) \times (n-3) \times \cdots \times (n-(k-1))$$
Notice how $(n-1)$ is the point where we have $2$ numbers, $(n-2)$ is the point where we have $3$, and so on, so that $(n-(k-1))$ is the point with the $k^{th}$ number. We often rewrite this last as $(n-k+1)$ since it's simpler.
Some examples of this, explicitly, are below. Notice how each will have $k$ numbers being multiplied together, the integers from $n-k+1$ all up to $n$.
- $n=3,k=2$ gives the product of $3 \times 2$
- $n=4,k=2$ gives the product of $4 \times 3$
- $n=5,k=4$ gives the product of $5 \times 4 \times 3 \times 2$
- $n=6,k=3$ gives the product of $6 \times 5 \times 4$
Of course, then, notice that you can extend the original product of $n \times (n-1) \times \cdots \times (n-k+1)$ all of the way down to $1$, by multiplying by the intermediate integers, which would be the next lowest ones: $(n-k)$, $(n-k-1)$, $(n-k-2)$, and so on. But to keep it equal, you will need to divide by those factors as well. Thus,
$$n(n-1)\cdots (n-k+1) = \frac{n(n-1)\cdots (n-k+1)(n-k)(n-k-1)\cdots(2)(1)}{(n-k)(n-k-1)(n-k-2)\cdots(2)(1)}$$
But notice! The numerator is precisely the definition of $n!$, and the bottom is that for $(n-k)!$ as well! That means,
$$n(n-1)\cdots (n-k+1) = \frac{n!}{(n-k)!}$$
Thus, when one says that
$$\binom n k = \frac{n(n-1)\cdots(n-k+1)}{k!}$$
it is equivalent to say that, substituting our new expression in terms of factorials in for the product,
$$\binom n k = \frac{n!}{k!(n-k)!}$$
$\endgroup$
