Séminaire Lotharingien de Combinatoire, 91B.68 (2024), 12 pp.
Sergi Elizalde and Alejandro B. Galván
Combinatorial Properties of Triangular Partitions
Abstract.
A triangular partition is a partition whose Ferrers diagram can be separated from its complement (as a subset of N2) by a straight line. Having their origins in number theory and computer vision, triangular partitions have been studied from a combinatorial perspective by Corteel et al. under the name plane corner cuts, and more recently by Bergeron and Mazin in the context of algebraic combinatorics. Here we derive new enumerative, geometric, and algorithmic properties of such partitions.
We give a new characterization of triangular partitions and the cells that can be added or removed while preserving the triangular condition, and use it to describe the Möbius function of the restriction of Young's lattice to triangular partitions.
We obtain a formula for the number of triangular partitions whose Young diagram fits inside a square, deriving a new proof of Lipatov's enumeration theorem for balanced words.
Finally, we present an algorithm that generates all the triangular partitions of a given size, which is significantly more efficient than previous ones and allows us to compute the number of triangular partitions of size up to 105.
Received: November 15, 2023.
Accepted: February 15, 2024.
Final version: April 1, 2024.
The following versions are available: