Young tableaux with periodic walls: counting with the density method

Cyril Banderier and Michael Wallner

This is the webpage of the article Young tableaux with periodic walls: counting with the density method.

This is our FPSAC 2021 submission:
BanderierWallnerFPSAC2021.pdf

The accompanying Maple session is available here:
PeriodicWallsDensityMethodPackage.mw

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.

Sneak Preview

We consider a generalization of Young tableaux by allowing two consecutive cells to have decreasing values. We put a bold red edge between the cells which are allowed (but not imposed) to be decreasing (we call these edges "walls"), and consider structures where the location of the walls obey some periodicity rules. We will consider several families of Young tableaux with walls.

A Jenga tableau consists of rows of blocks stacked on top of each other such that there are horizontal walls everywhere except at a center column. Here we see a Jenga tableau with 7 rows.

A second class consists of all 2xn Young tableaux with walls built from 2x2 building blocks. We characterize them (except for two cases) with respect to the nature of their counting sequences: simple product, algebraic, hypergeometric, or D-algebraic.