1
$\begingroup$

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*}

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 24 '18 at 18:28
  • 2
    $\begingroup$ 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) $\endgroup$ – Ilya Bogdanov Nov 24 '18 at 18:58
1
$\begingroup$

For completeness, let me give an answer using the ideas of Gerhard and Ilya in the comments.

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.)

For another question in this vein, see here.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.