International Mathematics Competition

Let $a_{r} \in\left\{i_{1}, \ldots, i_{k}\right\} \cap\left\{a_{1}, \ldots, a_{k}\right\}$. Thus $a_{r}=i_{s}$ for some $s \neq r$. Now there are two cases: Case 1. $a_{s} \in\left\{i_{1}, \ldots, i_{k}\right\}$. Let $a_{s}=i_{t}$. In this case a derangement $x=\left(x_{1}, \ldots, x_{n}\right)$ satisfies the condition $x_{i_{j}}=a_{j}$ if and only if the derangement $x^{\prime}=\left(x_{1}^{\prime}, \ldots, x_{i_{t}-1}^{\prime}, x_{i_{t}+1}^{\prime}, x_{n}^{\prime}\right)$ of the set $[n] \backslash\left\{i_{t}\right\}$ satisfies the condition $x_{i_{j}}^{\prime}=a_{j}^{\prime}$ for all $j \neq t$, where $a_{j}^{\prime}=a_{j}$ for $j \neq s$ and $a_{s}^{\prime}=a_{t}$. This provides a one to one correspondence between the derangements $x=\left(x_{1}, \ldots, x_{n}\right)$ of $[n]$ with $x_{i_{j}}=a_{j}$ for the given sets $\left\{i_{1}, \ldots, i_{k}\right\}$$and \left\{a_{1}, \ldots, a_{k}\right\}$ with $\ell$ elements in their intersections, and the derangements $x^{\prime}=\left(x_{1}^{\prime}, \ldots, x_{i_{t}-1}^{\prime}, x_{i_{t}+1}^{\prime}, x_{n}^{\prime}\right)$ of $[n] \backslash\left\{i_{t}\right\}$ with $x_{i_{j}}=a_{j}^{\prime}$ for the given sets $\left\{i_{1}, \ldots, i_{k}\right\} \backslash\left\{i_{t}\right\}$$and \left\{a_{1}^{\prime}, \ldots, a_{k}^{\prime}\right\} \backslash\left\{a_{t}^{\prime}\right\}$ with $\ell-1$ elements in their intersections. Case 2. $a_{s} \notin\left\{i_{1}, \ldots, i_{k}\right\}$. In this case a derangement $x=\left(x_{1}, \ldots, x_{n}\right)$ satisfies the condition $x_{i_{j}}=a_{j}$ if and only if the derangement $x^{\prime}=\left(x_{1}^{\prime}, \ldots, x_{a_{s}-1}^{\prime}, x_{a_{s}+1}^{\prime}, x_{n}^{\prime}\right)$ of the set $[n] \backslash\left\{a_{s}\right\}$ satisfies the condition $x_{i_{j}}^{\prime}=a_{j}$ for all $j \neq s$. This provides a one to one correspondence between the derangements $x=\left(x_{1}, \ldots, x_{n}\right)$ of $[n]$ with $x_{i_{j}}=a_{j}$ for the given sets $\left\{i_{1}, \ldots, i_{k}\right\}$$and \left\{a_{1}, \ldots, a_{k}\right\}$ with $\ell$ elements in their intersections, and the derangements $x^{\prime}=\left(x_{1}^{\prime}, \ldots, x_{a_{s}-1}^{\prime}, x_{a_{s}+1}^{\prime}, x_{n}^{\prime}\right)$ of $[n] \backslash\left\{a_{s}\right\}$ with $x_{i_{j}}=a_{j}$ for the given sets $\left\{i_{1}, \ldots, i_{k}\right\} \backslash\left\{i_{s}\right\}$$and \left\{a_{1}, \ldots, a_{k}\right\} \backslash\left\{a_{s}\right\}$ 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 $2 k \leqslant n$. For $k=0$, we obviously have $\Delta(n, 0,0)=D_{n}$. For $k \geqslant 1$, we claim that $$\Delta(n, k, 0)=\Delta(n-1, k-1,0)+\Delta(n-2, k-1,0)$$ For a derangement $x=\left(x_{1}, \ldots, x_{n}\right)$ satisfying $x_{i_{j}}=a_{j}$ there are two cases: $x_{a_{1}}=i_{1}$ or $x_{a_{1}} \neq i_{1}$. If the first case occurs then we have to evaluate the number of derangements of the set $[n] \backslash\left\{i_{1}, a_{1}\right\}$ for the given sets $\left\{i_{2}, \ldots, i_{k}\right\}$$and \left\{a_{2}, \ldots, a_{k}\right\}$ 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] \backslash\left\{a_{1}\right\}$ for the given sets $\left\{i_{2}, \ldots, i_{k}\right\}$$and \left\{a_{2}, \ldots, a_{k}\right\}$ 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)}, \quad 2 \leqslant 2 k \leqslant 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{aligned} \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)} \\ & +\frac{D_{(n+1)-(2 k-1)}}{n-(2 k-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)-(2 k-1)}}{n-(2 k-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)-(2 k-1)}}{n-(2 k-1)} \\ = & \sum_{i=0}^{k-1}\binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n-(k+i)} . \end{aligned}$$