Combination definition question

Question

I am relatively new to math.

I am confused as to the formula given is this Wikipedia page on combination, where it states in the first paragraph

$$\displaystyle C^n_k={n\choose k}=\frac{n(n-1)…(n-k+1)}{k(k-1)…1},$$ which can be written using factorials as $\displaystyle\frac{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 '$n(n-1)...(n-k+1)$' mean?

Answer 1

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

Answer 2

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