RSK Insertion for Set Partitions and Diagram Algebras

We give combinatorial proofs of two identities from the representation theory of the partition algebra $C{A}_k(n),n\ge 2k$. The first is $n^k = \sum_\lambda f^\lambda m_k^\lambda$,wherethesumisoverpartitions$\lambda$of$n$,$f^\lambda$isthenumberofstandardtableauxofshape$\lambda$,and$m_k^\lambda$isthenumberof\mathrm{"}vacillatingtableaux\mathrm{"}ofshape$\lambda$ and length $2k$. Our proof uses a combination of Robinson-Schensted-Knuth insertion and jeu de taquin. The second identity is $B(2k) = \sum_\lambda (m_k^\lambda)^2$,where$B(2k)$isthenumberofsetpartitionsof${1, >…, 2k}$. 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.