Home > Algebra, Combinatorics > IMC 2014 Day 2 Problem 5

## IMC 2014 Day 2 Problem 5

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

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

IMC 2014 Day 2 Problem 5