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\neq 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\neq 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)}$$ (Proposed by Combinatorics; Ferdowsi University of Mashhad, Iran; Mirzavaziri)