Set-Valued Tableaux & Generalized Catalan Numbers

Document Type

Article

Publication Date

3-8-2018

Abstract

Standard set-valued Young tableaux are a generalization of standard Young tableaux in which cells may contain more than one integer, with the added conditions that every integer at position (i, j) must be smaller than every integer at positions (i, j + 1) and (i+ 1, j). This paper explores the combinatorics of standard setvalued Young tableaux with two-rows, and how those tableaux may be used to provide new combinatorial interpretations of generalized Catalan numbers. New combinatorial interpretations are provided for the two-parameter Fuss-Catalan numbers (Raney numbers), the rational Catalan numbers, and the solution to the so-called “generalized tennis ball problem”. Methodologies are then introduced for the enumeration of standard set-valued Young tableaux, prompting explicit formulas for the general two-row case. The paper closes by drawing a bijection between arbitrary classes of two-row standard set-valued Young tableaux and collections of two-dimensional lattice paths that lie weakly below a unique maximal path.

Share

COinS