Sum of the product of Permutations

Question

I found a similar problem on one of my problem sets and am struggling with how to approach the problem.

The problem is as follows: $$ \text{Evaluate} \sum _{k=1}^{n}\:P(n, k-1)P(n-1,n-k). $$

The function $P(n, r)$ represents the number of permutations of length $r$ you can form from $n$ total objects.

Using a Computer Solver (Sympy), I know that the answer is $(2^{n}-1)(n-1)!$. However, I am not sure how to get there. I would appreciate any insights into how to approach this problem and/or a walkthrough on how to get the solution.

Answer 1

$$\sum_{k=1}^nP(n,k-1)P(n-1,n-k)=\sum_{k=1}^n \frac{n!}{(n-k+1)!}\cdot\frac{(n-1)!}{(k-1)!}\\=\sum_{k=0}^{n-1} \frac{n!}{(n-k)!}\cdot\frac{(n-1)!}{k!}=(n-1)!\sum_{k=0}^{n-1} \cdot\frac{n!}{k!(n-k)!} \\=(n-1)!\sum_{k=0}^{n-1} {n\choose k}=(n-1)!\,(2^{n}-1)$$

Answer 2

Just write

$$P(n,r) = \binom nr \cdot r!$$

and note that $\sum_{k=0}^n\binom nk =2^n$.

So, you get

\begin{eqnarray}\sum_{k=1}^{n}\:P(n, k-1)P(n-1,n-k) & = & \sum_{k=1}^{n}\binom n{k-1}(k-1)!\binom{n-1}{n-k}(n-k)! \\ & = & \sum_{k=1}^{n}\frac{n!(n-1)!}{(n-(k-1))!(n-1-(n-k))!} \\ & = & (n-1)!\sum_{k=1}^{n}\binom n{k-1} \\ & = & (n-1)!(2^n-1) \end{eqnarray}