I've just started learneing about permutations and i've come across a problem that has completely stumped me.
Prove P(n, 2) = P(n-1, 2) + 2P(n-1, 1)
Thanks, Joe
In general $\displaystyle P(n,j) = \frac{{n!}}{{\left( {n - j} \right)!}}$ so we have:
$\displaystyle \begin{gathered}
P(n,2) = \frac{{n!}}
{{\left( {n - 2} \right)!}} \hfill \\
P(n - 1,2) = \frac{{\left( {n - 1} \right)!}}
{{\left( {n - 3} \right)!}} \hfill \\
P(n - 1,1) = \frac{{\left( {n - 1} \right)!}}
{{\left( {n - 2} \right)!}} \hfill \\
\end{gathered} $.
Make use of the fact that$\displaystyle P(n,r)=\frac{n!}{(n-r)!}$
$\displaystyle \frac{n!}{(n-2)!}=\frac{(n-1)!}{(n-3)!}+\frac{2(n-1)!}{(n-2)!}$
$\displaystyle \frac{n!}{(n-2)!}-\frac{2(n-1)!}{(n-2)!}=\frac{(n-1)!}{(n-3)!}$
$\displaystyle
\frac{(n-1)(n-2)![n-2]}{(n-2)(n-3)!}=\frac{(n-1)!}{(n-3)!}
$
$\displaystyle (n-1)(n-2)!=(n-1)!$