0
$\begingroup$

Let $n$ and $k$ be positive integers with $n \ge k$. Give a combinatorial proof that $$n_k = (n-1)_k + k(n-1)_{k-1},$$ where $n_k$ is a falling factorial: $n_k$ = $n(n-1)(n-2)\ldots(n-k+1)$.

I know $n_k = n \cdot (n-1)_{k-1}$. For example $10_4 = 10 \cdot 9_3$, which equates to: $10 \cdot 9 \cdot 8 \cdot 7 = 10 \cdot (9 \cdot 8 \cdot 7)$.

However, I am completely lost on how to extrapolate $n_k = (n-1)_k + k(n-1)_{k-1}$ from $n_k = n \cdot (n-1)_{k-1}$.

I can work out numerical examples in my head and it makes perfect sense, but I'm missing something and I dont know what it is that I'm missing.

$\endgroup$
  • $\begingroup$ Hint: Split the $n$ factor into $\left(n-k\right) + k$. $\endgroup$ – darij grinberg Mar 1 at 3:16
1
$\begingroup$

$n_k$ represents the number of arrangements of $n$ elements in groups of $k$ (the order is relevant here). Split those arrangements into two classes: those where one particular element is part of the group and those where this element is not part of the group. The number of the latter is $(n-1)_k$ because you choose among the rest. The number of the former is $k(n-1)_{k-1}$ because you choose $k-1$ among the remaining $(n-1)$ and there are $k$ possible locations for the fixed element.

$\endgroup$
  • $\begingroup$ I thought you were supposed to give a combinatorial proof, not an algebraic one. $\endgroup$ – GReyes Mar 1 at 3:56
0
$\begingroup$

I don't know the notation which you have used(I am still new in combinatorics). So I will use simple factorial notation. $$\frac{n!}{(n-k)!}$$
$$=\frac{{((n-k)+k)}\cdot{(n-1)!}}{(n-k)!}$$
$$=\frac{(n-1)!}{(n-k-1)!}+\frac{k(n-1)!}{(n-k)!}$$
$$=(n-1)_k +k(n-1)_{k-1}$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.