Multivariate Fuss–Catalan numbers

AbstractCatalan numbers C(n)=1/(n+1)2nn 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)=(n-k)/(n+k)n+kn. 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 B3(n,k,l) that give a 2-parameter distribution of C3(n)=1/(2n+1)3nn, which may be called order-3 Fuss–Catalan numbers, and enumerate ternary trees. The aim of this paper is a study of these integers B3(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 Cp(n)=1/((p-1)n+1)pnn, the number of p-ary trees