Enumeration and Generation of Young Tableaux with Walls: the Density Method
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. This leads to new classes of recurrences, and to 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 uniform random generation and enumeration. It finds its origins in number theory (values of the zeta function, with a Kontsevich-Zagier period point of view) and in poset theory (volume of polytopes). We also apply this approach to describe the asymptotic fluctuations of the limit surface of Young tableaux.
Based on several articles with Philippe Marchal and Michael Wallner.