IMC 2014 · Problem 5

For every positive integer $n$, denote by $D_n$ the number of permutations $(x_1, \dots, x_n)$ of $(1, 2, \dots, n)$ such that $x_j \ne j$ for every $1 \le j \le n$. For $1 \le k \le \frac{n}{2}$, denote by $\Delta(n,k)$ the number of permutations $(x_1, \dots, x_n)$ of $(1, 2, \dots, n)$ such that $x_i = k + i$ for every $1 \le i \le k$ and $x_j \ne j$ for every $1 \le j \le n$. Prove that

$$\Delta(n,k) = \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)}.$$