Return to Answer

Added I finally came round to looking what Knuth says about this exactly. His 1970 paper (Pacific J. Math, 34(3)) mentions symmetry, but not reversal of the insertion order. Hower in The Art of Computer Programming Vol 3. (1975) one finds in section 5.1.4 the following

Added I finally came round to looking what Knuth says about this exactly. His 1970 paper (Pacific J. Math, 34(3)) mentions symmetry, but not reversal of the insertion order. However, in The Art of Computer Programming Vol 3. (1975) one finds in section 5.1.4 the following

First, just for clarifty about the question, the Reifegerste preprint dates from September 2003, her paper was published in 2004, and Jacob Post's thesis is from 2009.

Here Theorem A states the Robinson-Schensted coreespondence for permutations, and Algorithm S (Delete corner element) is one step of evacuation. This is indeed the "symmetric form of the lemma" mentioned above.

First, just for clarity about the question, the Reifegerste preprint dates from September 2003, her paper was published in 2004, and Jacob Post's thesis is from 2009.

Here Theorem A states the Robinson-Schensted correspondence for permutations, and Algorithm S (Delete corner element) is one step of evacuation. So this is indeed the "symmetric form of the lemma" mentioned above.

Theorem C (M.P. Schützenberger). _If $P$ is the tableau formed by the construction of Theorem A from the permutation $a_1~a_2~\ldots~a_n$, and if $a_i=\min\{ a_1~a_2,\ldots,a_n\}$, then Algorithm S changes $P$ into the tableau corresponding to $a_1~\ldots a_{i-1}~a_{i+1}\ldots~a_n$.

Theorem C (M.P. Schützenberger). If $P$ is the tableau formed by the construction of Theorem A from the permutation $a_1~a_2~\ldots~a_n$, and if $a_i=\min\{ a_1~a_2,\ldots,a_n\}$, then Algorithm S changes $P$ into the tableau corresponding to $a_1~\ldots a_{i-1}~a_{i+1}\ldots~a_n$.