Séminaire Lotharingien de Combinatoire, 85B.47 (2021), 12 pp.

Cyril Banderier and Michael Wallner

Young Tableaux with Periodic Walls: Counting with the Density Method

Abstract. We consider a generalization of Young tableaux in which we allow some consecutive pairs of cells with decreasing labels, conveniently visualized by a "wall" between the corresponding cells. Some shapes can be enumerated by variants of hook-length type formulas. We focus on families of tableaux (like the so-called "Jenga tableaux") having some periodic shapes, for which the generating functions are harder to obtain. We get some interesting new classes of recurrences, and a surprisingly rich zoo of generating functions (algebraic, hypergeometric, D-finite, differentially-algebraic). Some patterns lead to nice bijections with trees, lattice paths, or permutations. Our approach relies on the density method, a powerful way to perform both random generation and enumeration of linear extensions of posets.

Received: December 1, 2020. Accepted: March 1, 2021. Final version: April 29, 2021.

The following versions are available: