Permutation on the set of restricted permutations of $\{1,2,\ldots,n\}$

Question

Let $S$ be the set of restricted permutations of $\{1,2,\ldots,n\}$ where $1$ can be permuted to $1,2$ and $n$ can permuted to $n,n-1$ and $i$ can be permuted to $i-1,i,i+1$ for $2\leq i\leq n-1$.

Let $f:S\to S$ be a bijection. Let $\underbrace{f\circ f\circ \cdots f(x)}_{\text{m times}}=x$ be called the orbit of $x$ under $f$ for some $x\in S$.

I am trying to find a bijection $f$ with an orbit as large as possible. I am not sure how to go about finding that. Any ideas?

Answer 1

Obviously, the best case you can hope for is that $m=|S|$, namely that all permutations in $S$ are in one big orbit. Here is an $f$ which achieves this.

From the comments, you know that a permutation $\pi$ is in $S$ if and only if $S$ the cycle structure of $\pi$ only has fixed points and transpositions, and all transpositions are of the form $(i\;\;i+1)$, switching adjacent elements. For completeness, the proof is this. If $\pi(n)=n$, then by induction, $\pi$ restricted to $\{1,\dots,n-1\}$ also has the form described. If $\pi(n)=n-1$, then you must have $\pi(n-1)=n$, since only $n-1$ and $n$ can map to $n$, and we similarly conclude by induction that $\pi$ restricted to $\{1,\dots,n-2\}$ has the claimed form.

Such a permutation can be uniquely represented as an ordered sequence of ones and twos whose total is $n$. For example, $$ (1\;2)(3)(4)(5\;6)(7\;8)(9)\quad \iff\quad 2,1,1,2,2,1 $$ I will define $f:S\to S$ in terms of these sequences of ones and twos.

Let $s\in S$. To compute $f(s)$,

• Find the rightmost $1$ in $s$ which is not at the right end. If no such $1$ exists, then $s=2,2,\dots,2$ or $s=2,2,\dots,2,1$, and we define $f(s)=1,1,\dots,1$.

  • If that $1$ has a $1$ to its right, then delete both $1$'s, and put a $2$ in their place.
  • If that $1$ is has a $2$ to its right, then switch that $1$ and $2$.

• Finally, find all $2$'s to the right of the change just made, and replace each of them with the substring $1,1$.

More succinctly, $f(s)$ is the next string after $s$ in lexicographic order, unless $s$ is the last in this order, in which case $f(s)$ is the earliest string. Here is an example of the complete orbit when $n=6$.

Step	Sequence
1	$1111\color{red}{11}$
2	$111\color{red}{12}$
3	$11\color{red}{12}1$
4	$112\color{red}{11}$
5	$1\color{red}{12}2$
6	$121\color{red}{11}$
7	$12\color{red}{12}$
8	$\color{red}{12}21$
9	$211\color{red}{11}$
10	$21\color{red}{12}$
11	$2\color{red}{12}{1}$
12	$22\color{red}{11}$
13	$222$
14	$111111$