= Solution
Let $a$ be the single entry in the second row of $P$. It lies in $\{2,\ldots,n\}$; the first row is all the other entries in increasing order. Consider the <adjacent transposition> $\sigma=(a-1,a)$, whose word is
$$
1,2,\ldots,a-2,\ a,\ a-1,\ a+1,\ldots,n.
$$
The first $a-1$ entries append in increasing order to the first row. At insertion time $a$, the value $a-1$ bumps $a$ into the second row, creating its only cell. Every later entry appends to the first row. Thus the insertion tableau has second-row entry $a$ and all other entries in the first row, precisely $P$.
The recording tableau also has second-row entry $a$, the time of the unique bump, and all other time labels in increasing first-row order. It too is $P$. Bijectivity of the correspondence therefore gives
$$
\boxed{\operatorname{RSK}^{-1}(P,P)=(a-1,a).}
$$
This includes $n=2,a=2$. It identifies the actual <permutation> without needing a general theorem about <involutions>.
This is <RSK of an adjacent transposition>.
Back to article page
