Korean J. Math. Vol. 24 No. 3 (2016) pp.469-487
DOI: https://doi.org/10.11568/kjm.2016.24.3.469

Generalization of the Schensted algorithm for rim hook tableaux

Article Sidebar

PDF
Published: Sep 30, 2016
Keywords:
partition, hook, rim hook, generalized hook permutation, rim hook tableau, semistandard rim hook tableau, Schensted algorithm
Mathematics Subject Classification:
05E10

Main Article Content

Jaejin Lee
Department of Mathematics Hallym University Chunchon 24252, Korea

Abstract

In [6] Schensted constructed the Schensted algorithm, which gives a bijection between permutations and pairs of standard tableaux of the same shape. Stanton and White [8] gave analog of the Schensted algorithm for rim hook tableaux. In this paper we give a generalization of Stanton and White's Schensted algorithm for rim hook tableaux. If $k$ is a fixed positive integer, it shows a one-to-one correspondence between all generalized hook permutations $\mathcal H$ of size $k$ and all pairs $(P,Q)$, where $P$ and $Q$ are semistandard $k$-rim hook tableaux and $k$-rim hook tableaux of the same shape, respectively.


Article Details

References

[1] A. Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), 320–328. Google Scholar

[2] D. E. Knuth, Sorting and Searching; The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley, Mass. Google Scholar

[3] D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727. Google Scholar

[4] J. Lee, A Schensted algorithm for shifted rim hook tableaux, J. Korean Math. Soc. 31 (1994), 179–203. Google Scholar

[5] B. E. Sagan, Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley, J. Combin. Theory Ser. A 45 (1987), 62–103. Google Scholar

[6] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191. Google Scholar

[7] B. Sagan and R. Stanley, Robinson-Schensted algorithms for skew tableaux, J. Combin. Theory Ser. A 55 (1990), 161–193. Google Scholar

[8] D. W. Stanton and D. E. White, A Schensted algorithm for rim hook tableaux, J. Combin. Theory Ser. A 40 (1985), 211–247. Google Scholar

[9] D. E. White, A bijection proving orthogonality of the characters of Sn, Advances in Math. 50 (1983), 160–186. Google Scholar

[10] D. R. Worley, A Theory of Shifted Young Tableaux, Ph. D. thesis (1984), M.I.T. Google Scholar