# Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$

Let $$S_n$$ be the symmetric group of all the permutations of $$\{1,\ldots,n\}$$. Motivated by Question 315568 (http://mathoverflow.net/questions/315568), here I pose the following question.

QUESTION: Is it true that for each integer $$n>5$$ we have $$\sum_{k=1}^n\frac1{k+\pi(k)}=1$$ for some odd (or even) permutation $$\pi\in S_n$$?

Let $$a_n$$ be the number of all permutations $$\pi\in S_n$$ with $$\sum_{k=1}^n(k+\pi(k))^{-1}=1$$. Via Mathematica, I find that $$\begin{gather}a_1=a_2=a_3=a_5=0,\ a_4=1,\ a_6=7, \\ a_7=6,\ a_8=30,\ a_9=110, \ a_{10}=278,\ a_{11}=1332.\end{gather}$$ For example, $$(1,4,3,2)$$ is the unique (odd) permutation in $$S_4$$ meeting our requirement for $$n=4$$; in fact, $$\frac1{1+1}+\frac1{2+4}+\frac1{3+3}+\frac1{4+2}=1.$$ For $$n=11$$, we may take the odd permutation $$(4,8,9,11,10,6,5,7,3,2,1)$$ since \begin{align}&\frac1{1+4}+\frac1{2+8}+\frac1{3+9}+\frac1{4+11}+\frac1{5+10}\\&+\frac1{6+6}+\frac1{7+5}+\frac1{8+7}+\frac1{9+3}+\frac1{10+2}+\frac1{11+1}\end{align} has the value $$1$$, we may also take the even permutation $$(5, 6, 7, 11, 10, 4, 9, 8, 3, 2, 1)$$ to meet the requirement.

PS: After my initial posting of this question, Brian Hopkins pointed out that A073112($$n$$) on OEIS gives the number of permutations $$p\in S_n$$ with $$\sum_{k=1}^n\frac1{k+p(k)}\in\mathbb Z$$, but A073112 contains no comment or conjecture.

• This sequence (with just one more term, 3312) is A073112 with the requirement that the sum is an integer. No citations or other interpretations, just PARI code. – Brian Hopkins Nov 19 '18 at 3:51
• It seems that the identity maximises $\sum_{k=1}^n\frac{1}{k+\pi(k)}$, so this maximum is strictly less than $2$ for small values of $n$, which explains the coincidence. If the identity indeed maximises the sum, the first time the two sequences might be different is for $n=31$. – Martin Rubey Nov 19 '18 at 7:23
• Brief comment on your arXiv:1811.10503v1 preprint: Theorem 1.2 is very close to Theorem 1 (a) in math.stackexchange.com/a/2597700 (which has since become part of Theorem 1.1 in Johann Cigler's arXiv:1803.05164v2). Indeed, if I shift my numbers $0, 1, \ldots, n-1$ by $1$, then my nimble permutation becomes a $\pi \in S_n$ such that each $i \in \left\{1,2,\ldots,n\right\}$ has the property that $i + \pi\left(i\right)$ equals a power of $2$ minus $1$. Are your and my permutation related? – darij grinberg Nov 27 '18 at 3:13

Claim: $$a_n>0$$ for all $$n\geq 6\quad (*)$$.

Proof: We use induction to prove $$(*)$$.

We have $$a_6,a_7,a_8,a_9,a_{10},a_{11}>0$$. Assume $$(*)$$ holds for all the integers $$\in [6,n-1]$$. We want to show that $$a_n>0$$ for all $$n\geq12$$.

If $$n$$ is an odd, let $$n=2m+1$$, we have $$m\geq6$$, so by induction hypothesis, there exists $$\pi\in S_m$$ such that $$\sum\limits_{k=1}^{m}\frac{1}{k+\pi(k)}=1$$. Let \begin{align*} \sigma(2k+1)&=2m+1-2k\quad\text{for}\quad k=0,1,2\ldots, m,\\ \sigma(2k)&=2\pi(k)\quad\text{for}\quad k=1,2,\ldots, m. \end{align*} Then $$\sigma\in S_{n}$$, and $$\sum\limits_{k=1}^{n}\frac{1}{k+\sigma(k)}=\sum\limits_{k=1}^{m}\frac{1}{2k+\sigma(2k)}+\sum\limits_{k=0}^{m}\frac{1}{2k+1+\sigma(2k+1)}\\ =\frac{1}{2}\sum\limits_{k=1}^{m}\frac{1}{k+\pi(k)}+\sum\limits_{k=0}^{m}\frac{1}{2k+1+(2m-2k+1)}=\frac{1}{2}+(m+1)\frac{1}{2m+2}=1.$$

If $$n$$ is an even, let $$n=2m$$, also we have $$m\geq6$$ and there exists $$\pi\in S_m$$, such that $$\sum\limits_{k=1}^{m}\frac{1}{k+\pi(k)}=1$$. Let \begin{align*} \sigma(2k-1)&=2m+1-2k\quad\text{for}\quad k=1,2,\ldots,m, \\ \sigma(2k)&=2\pi(k)\quad\text{for}\quad k=1,2,\ldots,m. \end{align*} Then $$\sigma\in S_{n}$$ and $$\sum\limits_{k=1}^{n}\frac{1}{k+\sigma(k)}=\sum\limits_{k=1}^{m}\frac{1}{2k+\sigma(2k)}+\sum\limits_{k=1}^{m}\frac{1}{2k-1+\sigma(2k-1)}=\frac{1}{2}\sum\limits_{k=1}^{m}\frac{1}{k+\pi(k)}+ \sum\limits_{k=1}^{m}\frac{1}{2k-1+(2m-2k+1)}=1.$$ Hence $$a_{n}>0$$.

By induction $$(*)$$ holds for all the $$n\geq 6$$.

• So we are done if the permutations for n=6~11 contain both odd ones and even ones. Is it true according to the computer? Also, following this idea, what is the best lower bound of a_n you can get? – Yifeng Huang Nov 27 '18 at 23:53