Modular Catalan Numbers
Preprint
Abstract
We introduce the modular Catalan number $C_{n,k}$ which enumerates distinct functions obtained by parenthesizing $x_1*\cdots*x_{n+1}$, where $a*b:=a+e^{2\pi i/k}\,b$. We find restricted families of binary trees and other Catalan objects that are enumerated by $C_{n,k}$. We give a closed formula for $C_{n,k}$ and show that its generating function satisfies a degree $k$ polynomial equation.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Pattern avoidance in binary treesJournal of Combinatorial Theory, Series A, 2010
- Restricted 1-3-2 Permutations and Generalized PatternsAnnals of Combinatorics, 2002
- Order Structure on the Algebra of Permutations and of Planar Binary TreesJournal of Algebraic Combinatorics, 2002
- From Motzkin to Catalan permutationsDiscrete Mathematics, 2000
- Polyominoes and polygons1994