$k$-permutations combinatorial proof $P(n,k) = P(n-1,k) + k\cdot P(n-1,k-1).$

Question

I'm currently working through Richard Hammack's Book of Proof.

I'm a bit stumped on the combinatorial proof of $k$-permutations:

Show that $$P(n,k) = P(n-1,k) + k\cdot P(n-1,k-1).$$

Can anyone give me a hand with this? Much appreciated!

Answer 1

Another approach could be double counting or counting in two ways.

Assume we want to make a $k-$member ordered line (for example from left to right) with $n$ students. Clearly this can be done in $P(n,k)$ ways.

Now, pick a student out of the $n$ students called $A$. Two cases happen:

$1$. $A$ is absent in the line. In this case we will have $P(n-1,k)$ ways.

$2$. $A$ is not absent. In this case $A$ can stands at $k$ positions and regardless of the position of $A$, $n-1$ other positions can be filled in $P(n-1,k-1)$ ways. Thus, we will get $k.P(n-1,k-1)$ ways in this case.

Answer 2

By definition, we have:

$\displaystyle \tag*{} P(n,k) = \dfrac{n!}{(n-k)!}$

So:

$\displaystyle \tag*{}\begin{align} P(n-1,k) &=\dfrac{(n-1)!}{(n-k-1)!} \\\\ P(n-1,k-1)&= \dfrac{(n-1)!}{(n-k)!} \end{align}$

Now, solving RHS, we have:

$\displaystyle \tag*{} \begin{align} P(n-1,k) + k \cdot P(n-1,k-1) &= \dfrac{(n-1)!}{(n-k-1)!} + k \cdot \dfrac{(n-1)!}{(n-k)!} \\\\ &= \dfrac{(n-1)!}{(n-k)!} \cdot (n-k+k) \\\\ &= \dfrac{n!}{(n-k)!} \end{align} $