|
3 | deleted 16 characters in body | ||
|
For $0 \le lt k \lt n$, $$\binom{n}{k} = \frac{n}{n-k}\binom{n-1}{k}$$ How k-subsets of [n], marked dark green in the rows, come from k-subsets of [n-1] after n-fold duplication and rearrangement:
|
||||
|
|
2 | added 331 characters in body | ||
|
$ For $0 \binom{n}{k} le k \lt n$, $$\binom{n}{k} = \frac{n!}{(n-k)!\ k!} frac{n}{n-k}\binom{n-1}{k}$$ How k-subsets of [n], marked dark green in the rows, come from k-subsets of [n-1] after n-fold duplication and rearrangement:
Induction step for k=n$ which we already know due to case $k < n$:
Hint: k=0$: $$\frac{n}{(n-k)} $\binom{n}{k} = \frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!} = \frac{n!}{(n-k)!\ k!}$$ |
||||
|
|
1 | [made Community Wiki] | ||
|
$$ \binom{n}{k} = \frac{n!}{(n-k)!\ k!} $$ Induction step for $k < n$:
Hint: $$\frac{n}{(n-k)} \frac{(n-1)!}{(n-1-k)!\ k!}$$ |
||||
Exactly $n-k$ times:
