
doi: 10.1007/bf03024089
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.
lattice paths, enumeration problems, Other combinatorial number theory, generating functions, Exact enumeration problems, generating functions, Catalan numbers
lattice paths, enumeration problems, Other combinatorial number theory, generating functions, Exact enumeration problems, generating functions, Catalan numbers
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 143 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
