I was was solving IMO 1987, Problem 1 and also found the first solution. However, I also tried a combinatorics approach but couldn't find any valid argument. My argument was as follows:
Consider each $p_n(k)$ seperately. There are $n \choose k$ possibilities to choose $k$ fixed points and $n-k$ positions that should not contain fixed points. Now filling the gaps from begin to end, the first non-fix point position has $n-k-1$ possibilities ($k$ taken + 1 is not allowed). The second position has $n – k – 2$ by the same logic, etc. In total we get:
$$
p_n(k) = {n \choose k} (n-k-1)!
$$
Now, for $k = n-1$ we automatically get $n$ fixed points by the pigeonhole principle. Therefore, we can exclude $k-1$ from our answer:
$$
\sum_{k=0}^n k p_n(k) = \sum_{k=1}^{n} k p_n(k) = \left( \sum_{k=1}^{n-2} kp_n(k) \right) + n = n + \sum_{k=1}^{n-2} k{n \choose k} (n-k-1)!
$$
I then tried to show that
$$
\sum_{k=1}^{n-2} k {n \choose k} (n-k-1)! = n! – n
$$
via induction but it doesn't work. For $n = 3,4$ the formula gives the correct result.
Could anyone point out where the flaw in my logic is and maybe share a valid solution based on combinatorics.
Best Answer
Your claim that $p_n(k)=\binom nk(n-k-1)!$ is not correct. In the case where $k=0$, your formula would imply that there are $(n-1)!$ permutations with zero fixed points, so $(n-1)!$ derangements of $n$ objects. However, when $n=4$, your formula claims there are $(4-1)!=6$ derangements, but there are actually $9$ derangements of four objects.
Let $D_n$ be the number of derangements of $n$ objects. It is well known that $$ D_n=n!\sum_{k=0}^n \frac{(-1)^k}{k!} $$ The correct formula for $p_n(k)$ is
$$ p_n(k)=\binom nkD_{n-k} $$ This is similar to what you have, but instead of $(n-k-1)!$, the correct expression is $D_{n-k}$.
This old question has three great proofs of the formula. One proof uses simple algebraic rearrangement, one proof uses a bijective proof, and the final uses a probabilistic proof involving linearity of expectation.