Given a permutation $\left(a_{0}, a_{1}, \ldots, a_{n}\right)$ of the sequence $0,1, \ldots, n$. A transposition of $a_{i}$ with $a_{j}$ is called legal if $a_{i}=0$ for $i>0$, and $a_{i-1}+1=a_{j}$. The permutation $\left(a_{0}, a_{1}, \ldots, a_{n}\right)$ is called regular if after a number of legal transpositions it becomes $(1,2, \ldots, n, 0)$. For which numbers $n$ is the permutation $(1, n, n-1, \ldots, 3,2,0)$ regular?

Answer: $n=2$ and $n=2^{k}-1, k$ positive integer.

#
A legal transposition consists of looking at the number immediately before 0 and exchanging 0 and its successor; therefore, we can perform at most one legal transposition to any permutation, and a legal transposition is not possible only and if only 0 is preceded by $n$.

If $n=1$ or $n=2$ there is nothing to do, so $n=1=2^{1}-1$ and $n=2$ are solutions. Suppose that $n>3$ in the following.

Call a pass a maximal sequence of legal transpositions that move 0 to the left. We first illustrate what happens in the case $n=15$, which is large enough to visualize what is going on. The first pass is

$$
\begin{aligned}
& (1,15,14,13,12,11,10,9,8,7,6,5,4,3,2,0) \\
& (1,15,14,13,12,11,10,9,8,7,6,5,4,0,2,3) \\
& (1,15,14,13,12,11,10,9,8,7,6,0,4,5,2,3) \\
& (1,15,14,13,12,11,10,9,8,0,6,7,4,5,2,3) \\
& (1,15,14,13,12,11,10,0,8,9,6,7,4,5,2,3) \\
& (1,15,14,13,12,0,10,11,8,9,6,7,4,5,2,3) \\
& (1,15,14,0,12,13,10,11,8,9,6,7,4,5,2,3) \\
& (1,0,14,15,12,13,10,11,8,9,6,7,4,5,2,3)
\end{aligned}
$$

After exchanging 0 and 2 , the second pass is

$$
\begin{aligned}
& (1,2,14,15,12,13,10,11,8,9,6,7,4,5,0,3) \\
& (1,2,14,15,12,13,10,11,8,9,0,7,4,5,6,3) \\
& (1,2,14,15,12,13,0,11,8,9,10,7,4,5,6,3) \\
& (1,2,0,15,12,13,14,11,8,9,10,7,4,5,6,3)
\end{aligned}
$$

After exchanging 0 and 3 , the third pass is

$$
\begin{aligned}
& (1,2,3,15,12,13,14,11,8,9,10,7,4,5,6,0) \\
& (1,2,3,15,12,13,14,11,8,9,10,0,4,5,6,7) \\
& (1,2,3,15,12,13,14,0,8,9,10,11,4,5,6,7) \\
& (1,2,3,0,12,13,14,15,8,9,10,11,4,5,6,7)
\end{aligned}
$$

After exchanging 0 and 4 , the fourth pass is

$$
\begin{aligned}
& (1,2,3,4,12,13,14,15,8,9,10,11,0,5,6,7) \\
& (1,2,3,4,0,13,14,15,8,9,10,11,12,5,6,7)
\end{aligned}
$$

And then one can successively perform the operations to eventually find

$$
(1,2,3,4,5,6,7,0,8,9,10,11,12,13,14,15)
$$

after which 0 will move one unit to the right with each transposition, and $n=15$ is a solution. The general case follows.

Case 1: $n>2$ even: After the first pass, in which 0 is transposed successively with $3,5, \ldots, n-1$, after which 0 is right after $n$, and no other legal transposition can be performed. So $n$ is not a solution in this case.

Case 2: $n=2^{k}-1$ : Denote $N=n+1, R=2^{r},[a: b]=(a, a+1, a+2, \ldots, b)$, and concatenation by a comma. Let $P_{r}$ be the permutation

$$
[1: R-1],(0),[N-R: N-1],[N-2 R: N-R-1], \ldots,[2 R: 3 R-1],[R: 2 R-1]
$$

$P_{r}$ is formed by the blocks $[1: R-1],(0)$, and other $2^{k-r}-1$ blocks of size $R=2^{r}$ with consecutive numbers, beginning with $t R$ and finishing with $(t+1) R-1$, in decreasing order of $t$. Also define $P_{0}$ as the initial permutation.

Then it can be verified that $P_{r+1}$ is obtained from $P_{r}$ after a number of legal transpositions: it can be easily verified that $P_{0}$ leads to $P_{1}$, as 0 is transposed successively with $3,5, \ldots, n-1$, shifting cyclically all numbers with even indices; this is $P_{1}$.

Starting from $P_{r}, r>0,0$ is successively transposed with $R, 3 R, \ldots, N-R$. The numbers $0, N-R, N-3 R, \ldots, 3 R, R$ are cyclically shifted. This means that $R$ precedes 0 , and the blocks become

$$
\begin{gathered}
{[1: R],(0),[N-R+1: N-1],[N-2 R: N-R],[N-3 R+1: N-2 R-1], \ldots} \\
{[3 R+1: 4 R-1],[2 R: 3 R],[R+1: 2 R-1]}
\end{gathered}
$$

Note that the first block and the ones on even positions greater than 2 have one more number and the other blocks have one less number.

Now $0, N-R+1, N-3 R+1, \ldots, 3 R+1, R+1$ are shifted. Note that, for every $i$ th block, $i$ odd greater than 1 , the first number is cyclically shifted, and the blocks become

$$
\begin{gathered}
{[1: R+1],(0),[N-R+2: N-1],[N-2 R: N-R+1],[N-3 R+2: N-2 R-1], \ldots,} \\
{[3 R+1: 4 R-1],[2 R: 3 R+1],[R+2: 2 R-1]}
\end{gathered}
$$

The same phenomenom happened: the first block and the ones on even positions greater than 2 have one more number and the other blocks have one less number. This pattern continues: $0, N-R+u, N-3 R+u, \ldots, R+u$ are shifted, $u=0,1,2, \ldots, R-1$, the first block and the ones on even positions greater than 2 have one more number and the other blocks have one less number, until they vanish. We finish with

$$
[1: 2 R-1],(0),[N-2 R: N-1], \ldots,[2 R: 4 R-1]
$$

which is precisely $P_{r+1}$.

Since $P_{k}=[1: N-1],(0), n=2^{k}-1$ is a solution.

Case 3: $n$ is odd, but is not of the form $2^{k}-1$. Write $n+1$ as $n+1=2^{a}(2 b+1), b \geq 1$, and define $P_{0}, \ldots, P_{a}$ as in the previous case. Since $2^{a}$ divides $N=n+1$, the same rules apply, and we obtain $P_{a}$ :

$$
\left[1: 2^{a}-1\right],(0),\left[N-2^{a}: N-1\right],\left[N-2^{a+1}: N-2^{a}-1\right], \ldots,\left[2^{a+1}: 3 \cdot 2^{a}-1\right],\left[2^{a}: 2^{a+1}-1\right]
$$

But then 0 is transposed with $2^{a}, 3 \cdot 2^{a}, \ldots,(2 b-1) \cdot 2^{a}=N-2^{a+1}$, after which 0 is put immediately after $N-1=n$, and cannot be transposed again. Therefore, $n$ is not a solution. All cases were studied, and so we are done.

Comment: The general problem of finding the number of regular permutations for any $n$ seems to be difficult. A computer finds the first few values

$$
1,2,5,14,47,189,891,4815,29547
$$

which is not catalogued at oeis.org.