1. Combinatorial properties of Catalan pairs
- Author
-
Simone Rinaldi, Luca Ferrari, Filippo Disanto, and Renzo Pinzani
- Subjects
Discrete mathematics ,Mathematics::Combinatorics ,Catalan numberspartially ordered setsenumeration ,Catalan numbers ,enumeration ,partially ordered sets ,Component (thermodynamics) ,Applied Mathematics ,Characterization (mathematics) ,language.human_language ,Catalan number ,Combinatorics ,language ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Catalan ,Partially ordered set ,Axiom ,Mathematics - Abstract
We define the notion of a Catalan pair, which is a pair of (strict) order relations ( S , R ) satisfying certain axioms. We show that Catalan pairs of size n are counted by Catalan numbers. We study some combinatorial properties of the relations R and S. In particular, we show that the second component R uniquely determines the pair, and we give a characterization of the poset R in terms of forbidden configurations. We also propose some generalizations of Catalan pairs arising from the modification of one of the axioms.
- Published
- 2009