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

1. August 1, 2014 at 7:57 pm
2. August 3, 2014 at 6:11 pm

Very straightforward solution:
delta(n+1,k+1)=delta(n,k)+delta(n-1,k). The proof of this is easy combinatorical transformation – start with delta(n+1,k+1), erase 2k+2 from the list, exchange 2k+1 with k+1 and if needed, erase 2k+1 as well. In order to complete an induction, just check the trivial cases delta(2k,k) and delta(n,1).