Characterizing multisets that are the sum of two permutations

Suppose you have a permutation $\pi$ of $1 \ldots n$. The multiset $\{m_i\}$ = $\{ i + \pi(i) \}_i$ is easily seen to have the following properties:

• $\sum_j m_j = n(n+1)$.

• If the elements are ordered so $m_1 \leq m_2 \leq \ldots \leq m_n$, then $\sum_{j=1}^k m_j \geq k(k+1)$.

For example, if the permutation $\pi$ is 5 2 3 1 4, the multiset is $\{4,5,6,6,9\}$

  1 2 3 4 5 
+ 5 2 3 1 4
= 6 4 6 5 9

Are these two properties sufficient? That is, for every multiset satisfying these two properties, is there a permutation $\pi$ that generates it?

This is a question that I have thought about in the past, and I was reminded of it by this related cs.SE question.

EDIT: and if you look at the linked cs.SE question, I give a link that shows the problem of determining whether a multiset is the sum of two permutations is NP-complete.

Solution 1:

Nice question! Using a computer search, I found that $\{5,5,5,9,9,9\}$ satisfies the criteria but does not arise from a permutation in this way. The number of multisets generated by the permutations in $S_n$ in this way seems to be A019589 ($1, 2, 5, 16, 59, 246, 1105, \ldots)$ in Sloane's while the number of multisets with $n$ elements satisfying the conditions you gave is A007747 $(1, 2, 5, 16, 59, 247, 1111, \ldots)$.