Consider all the permutations of the first $n$ natural numbers. From each permutation we can form a multiset of integers (which I call a gap multiset) consisting of all the absolute differences of each adjacent pair in the permutation.
For example if $n=6$ we have $n!=120$ such permutations. The permutation (1,2,3,4,5,6) produces the gap multiset {1,1,1,1,1} and (1,6,2,5,3,4) produces the gap mutliset {1,2,3,4,5}.
There are three obvious conditions for a gap multiset of a permutation of the first $n$ natural numbers:
- The multiset must have a cardinality of $n-1$.
- The elements must be integers between $1$ and $n-1$ inclusive.
- Each of the integers $m$, where $0<m<n$, have a maximum multiplicity of $n-m$.
So for example if n=6 then due to condition 3 you can only have one 5, since it can only be formed from 6-1=5.
These conditions are necessary but not sufficient for a multiset to be a gap multiset. For example if $n=6$ the following multisets fulfill all the conditions above but are not gap multisets:
- {3,3,4,4,5}
- {3,3,3,4,5}
- {2,3,4,4,5}
- {2,2,3,4,5}
- {2,2,2,4,4}
- {2,2,2,2,4}
- {1,3,4,4,5}
In another example, if n=10 then:
- {1,1,1,1,1,7,8,8,9} is NOT a gap multiset
- {1,1,1,1,1,7,7,8,9} is a gap multiset, corresponding to 4 permutations
Can you give succinct conditions which are sufficient for a multiset to be a gap multiset? I.e. given a multiset, can you give an algorithm that decides whether or not it is a gap multiset, which does not involve a search?