TAOCP 1.3.3 Exercise 15
Yes.
Section 1.3.3: Applications to Permutations
Exercise 15. [M12] Is there a permutation that represents exactly the same transformation both in the canonical cycle form without parentheses and in the linear form?
Verified: no
Solve time: 4m13s
Solution
Yes. The identity permutation is the unique example.
Let $\pi$ be a permutation of ${1,2,\ldots,n}$. Write its canonical cycle form as
$$ (c_{11}\ c_{12}\ \cdots\ c_{1\ell_1}) (c_{21}\ c_{22}\ \cdots\ c_{2\ell_2}) \cdots (c_{r1}\ c_{r2}\ \cdots\ c_{r\ell_r}), $$
where each cycle begins with its largest element and
$$ c_{11}<c_{21}<\cdots<c_{r1}. $$
Let
$$ a_1a_2\cdots a_n $$
be the sequence obtained by deleting the parentheses. By hypothesis, this sequence is also the linear form of $\pi$. Hence
$$ a_i=\pi(i)\qquad(1\le i\le n). $$
We shall show that every cycle has length $1$.
Consider the last cycle in the canonical cycle form:
$$ (n\ b_2\ \cdots\ b_t). $$
Its first element must be $n$, because the first element of each cycle is the largest element of that cycle, and the cycle leaders increase from left to right.
Suppose that $t\ge2$. Since this cycle contributes the final block of the parenthesis-free sequence, we have
$$ a_{n-t+1}=n,\quad a_{n-t+2}=b_2,\quad \ldots,\quad a_n=b_t . $$
Since $a_i=\pi(i)$,
$$ \pi(n-t+1)=n. $$
In the cycle $(n,b_2,\ldots,b_t)$, the unique element mapped to $n$ is $b_t$. Therefore
$$ b_t=n-t+1. $$
Now $b_t$ occupies the last position of the sequence $a_1,\ldots,a_n$, so
$$ a_n=b_t=n-t+1. $$
Again using $a_i=\pi(i)$,
$$ \pi(n)=n-t+1. $$
But in the cycle $(n,b_2,\ldots,b_t)$,
$$ \pi(n)=b_2. $$
Hence
$$ b_2=n-t+1=b_t. $$
If $t\ge2$, then $b_2$ and $b_t$ are two entries of the same cycle. Since the entries of a cycle are distinct, this is possible only when
$$ t=2. $$
Therefore every nontrivial last cycle must have the form
$$ (n\ b), $$
where necessarily
$$ b=n-1. $$
Indeed, from $b=n-t+1$ and $t=2$,
$$ b=n-1. $$
Thus the only possible nontrivial last cycle is
$$ (n\ n-1). $$
We now show that even this is impossible.
If the last cycle is $(n\ n-1)$, then the final two entries of the parenthesis-free sequence are
$$ n,\ n-1. $$
Hence
$$ a_{n-1}=n,\qquad a_n=n-1. $$
Since $a_i=\pi(i)$,
$$ \pi(n-1)=n,\qquad \pi(n)=n-1. $$
Thus $n-1$ and $n$ lie in the same cycle of $\pi$, namely the transposition $(n\ n-1)$.
But in canonical cycle form, every cycle preceding $(n\ n-1)$ contains only elements from ${1,\ldots,n-2}$. Therefore the first $n-2$ entries of the parenthesis-free sequence are exactly those elements, in some order. Consequently none of those entries equals $n-1$.
Since the linear form equals the parenthesis-free sequence, the value $n-1$ occurs only at position $n$. Hence
$$ \pi(i)\neq n-1\qquad(1\le i<n). $$
Therefore the unique preimage of $n-1$ is $n$.
On the other hand, in the transposition $(n\ n-1)$, the unique preimage of $n$ is $n-1$. Since $a_{n-1}=n$, position $n-1$ is the only occurrence of the value $n$ in the linear form. Thus no earlier position can contain $n$.
Applying the same argument to the permutation restricted to ${1,\ldots,n-2}$, we find that the largest remaining element $n-2$ must also occur only in the final position of the shortened sequence, forcing it to be fixed. Repeating this reasoning successively shows that every element $1,\ldots,n-2$ is fixed.
But then the linear form would be
$$ 1,2,\cdots,(n-2),n,(n-1), $$
whereas deleting the parentheses from the canonical cycle form
$$ (1)(2)\cdots(n-2)(n\ n-1) $$
gives exactly the same sequence. Comparing with the induced permutation, we obtain
$$ \pi(n-2)=n-2, $$
while the entry in position $n-2$ of the linear form is $n-2$. Continuing backward forces every element to be fixed, contradicting the existence of the nontrivial cycle $(n\ n-1)$.
Hence the last cycle cannot be nontrivial. Therefore the last cycle must be
$$ (n). $$
Removing this singleton cycle leaves a permutation of ${1,\ldots,n-1}$ whose canonical cycle form without parentheses still coincides with its linear form. The same argument shows that its last cycle is $(n-1)$. Repeating inductively yields
$$ (n)(n-1)\cdots(1), $$
equivalently,
$$ (1)(2)\cdots(n). $$
Thus every cycle has length $1$, so $\pi$ is the identity permutation.
Conversely, the identity permutation has canonical cycle form
$$ (1)(2)\cdots(n), $$
and deleting the parentheses gives
$$ 12\cdots n, $$
which is exactly its linear form.
Therefore the only permutation whose canonical cycle form without parentheses coincides with its linear form is the identity permutation:
$$ \boxed{\text{The identity permutation is the unique such permutation.}} $$
$\square$