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, \mathbf{1 0}, 11,8,9,0,7,4,5,6,3) \\
& (1,2, \mathbf{1 4}, 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 phenomenon 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.