Modular Catalan numbers

详细信息    查看全文

• 作者：Nickolas Hein^a ; ^{nhein@benedictine.edu} ; Jia Huang^b ; ^{huangj2@unk.edu}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：197-218
• 全文大小：562 K
• 卷排序：61

文摘

The Catalan number CnCn enumerates parenthesizations of x0∗⋯∗xnx0∗⋯∗xn where ∗∗ is a binary operation. We introduce the modular Catalan number Ck,nCk,n to count equivalence classes of parenthesizations of x0∗⋯∗xnx0∗⋯∗xn when ∗∗ satisfies a kk-associative law generalizing the usual associativity. This leads to a study of restricted families of Catalan objects enumerated by Ck,nCk,n with emphasis on binary trees, plane trees, and Dyck paths, each avoiding certain patterns. We give closed formulas for Ck,nCk,n with two different proofs. For each n≥0n≥0 we compute the largest size of kk-associative equivalence classes and show that the number of classes with this size is a Catalan number.