A new generalization of the Narayana numbers inspired by linear operators on associative $d$-ary algebras

Abstract

We introduce and study a generalization of the Narayana numbers $N_d(n,k)=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)\left(\genfrac{}{}{0ex}{}{n+(n-k)(d-2)+1}{k}\right)$ for integers $d\ge 2$ and $n,k\ge 0$. This two-parameter array extends the classical Narayana numbers ($d=2$) and yields a $d$-ary analogue of the Catalan numbers $C_d(n)={\sum }_{k=0}^n{N}_d(n,k)$. We give nine combinatorial interpretations of $N_d(n,k)$ that unify and generalize known combinatorial interpretations of the Narayana numbers and $C_3(n)$ in the literature. In particular, we show that $N_d(n,k)$ counts a natural class of operator monomials over a $d$-ary associative algebra, thereby extending a result of Bremner and Elgendy for the binary case. We also construct explicit bijections between these monomials and several families of classic combinatorial objects, including Schröder paths, Dyck paths, rooted ordered trees, and $231$-avoiding permutations.