Multivariate Fuss-Catalan numbers

DOI10.1016/J.DISC.2007.08.100MaRDI QIDQ942097zbMATH OpenOpenAlexDBLPWikidataFDO

Authors J.-C. Aval

Publication date 4 September 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.0906

zbMATH Keywords

ballot numbersCatalan numbersstatistics on paths and trees

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Abstract: Catalan numbers $C(n)=frac1n+12nchoosen$ 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)=fracn-kn+kn+kchoosen$. 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)=frac12n+13nchoosen$, 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)=frac1(p-1)n+1pnchoosen$, the number of $p$-ary trees.

Review text

The \textit{ballot numbers}, \(B(n,k)\), of which the sums for fixed \(k\) are the Catalan numbers, are defined for integers \(n>0\), \(k\geq0\) by \(B(1,0)=1\); \(\forall k\geq n\), \(B(n,k)=0\); and a recursive formula equivalent to \(B(n,k) = B(n-1,k)+B(n,k-1)\). The author generalizes to a 3-dimensional analogue, \(B_3(n,k,\ell)\), and beyond.

Recommendations

• Enumeration via ballot numbers
• Super ballot numbers
• The Ballot Problem Revisited
• Catalan's trapezoids
• scientific article; zbMATH DE number 4189736

Cites work

• A Solomon descent theory for the wreath products G\wr\mathfrak S_n
• Andre's reflection proof generalized to the many-candidate ballot problem
• Catalan numbers, their generalization, and their uses
• ECO:a methodology for the enumeration of combinatorial objects
• scientific article; zbMATH DE number 981696 (Why is no real title available?)
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 3448641 (Why is no real title available?)
• scientific article; zbMATH DE number 3405871 (Why is no real title available?)
• scientific article; zbMATH DE number 2246193 (Why is no real title available?)
• Ideals and quotients of \(B\)-quasisymmetric polynomials
• Super ballot numbers
• The cycle lemma and some applications
• The Riordan group

Cited in

(35)

• On a generalization of polynomials in the ballot problem
• Super ballot numbers
• A family of Bell transformations
• Combinatorial proofs of some properties of tangent and Genocchi numbers
• Enumerations of rational non-decreasing Dyck paths with integer slope
• Quot schemes of curves and surfaces: virtual classes, integrals, Euler characteristics
• Evaluations of some Euler-Apéry-type series
• Pattern-restricted permutations composed of 3-cycles
• Exceptional and modern intervals of the Tamari lattice
• Lattice paths and branched continued fractions. II: Multivariate Lah polynomials and Lah symmetric functions
• Dynamic survival bias in optimal stopping problems
• Some properties of the Fuss-Catalan numbers
• Some new binomial sums related to the Catalan triangle
• Some combinatorial interpretations and applications of Fuss-Catalan numbers
• Some geometric properties of analytic series whose coefficients are reciprocal of Fuss-Catalan numbers
• A ballot number formulary.
• Enumerations of plane trees with multiple edges and Raney lattice paths
• Logarithmically complete monotonicity of Catalan-Qi function related to Catalan numbers
• On the complex-type Catalan transform of the \(k\)-Fibonacci numbers
• Three identities of the Catalan-Qi numbers
• Enumeration and asymptotic formulas for rectangular partitions of the hypercube
• Lagrange inversion
• Injectively \(k\)-colored rooted forests
• Lattice Paths and Branched Continued Fractions: An Infinite Sequence of Generalizations of the Stieltjes–Rogers and Thron–Rogers Polynomials, with Coefficientwise Hankel-Total Positivity
• Several identities and relations related to q-analogues of Pochhammer k-symbol with applications to Fuss-Catalan-Qi numbers
• On locally constructible spheres and balls
• A new parallel solver suited for arbitrary semilinear parabolic partial differential equations based on generalized random trees
• Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
• Determinants of Toeplitz-Hessenberg matrices with Fuss-Catalan entries
• Some formulas related to Pochhammer k -symbol and Fuss–Catalan–Qi numbers
• Scalable pattern matching in computation graphs
• A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode
• Several formulas and identities related to the Pochhammer k-symbol and application to a case of the Fuss-Catalan-Qi numbers
• Logarithmically complete monotonicity of a function related to the Catalan-Qi function
• On directed lattice paths with vertical steps

This page was built for publication: Multivariate Fuss-Catalan numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q942097)