# Derangements and unit fractions

Motivated by a recent question of Zhi-Wei Sun and its nice answer by Zhao Shen, here are two related questions.

Let $$S_n$$ be the group of permutations on $$\{1, 2, \ldots, n\}$$.

a. For each $$n \ge 6$$, is there some $$\pi \in S_n$$ such that $$\sum_{k=1}^n \frac{1}{k - \pi(k)} = 3?$$

b. For each $$n \ge 8$$, is there some $$\pi \in S_n$$ such that $$\sum_{k=1}^n \frac{1}{k - \pi(k)} = 0?$$

In order for the sums to be well-defined/finite, the permutations must have no fixed points, i.e., the questions are looking for derangements with certain properties.

Here are data found using Mathematica on the number of derangements in $$S_n$$ for which $$\sum_{k=1}^n \frac{1}{k - \pi(k)}$$ is a nonnegative integer. (By symmetry, negative sums match the positive sums.)

$$\begin{array}{r|rrrrrrrr} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 2 & 1 \\ 3 & 0 \\ 4 & 5 \\ 5 & 0 \\ 6 & 53 & 0 & 0 & 1\\ 7 & 0 & 12 & 0 & 1\\ 8 & 859 & 53 & 40 & 27 & 2\\ 9 & 176 & 421 & 23 & 49 & 0 & 0 & 1 \\ 10 & 20329 & 1593 & 1366 & 684 & 120 & 3 & 3 & 2\\ 11 & 7410 & 16025 & 4544 & 2714 & 262 & 38 & 85 & 0\\ \end{array}$$

For example, $$(3,1,2,6,4,5) \in S_6$$ satisfies (a) since \begin{align*} \frac{1}{1-3} + \frac{1}{2-1} + \frac{1}{3-2}+\frac{1}{4-6}+\frac{1}{5-4}+\frac{1}{6-5} \\ = \frac{1}{-2} + 1 + 1+\frac{1}{-2}+1+1=3 \end{align*} and $$(2,6,5,8,4,9,1,7,3)\in S_9$$ satisfies (b) since \begin{align*} \frac{1}{1-2} + \frac{1}{2-6} + \frac{1}{3-5}+\frac{1}{4-8}+\frac{1}{5-4}+\frac{1}{6-9} +\frac{1}{7-1}+\frac{1}{8-7}+\frac{1}{9-3} \\ = -1 + \frac{1}{-4} + \frac{1}{-2}+\frac{1}{-4}+1+\frac{1}{-3} +\frac{1}{6}+1+\frac{1}{6}=0. \end{align*}

• For question b, the answer is yes for n even by any appropriate involution. It might be useful to examine the answers for 9. I suspect each one can be extended to higher n. Similarly, once any sum is achieved for two n of different parity, all higher n should achieve that sum by extending the solution. Gerhard "Knows How To Add Zero" Paseman, 2018.11.24. – Gerhard Paseman Nov 24 '18 at 18:28
• Completing the answer for b): as soon as there is an odd $n$ for which such derangement exists, it also exosts for all larger odd $n$, as you may supplement by independent transpositiobs. Tbe same holds for a) – Ilya Bogdanov Nov 24 '18 at 18:58

Proposition: Suppose $$\pi \in S_n$$ satisfies $$\sum_{k=1}^n \frac{1}{k-\pi(k)} = r$$ for some real number $$r$$. Then, using cycle notation, $$\tau = \pi (n+2, n+1) \in S_{n+2}$$ satisfies $$\sum_{k=1}^{n+2} \frac{1}{k-\tau(k)} = r$$.
Proof: $$\sum_{k=1}^{n+2} \frac{1}{k-\tau(k)} = \left[\sum_{k=1}^n \frac{1}{k-\pi(k)}\right] + \frac{1}{n+1-(n+2)} + \frac{1}{n+2-(n+1)} = r - 1 + 1 = r.$$
Therefore the problem, for any fixed sum, reduces to finding initial permutations of $$S_n$$ for odd and even values of $$n$$. For instance, to verify that, for each $$n \ge 7$$, there is some $$\pi \in S_n$$ with $$\sum_{k=1}^n \frac{1}{k-\pi(k)} = 1$$, it suffices to verify that the derangements (in list form) $$(3,6,7,1,2,5,4) \in S_7$$ and $$(2, 4, 6, 3, 8, 5, 1, 7) \in S_8$$ satisfy the condition. (I found these using Mathematica.)