Multivariate Fuss-Catalan numbers

Abstract

Catalan numbers $C(n)=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ enumerate binary trees and Dyck paths. The distribution of paths with respect to their number $k$ of factors is given by ballot numbers $B(n,k)=\frac{n-k}{n+k}\left(\genfrac{}{}{0ex}{}{n+k}{n}\right)$. These integers are known to satisfy simple recurrence, which may be visualised in a ``Catalan triangle'', a lower-triangular two-dimensional array. It is surprising that the extension of this construction to 3 dimensions generates integers $B_3(n,k,l)$ that give a 2-parameter distribution of $C_3(n)=\frac{1}{2n+1}\left(\genfrac{}{}{0ex}{}{3n}{n}\right)$, which may be called order-3 Fuss-Catalan numbers, and enumerate ternary trees. The aim of this paper is a study of these integers $B_3(n,k,l)$. We obtain an explicit formula and a description in terms of trees and paths. Finally, we extend our construction to $p$-dimensional arrays, and in this case we obtain a $(p-1)$-parameter distribution of $C_p(n)=\frac{1}{(p-1)n+1}\left(\genfrac{}{}{0ex}{}{pn}{n}\right)$, the number of $p$-ary trees.

References in corpus (1)

• Ideals and quotients of B-quasisymmetric functions