Combinatorics of Oscillating Tableaux

Abstract

In this paper, we first introduce the RSK algorithm, which gives a correspondence between integer sequences and standard tableaux. Then we introduce Schensted’s theorem and Greene’s theorem that describe how the shape of the standard tableau is determined by the sequence. We list four different bijections constructed by using the RSK insertion. The first one is a bijection between vacillating tableaux and pairs (P, T), where P is a set of ordered pairs and T is a standard tableau. The second one is a bijection between set partitions of [n] and vacillating tableaux. The third one is about partial matchings and up-down tableaux and the final one is from sequences to pairs (T, P), where T is still a standard tableau and P is a special oscillating tableau. We analyze some combinatorial statistics via these bijections.