Given a natural number $k<n$ and a permutation $\sigma\in S_n$, I will call $k$ a shift of $\sigma$ if there is some $m$ with $\sigma(m)-m\equiv k \mod n$. If one is given a sequence $s=(x_1,...,x_n)$ of $n$ natural numbers between $0$ and $n-1$, is there some known way to determine whether $s$ represents the shifts of some permutatuon in $S_n$? If not, I am also interested in relevant heuristics. Thank you.
$\begingroup$
$\endgroup$
6
-
3$\begingroup$ See artofproblemsolving.com/community/c6h85076p494833 $\endgroup$– Ilya BogdanovCommented Jun 9, 2020 at 21:13
-
$\begingroup$ @IlyaBogdanov: that link characterizes sequences which are sums (equivalently, differences) of two permutations. But the question here is slightly different, because here one of the permutations is assumed to be the identity. Does the same result still apply? $\endgroup$– Sam HopkinsCommented Jun 11, 2020 at 17:22
-
$\begingroup$ @SamHopkins Yes; if $\sigma$ and $\tau$ are two permutations with prescribed differences, then $\sigma\tau^{-1}$ is a permutation with the same multiset of shifts. $\endgroup$– Ilya BogdanovCommented Jun 11, 2020 at 19:22
-
$\begingroup$ @IlyaBogdanov: yes, but it was unclear to me whether the question was about multisets of shifts or sequences of shifts. $\endgroup$– Sam HopkinsCommented Jun 11, 2020 at 19:45
-
1$\begingroup$ @SamHopkins Well, for a sequence it is rather trivial, isn’t it? The characterization is ‘$x_i+i$ are pairwise distinct module $n$’... $\endgroup$– Ilya BogdanovCommented Jun 11, 2020 at 19:50
|
Show 1 more comment