Combinatorics of three-Catalan numbers and some positivities

Boualam Rezig, Moussa Ahmia · 2025

Read Combinatorics of three-Catalan numbers and some positivities by Boualam Rezig, Moussa Ahmia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-03615.txt.

Introduction

Boualam Rezig and Moussa Ahmia introduce the three-Catalan triangle, a new array in the Catalan family of counting sequences. Their 2025 paper sets out the three-Catalan numbers with a recurrence relation and a combinatorial reading of what they count. Catalan structures appear across combinatorics, from tree shapes to bracketings, and variants often carry hidden order.

Two shape results follow. The three-Catalan numbers themselves are log convex, meaning each term sits at or above the geometric mean of its neighbors. The rows of the triangle, read as sequences, are log concave instead. The authors present the pair of results as the triangle's first properties, inviting links to other known triangles.

Catalog record

CREATORBoualam Rezig, Moussa Ahmia
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-03615

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Combinatorics of three-Catalan numbers and some positivities Boualam Rezig, Moussa Ahmia Abstract . We introduce the three-Catalan triangle, highlighting the three-Catalan numbers along with their recurrence relation and combinatorial interpretation, which allows us to establish their log-convexity. Additionally, we prove that the rows of the three-Catalan triangle form a log-concave sequence. 2010 Mathematics Subject Classification 05A05, 05A15, 05A19, 05A30. 1. Introduction The Catalan numbers C_{n} have a deep historical lineage, tracing back to Euler and Catalan, with broad generalizations that enhance their combinatorial significance. They play a fundamental role in modern combinatorics, algebra, and computer science, counting numerous combinatorial structures. Defined by the formula C_{n}:=\binom{2n}{n}-\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)!n!},\ \ \ n\geq 0, these numbers were formally introduced in 1838 by the Belgian mathematician Eugène Charles Catalan in connection with counting nested parenthetical sequences and polygon triangulations, securing his name in their legacy. However, Segner had already identified them in 1758 in his study of binary trees and convex polygon triangulations. Earlier still, in 1751 , Euler investigated the number of ways to divide an n -sided convex polygon into triangles using non-crossing diagonals, deriving a recurrence relation that corresponds to the Catalan numbers, though he did not name them. Later, other mathematicians, including Bertrand and Kirkman, rediscovered them in various combinatorial contexts. The Catalan numbers have several combinatorial interpretations [ 16 , 17 , 23 ] . Notably, they are associated with binary trees and Dyck paths: • The Catalan number represents the number of rooted plane trees with n edges (see [ 17 ] for further details). • The Catalan number also counts the number of Dyck paths from (0,0) to (2n,0) using steps (1,1) and (1,-1) , while staying above the x -axis. Equivalently, it represents the number of lattice paths from (0,0) to (n,n) with steps (0,1) and (1,0) , remaining below or on the line y=x . Over time, several generalizations of Catalan numbers have been developed. (1) Super-Catalan numbers (or Schröder numbers): These numbers count paths that are less restricted than those counted by the standard Catalan numbers. They follow the recurrence: S_{n}=S_{n-1}+\sum_{k=1}^{n-1}S_{k}S_{n-k}. They generalize the number of ways to divide a polygon into parts using non-intersecting diagonals. (2) m -Catalan numbers (or Higher-order Catalan numbers): are a generalization that count the number of ways to divide an (mn+1) -gon into n regions using non-crossing diagonals: C_{n}^{(m)}=\frac{1}{(m-1)n+1}\binom{mn}{n}. (3) Fuss–Catalan numbers (or Raney numbers) [ 22 ] : These are a p -ary generalization: C_{n}^{(p)}=\frac{1}{pn+1}\binom{(p+1)n}{n}. They count p -ary trees and appear in higher-dimensional lattice paths. (4) q -Catalan numbers [ 11 ] : These incorporate a parameter q to keep track of extra structure (e.g., weighted combinatorial objects like lattice paths with area constraints): C_{q}(n)=\frac{1}{[n+1]_{q}}{2n\brack n}_{q}=\frac{[2n]_{q}!}{[n+1]_{q}![n]_{q}!}, where [k]_{q}!=[1]_{q}\cdots[k]_{q} is q -factorial number with [k]_{q}=1+q+\cdots+q^{k-1} . (5) Higher-dimensional Catalan numbers (or d -dimensional Catalan numbers) [ 10 ] : Appearing in algebraic topology and category theory, these numbers generalize Catalan numbers to higher dimensions, such as the Tamari lattice: C_{d}(n)=(dn)!\prod_{i=0}^{d-1}\frac{i!}{(n+i)!},\ \ \ d=2,3,\ldots which for d=2 clearly reduce the conventional Catalan numbers. (6) s -Catalan number [ 8 ] : By the way, there is another generalization of Catalan numbers using bi s nomial coefficients \binom{n}{k}_{s} [ 6 , 7 ] which are defined as the k -th coefficient in the expansion (1+x+\cdots+x^{s})^{n}=\sum_{k=0}^{sn}\binom{n}{k}_{s}x^{k}. This generalization, introduced by Belbachir and Igueroufa [ 8 ] for odd s , is denoted by C_{n}^{(s)} and referred to as the s -Catalan number , given by (1) C_{n}^{(s)}:=\binom{2n}{sn}_{s}-\binom{2n}{sn+1}_{s}, where \binom{2n}{sn}_{s} is the central bi s nomial coefficients. Linz [ 20 ] later extended the definition of s -Catalan numbers to all positive integers s and provided a combinatorial interpretation of these numbers in terms of Littlewood–Richardson coefficients. Ghemit and Ahmia [ 18 ] further studied the two-Catalan numbers C_{n}^{(2)} , establishing a combinatorial interpretation based on a subset of vertically constrained Motzkin-like paths introduced by Irvine et al [ 19 ] . This approach ultimately led to proving the log-convexity of these numbers. In this paper, we focus on the specific case of s=3 for the s -Catalan numbers, as defined by relation ( 1 ), since the general case is too complex to analyze using the techniques employed here. In Section 2 , we introduce the coefficients of the three-Catalan triangle, referring to the first column of this triangle as the three-Catalan numbers. We then derive a recurrence relation and provide a combinatorial interpretation of these coefficients through a set of vertically constrained paths. Leveraging this interpretation, we establish the log-convexity of two-Catalan numbers in Section 3 . Finally, in Section 4 , we demonstrate that the rows of the three-Catalan triangle form a log-concave sequence. 2. Definition and path interpretation of three-Catalan numbers This section focuses on defining three-Catalan numbers and presenting combinatorial formulas, including a recurrence relation and interpretations through lattice paths. Since the s -Catalan number is defined as the difference between two consecutive terms of the central bi s nomial coefficient, we first examine the latter, which naturally generalizes binomial coefficients (see, e.g., [ 7 ] ). Defined for integers s\geq 1 and n\geq 0 , with k=0,1,\ldots,sn , the bi s nomial coefficient \binom{n}{k}_{s} represents the k th coefficient in the expansion: (2) (1+x+\cdots+x^{s})^{n}=\sum_{k\in\mathbb{Z}}\binom{n}{k}_{s}x^{k}, where \binom{n}{k}_{s}=0 for k>sn or k<0 . These coefficients satisfy several fundamental properties, including: • Symmetry: (3) \binom{n}{k}_{s}=\binom{n}{sn-k}_{s}. • Longitudinal recurrence: (4) \binom{n}{k}_{s}=\sum_{j=0}^{s}\binom{n-1}{k-j}_{s}. • Absorption identity: (5) k\binom{n}{k}_{s}=n\sum_{j=1}^{s}j\binom{n-1}{k-j}_{s}. These coefficients, similar to standard binomial coefficients, follow the construction of Pascal’s triangle, referred to as the ” s -Pascal triangle.” The initial values of the s -Pascal triangle for s=3 can be found in the OEIS database as A008287 [ 24 ] . \begin{array}[]{cccccccccccccc}n\backslash k&0&1&2&3&4&5&6&7&8&9&10&11&12\\ 0&1&&&&&&&&&&&&\\ 1&1&1&1&1&&&&&&&&&\\ 2&1&2&3&4&3&2&1&&&&&&\\ 3&1&3&6&10&12&12&10&6&3&1&&&\\ 4&1&4&10&20&31&40&44&40&31&20&10&4&1\end{array} Table 1: Triangle of quadrinomial coefficients: s=3 . For further properties of bi s nomial coefficients, see [ 7 , 12 , 6 ] . The first significant result on the unimodality of bi s nomial coefficients was given by Belbachir and Szalay [ 9 ] , who demonstrated that any ray crossing Pascal’s triangle forms a unimodal sequence. Additionally, in [ 1 , 3 , 4 , 5 , 2 ] , the authors explored various properties of bi s nomial coefficients, including strong log-convexity, unimodality, and the preservation of log-convexity and log-concavity. Now, we stat by the following definition. Definition 2.1 . Let n and k be positive integers. The coefficients of the three-Catalan triangle are defined by C_{n,k}^{(3)}:=\binom{2n}{3n+k}_{3}-\binom{2n}{3n+k+1}_{3}, for 0\leq k\leq 3n . Specifically, for k=0 , these coefficients are known as the three-Catalan numbers , denoted by C_{n}^{(3)} , C_{n}^{(3)}:=C_{n,0}^{(3)}=\binom{2n}{3n}_{3}-\binom{3n}{3n+1}_{3}, where \binom{2n}{3n}_{3} represents the central quadrinomial coefficient. This definition leads to the following key proposition. Proposition 2.2 . The coefficients of the three-Catalan triangle satisfy the recurrence relations: (6) \displaystyle C_{n+1,0}^{(3)}=C_{n,0}^{(3)}+C_{n,1}^{(3)}+C_{n,2}^{(3)}+C_{n,3}^{(3)}, (7) \displaystyle C_{n+1,1}^{(3)}=C_{n,0}^{(3)}+3C_{n,1}^{(3)}+3C_{n,2}^{(3)}+2C_{n,3}^{(3)}+C_{n,4}^{(3)}, (8) \displaystyle C_{n+1,2}^{(3)}=C_{n,0}^{(3)}+3C_{n,1}^{(3)}+4C_{n,2}^{(3)}+3C_{n,3}^{(3)}+2C_{n,4}^{(3)}+C_{n,5}^{(3)}, (9) \displaystyle C_{n+1,k}^{(2)}=C_{n,k-3}^{(3)}+2C_{n,k-2}^{(3)}+3C_{n,k-1}^{(3)}+4C_{n,k}^{(3)}+3C_{n,k+1}^{(3)}+2C_{n,k+2}^{(3)}+C_{n,k+3}^{(3)},\text{\ for\ }k\geq 3. These relations hold with the initial condition C_{0,0}^{(3)}=1 and C_{n,k}^{(3)}=0 unless 3n\geq k\geq 0 . Proof. Using Definition 2.1 and applying the recurrence relation ( 4 ) twice to the left-hand side of ( 9 ), we obtain, for k\geq 3 , \displaystyle C_{n+1,k}^{(3)} \displaystyle=\binom{2n+2}{3n+k+3}_{3}-\binom{2n}{3n+k+4}_{3}=\binom{2n+1}{3n+k}_{3}-\binom{2n+1}{3n+k+4}_{3} \displaystyle=\binom{2n}{3n+k-3}_{3}+\binom{2n}{3n+k-2}_{3}+\binom{2n}{3n+k-1}_{3}+\binom{2n}{3n+k}_{3} (10) \displaystyle\quad-\binom{2n}{3n+k+1}_{3}-\binom{2n}{3n+k+2}_{3}-\binom{2n}{3n+k+3}_{3}-\binom{2n}{3n+k+4}_{3} \displaystyle=C_{n,k-3}^{(3)}+2C_{n,k-2}^{(3)}+3C_{n,k-1}^{(3)}+4C_{n,k}^{(3)}+3C_{n,k+1}^{(3)}+2C_{n,k+2}^{(3)}+C_{n,k+3}^{(3)}. To prove ( 7 ), ( 8 ), and ( 9 ), we apply the symmetry property (

Read the complete text