-2

From the definition of binomial coefficient, $${n\choose k}=\frac{n!}{k!(n-k)!}\Rightarrow \frac{n!}{k!(n-k)!}=\frac{n(n-1)...(n-k+1)}{k!}$$ $$\Rightarrow \frac{n!}{(n-k)!}=n(n-1)...(n-k+1)$$

Could someone explain how to derive the last equation algebraically?

user300048
  • 1,147
  • $$\frac{n!}{(n-k)!}\=\frac {n(n-1)...(n-k+1)\color{red}{(n-k)!}}{\color{red}{(n-k)!}}\=n(n-1)...(n-k+1)$$ –  Mar 18 '16 at 16:17
  • it is not an equation, but equality. One must apply the definition of factorial. – AlvinL Mar 18 '16 at 16:41
  • You want the derivation of $\frac{n!}{(n-k)!}=n(n-1)\cdot\ldots\cdot(n-k+1)!$? That just follows immediately from the definition of the factorial $!$. – Eric S. Mar 18 '16 at 16:42
  • What do you mean? Those are simply definitions aren't they? Do you really need to have $bx = by \implies x = y$ (if $b \ne 0$), do you? – fleablood Mar 18 '16 at 22:28

3 Answers3

2

I will show it using induction. Observe that $$ \frac{k}{(k-k)!} = k(k-1)\dots(k-k+1) $$ Hence the case holds for $n = k$. Suppose that it holds for $n - 1$. Then $$\begin{align*} \frac{n!}{(n-k)!} &= \frac{n (n-1)!}{(n-k) (n-k-1)!}\\ &= \frac{n}{(n-k)} (n-1)(n-2)\dots(n-k)\\ &= n(n-1)(n-2)\dots(n-k+1) \end{align*}$$

Henricus V.
  • 18,694
0

from equations $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$ and$$\binom{n}{0}=1$$ we get $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}=\frac{n}{k}\frac{n-1}{k-1}\binom{n-2}{k-2}=\frac{n}{k}\frac{n-1}{k-1}\frac{n-2}{k-2}\binom{n-3}{k-3}=$$ $$=\frac{n}{k}\frac{n-1}{k-1}\frac{n-2}{k-2}...\frac{n-(k-1)}{k-(k-1)}\binom{n-k}{k-k}=$$ $$=\frac{n}{k}\frac{n-1}{k-1}\frac{n-2}{k-2}...\frac{n-(k-1)}{1}\binom{n-k}{0}=$$

Adi Dani
  • 16,949
0

Seriously?

$n! = n*(n-1)...........*3*2*1$

$(n-k)! = (n-k)*...... *3*2*1$

So $\frac {n!}{(n-k)!} = \frac {n*(n-1)*.....*(n-k + 1)(n-k)*(n-k - 1)*....*3*2*1}{(n-k)*(n-k - 1)*....*3*2*1} = n*(n-1)*.....*(n-k + 1)$

And $\frac {n!}{k!(n-k)!} = \frac 1 {k!}\frac {n!}{(n-k)!} = \frac 1 {k!}n*(n-1)*.....*(n-k + 1) = \frac{n*(n-1)*.....*(n-k + 1)}{k!}$.

The only thing that needs proving is that conceptually that ${n \choose k}$ conceptually can be solved by the expression $\frac{n*(n-1)*.....*(n-k + 1)}{k!}$

Which is... to choose $k$ items from $n$ items with regard to order, you have $n$ choices for the first. For the second you have any choice from the remaining $n-1$ items and so on. For any $i$th item you have may chose any of the $n-i$ remaining choices.

In total that is $n*(n-1)*.......*(n-k +1)$ or $\frac {n!}{(n-k)!}$ ways of choosing... with regard to order.

Without regard to order any of the various ways to arrange the $k$ items are equivalent. So #of ways to choose k from n without regard to order = $\frac {\text{# ways with order}}{\text{#number of ways to order k items}}$.

To arrange $k$ items, you have $k$ options for the first item, any of the $k-1$ remaining options for the second and so on. so #number of ways to order k items = $k!$.

So ${n \choose k}= \text{#of ways to choose k from n without regard to order} = \frac {\text{# ways with order}}{\text{#number of ways to order k items}} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n1}{k!(n-k)!}$

fleablood
  • 124,253