Combination Definition Question

Combination Definition Question
$\begingroup$

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$
0

2 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

James H. Sterling
Author

James H. Sterling

James Sterling reports on renewable energy developments, climate policy, ecological conservation, and green tech innovations around the globe.