What does the sum $\sum_{k=r}^{n} {k\choose r} p_{n,k}$ equal to? Let $p_{n,k}$ be the number of permutations of $[n]$ such that there are exactly $k$ fixed points. Let $r\in[n]$. 
What does the sum $$\sum_{k=r}^{n} {k\choose r} p_{n,k}$$
equal to? I'm told that there is a simplified answer but I'm unable to find it.
I think that $$p_{n,k}={n\choose k}!(n-k)$$ because to choose a permutation with $k$ fixed points we first have to choose the fixed points and then choose any derangement of the $n-k$ points that we didn't choose.
${n\choose k}{k\choose r}$ looks promising but I don't know how to deal with the $!(n-k)$.
Any hints would be appreciated.
 A: Define the set $S$ as follows;
$$S=\left\{(\sigma,A):\sigma\text{ is a permutation of }[n], A\text{ is an }r\text{-subset of }[n],\sigma\text{ fixes each element of } A\right\}$$
We count the size of $S$ in two different ways.
If we fix the first coordinate, $\sigma$, then the set $A$ must be chosen from the fixed points of $\sigma$, and it is easy to see that this gives the expression $\sum_{k=r}^{n} {k\choose r} p_{n,k}$ as you required.
On the other hand, once we fix the second coordinate, $A$, the action of permutation $\sigma$ is already decided on $A$ and there are $(n-r)!$ further options to consider. This gives $\#S={n\choose r}(n-r)!=n!/r!$, as in the comments.
A: This sum counts the ways to mark $r$ fixed points in permutations of $n$ elements by summing over the total number $k$ of fixed points in the permutation. You can count the same thing directly by first choosing $r$ elements to mark and then permuting the remaining $(n-r)!$ elements without constraints. There are $\binom nr$ choices for the $r$ points and $(n-r)!$ permutations for the remaining elements, for a count of $\frac{n!}{r!}$.
