Q10 Matemática  (IMC 2014)

Para cada inteiro positivo $n$, denote por $D_n$ o número de permutações $(x_1,\dots ,x_n)$ de $(1,2,\dots ,n)$ tal que $x_j\ne j$ para cada $1\le j\le n$. Para $1\le k\le \frac{n}{2}$, denote por $\Delta (n,k)$ o número de permutações $(x_1,\dots ,x_n)$ de $(1,2,pontos,n)$ tal que $x_i=k+i$ para cada $1\le i\le k$ e $x_j\ne j$ para cada $1\le j\le n$. Prove que $$\Delta (n,k)=\sum _{i=0}^{k=1}\left(\genfrac{}{}{0ex}{}{k-1}{i}\right)\frac{D_{(n+1)-(k+i)}}{n-(k+i)}$$ (Proposto por Combinatorics; Universidade Ferdowsi de Mashhad, Irã; Mirzavaziri)