19
$\begingroup$

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.

I conjecture that the question has a positive answer. Your comments are welcome!

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.

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Brian Hopkins Nov 19 '18 at 3:51
  • 5
    $\begingroup$ 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$. $\endgroup$ – Martin Rubey Nov 19 '18 at 7:23
  • $\begingroup$ 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? $\endgroup$ – darij grinberg Nov 27 '18 at 3:13
31
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Y.H. Nov 27 '18 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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