IMC 2014 · Day 2 · P10

Let $a_r \in \{i_1, \dots, i_k\} \cap \{a_1, \dots, a_k\}$. Thus $a_r = i_s$ for some $s \ne r$. Now there are two cases:

Case 1. $a_s \in \{i_1, \dots, i_k\}$. Let $a_s = i_t$. In this case a derangement $x = (x_1, \dots, x_n)$ satisfies the condition $x_{i_j} = a_j$ if and only if the derangement $x' = (x'_1, \dots, x'_{i_t - 1}, x'_{i_t + 1}, x'_n)$

of the set $[n] \setminus \{i_t\}$ satisfies the condition $x'_{i_j} = a'_j$ for all $j \ne t$, where $a'_j = a_j$ for $j \ne s$ and $a'_s = a_t$. This provides a one to one correspondence between the derangements $x = (x_1, \dots, x_n)$ of $[n]$ with $x_{i_j} = a_j$ for the given sets $\{i_1, \dots, i_k\}$ and $\{a_1, \dots, a_k\}$ with $\ell$ elements in their intersections, and the derangements $x' = (x'_1, \dots, x'_{i_t - 1}, x'_{i_t + 1}, x'_n)$ of $[n] \setminus \{i_t\}$ with $x'_{i_j} = a'_j$ for the given sets $\{i_1, \dots, i_k\} \setminus \{i_t\}$ and $\{a_1, \dots, a_k\} \setminus \{a_t\}$ with $\ell - 1$ elements in their intersections.

Case 2. $a_s \notin \{i_1, \dots, i_k\}$. In this case a derangement $x = (x_1, \dots, x_n)$ satisfies the condition $x_{i_j} = a_j$ if and only if the derangement $x' = (x'_1, \dots, x'_{a_s - 1}, x'_{a_s + 1}, x'_n)$ of the set $[n] \setminus \{a_s\}$ satisfies the condition $x'_{i_j} = a_j$ for all $j \ne s$. This provides a one to one correspondence between the derangements $x = (x_1, \dots, x_n)$ of $[n]$ with $x_{i_j} = a_j$ for the given sets $\{i_1, \dots, i_k\}$ and $\{a_1, \dots, a_k\}$ with $\ell$ elements in their intersections, and the derangements $x' = (x'_1, \dots, x'_{a_s - 1}, x'_{a_s + 1}, x'_n)$ of $[n] \setminus \{a_s\}$ with $x_{i_j} = a_j$ for the given sets $\{i_1, \dots, i_k\} \setminus \{i_s\}$ and $\{a_1, \dots, a_k\} \setminus \{a_s\}$ with $\ell - 1$ elements in their intersections.

These considerations show that $\Delta(n, k, \ell) = \Delta(n-1, k-1, \ell-1)$. Iterating this argument we have $$\Delta(n, k, \ell) = \Delta(n - \ell, k - \ell, 0).$$ We can therefore assume that $\ell = 0$. We thus evaluate $\Delta(n, k, 0)$, where $2k \le n$. For $k = 0$, we obviously have $\Delta(n, 0, 0) = D_n$. For $k > 1$, we claim that $$\Delta(n, k, 0) = \Delta(n-1, k-1, 0) + \Delta(n-2, k-1, 0).$$ For a derangement $x = (x_1, \dots, x_n)$ satisfying $x_{i_j} = a_j$ there are two cases: $x_{a_1} = i_1$ or $x_{a_1} \ne i_1$.

If the first case occurs then we have to evaluate the number of derangements of the set $[n] \setminus \{i_1, a_1\}$ for the given sets $\{i_2, \dots, i_k\}$ and $\{a_2, \dots, a_k\}$ with $0$ elements in their intersections. The number is equal to $\Delta(n-2, k-1, 0)$.

If the second case occurs then we have to evaluate the number of derangements of the set $[n] \setminus \{a_1\}$ for the given sets $\{i_2, \dots, i_k\}$ and $\{a_2, \dots, a_k\}$ with $0$ elements in their intersections. The number is equal to $\Delta(n-1, k-1, 0)$.

We now use induction on $k$ to show that $$\Delta(n, k, 0) = \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)}, \qquad 2 \le 2k \le n.$$ For $k = 1$ we have $$\Delta(n, 1, 0) = \Delta(n-1, 0, 0) + \Delta(n-2, 0, 0) = D_{n-1} + D_{n-2} = \frac{D_n}{n-1}.$$ Now let the result be true for $k - 1$. We can write $$\begin{align*} \Delta(n, k, 0) &= \Delta(n-1, k-1, 0) + \Delta(n-2, k-1, 0) \\ &= \sum_{i=0}^{k-2} \binom{k-2}{i} \frac{D_{n-(k-1+i)}}{(n-1) - (k-1+i)} + \sum_{i=0}^{k-2} \binom{k-2}{i} \frac{D_{(n-1)-(k-1+i)}}{(n-2) - (k-1+i)} \\ &= \sum_{i=0}^{k-2} \binom{k-2}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)} + \sum_{i=1}^{k-1} \binom{k-2}{i-1} \frac{D_{n-(k+i-1)}}{(n-1) - (k+i-1)} \\ &= \frac{D_{(n+1)-k}}{n-k} + \sum_{i=1}^{k-2} \binom{k-2}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)} \\ &\qquad + \frac{D_{(n+1)-(2k-1)}}{n - (2k-1)} + \sum_{i=1}^{k-2} \binom{k-2}{i-1} \frac{D_{(n+1)-(k+i)}}{n - (k+i)} \\ &= \frac{D_{(n+1)-k}}{n-k} + \sum_{i=1}^{k-2} \left[ \binom{k-2}{i} + \binom{k-2}{i-1} \right] \frac{D_{(n+1)-(k+i)}}{n - (k+i)} + \frac{D_{(n+1)-(2k-1)}}{n - (2k-1)} \\ &= \frac{D_{(n+1)-k}}{n-k} + \sum_{i=1}^{k-2} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)} + \frac{D_{(n+1)-(2k-1)}}{n - (2k-1)} \\ &= \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)}. \end{align*}$$

Remark. As a corollary of the above problem, we can solve the first problem. Let $n = 2k$, and $i_j = j$, $a_j = k + j$ for $j = 1, \dots, k$. Then a derangement $x = (x_1, \dots, x_n)$ satisfies the condition $x_{i_j} = a_j$ if and only if $x' = (x_{k+1}, \dots, x_n)$ is a permutation of $[k]$. The number of such permutations $x'$ is $k!$. Thus $\sum\limits_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{k+1-i}}{k-i} = k!$.