A schensted algorithm for rim hook tableaux

Dennis W. Stanton, Dennis E. White

Research output: Contribution to journalArticlepeer-review

71 Scopus citations

Abstract

We consider hooks, hook tableaux, rim hooks, and rim hook tableaux where all hooks and rim hooks have length k. Using a rim hook version of the "jeu d'taquin" of Schützenberger and the orientation of a rim hook (its mod k distance from the main diagonal), we give a simple alternative description of the *-diagrams of Robinson. The rim hook Schensted correspondence given by one of us in a previous paper then decomposes into a k-tuple of ordinary Schensted correspondences. This decomposition is used to "lift" the important applications of the ordinary Schensted correspondence to the rim hook Schensted correspondence. These include applications to inverses, increasing and decreasing subsequences, and the Schützenberger evacuation procedure.

Original languageEnglish (US)
Pages (from-to)211-247
Number of pages37
JournalJournal of Combinatorial Theory, Series A
Volume40
Issue number2
DOIs
StatePublished - Nov 1985

Bibliographical note

Funding Information:
* Partially supported by NSF Grant MCS-81-22034 and MCS-81-02237.

Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

Fingerprint Dive into the research topics of 'A schensted algorithm for rim hook tableaux'. Together they form a unique fingerprint.

Cite this