Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: RSK Insertion for Set Partitions and Diagram Algebras. | RSK Insertion for Set Partitions and Diagram Algebras Tom Halverson and Tim Lewandowski Department of Mathematics and Computer Science Macalester College Saint Paul MN 55105 USA halverson@ Submitted Jun 30 2005 Accepted Nov 2 2005 Published Dec 5 2005 Mathematics Subject Classifications 05A19 05E10 05A18 In honor of Richard Stanley on his 60th birthday. Abstract We give combinatorial proofs of two identities from the representation theory of the partition algebra CAk n n 2k. The first is nk Tx f xmf where the sum is over partitions A of n fx is the number of standard tableaux of shape A and mk is the number of vacillating tableaux of shape A and length 2k. Our proof uses a combination of Robinson-Schensted-Knuth insertion and jeu de taquin. The second identity is B 2k Tx mf 2 where B 2k is the number of set partitions of 1 . 2kg. We show that this insertion restricts to work for the diagram algebras which appear as subalgebras of the partition algebra the Brauer Temperley-Lieb planar partition rook monoid planar rook monoid and symmetric group algebras. 1 Introduction Two fundamental identities in the representation theory of the symmetric group Sk are a nk X fXdx and b k X fX 2 C1-1 Ah-k X k e X n where A varies over partitions of the integer k of length A n fx is the number of standard Young tableaux of shape A and dx is the number of column strict tableaux of shape A with entries from 1 . n . The Robinson-Schensted-Knuth RSK insertion algorithm provides a a bijection between sequences i1 . ik 1 ij n and pairs Px Qx consisting of a standard Young tableau Px of shape A and a column strict tableau Research supported in part by National Science Foundation Grant DMS0401098. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2 2005 R24 1 Qx of shape A thus providing a combinatorial proof of . If we restrict i1 . ik to be a permutation of 1 . k then Qx is a standard tableau and we have a proof of . Identity comes from .
