Permutations whose reverse shares the same recording tableau in the RSK correspondence

Abstract

The RSK correspondence is a bijection between permutations and pairs of standard Young tableaux with identical shape, where the tableaux are commonly denoted $P$ (insertion) and $Q$ (recording). It has been an open problem to demonstrate $$|\{w\in {\mathfrak{S}}_n|Q(w)=Q(w^r)\}|=\{\begin{array}{ll}{2}^{\frac{n-1}{2}}\left(\genfrac{}{}{0ex}{}{n-1}{\frac{n-1}{2}}\right)& n\text{ odd}\\ 0& n\text{ even}\end{array},$$ where $w^r$ is the reverse permutation of $w$. First we show that for each $w$ where $Q(w)=Q(w^r)$ the recording tableau $Q(w)$ has a symmetric hook shape and satisfies a certain simple property. From these two results, we succeed in proving the desired identity.

arXiv comment14 pages, 4 figures