Catalan numbers, their generalization, and their uses (Q1174258)

The authors are concerned with four enumeration problems all involving the numbers \(f(p,n)=(pn)!/n!(pn-n+1)!\) for positive integers \(p-1\) and \(n\). (1) Let \(a(p,n)\) be the number of planted plane trees having exactly \(n\) vertices with out-degree \(n\). (2) Let \(b(p,n)\) be the number of ways of associating \(n\) applications of a \(p\)-ary operation. (3) Let \(c(p,n)\) be the number of ways of subdividing a convex \((pn-n+2)\)-gon into \(n(p+1)\)-gons using \(n-1\) non-intersecting diagonals. (4) Let \(d(p,n)\) be the number of lattice paths from (0,0) to \((n,pn-n)\) where each step of the path is to the right or upward to an adjacent lattice point, and all points of the path are on or below the line \(y=(p-1)x\). The authors could have added: (5) Let \(e(p,n)\) be the number of binary sequences \((b_ 1,b_ 2,\dots)\) consisting of \(n\) 1's and \(pn-n\) 0's such that \(b_ 1+b_ 2+\cdots+b_ k p\) is at least \(k\) for \(k=1,2,\dots,n\). Using injections between the various sets involved, and solving one of the problems using generating functions, one can show that \(a(p,n)=b(p,n)=c(p,n)=d(p,n)=e(p,n)=f(p,n)\) for all positive integers \(p- 1\) and \(n\). Besides describing this result, the authors discuss more detailed problems involving lattice paths restricted to special regions.