Enumerating several statistics of r r -Colored Dyck paths with no 𝐝𝐝 \mathbf{dd} -steps having the same colors
2025
Read Enumerating several statistics of r r -Colored Dyck paths with no 𝐝𝐝 \mathbf{dd} -steps having the same colors (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-2506-08407.txt.
Introduction
Yidong Sun, Jinyi Wang, and Xinyu Wang count features of colored Dyck paths, in a mathematics paper from 2025. A Dyck path steps up and down and never drops below its start. Here each down step gets one of a set number of colors, and no two down steps in a row share a color.
The authors count points, up steps, and peaks at each height, plus a special three-step pattern. Counting formulas come from Riordan arrays tied to a weighted generating function for a related path family. Surprising relations in that function yield extra identities. The work enriches the combinatorics of colored lattice paths.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-08407
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Enumerating several statistics of r r -Colored Dyck paths with no 𝐝𝐝 \mathbf{dd} -steps having the same colors Abstract Yidong Sun 1 1 1 Corresponding author: Yidong Sun , Jinyi Wang 2 and Xinyu Wang 3 School of Science, Dalian Maritime University, 116026 Dalian, P.R. China Emails: 1 [email protected], 2 [email protected], 3 [email protected] Abstract An r -colored Dyck path is a Dyck path with all \mathbf{d} -steps having one of r colors in [r]=\{1,2,\dots,r\} . In this paper, we consider several statistics on the set \mathcal{A}_{n,0}^{(r)} of r -colored Dyck paths of length 2n with no two consecutive \mathbf{d} -steps having the same colors. Precisely, the paper studies the statistics “number of points” at level \ell , “number of \mathbf{u} -steps” at level \ell+1 , “number of peaks” at level \ell+1 and “number of \mathbf{udu} -steps” on the set \mathcal{A}_{n,0}^{(r)} . The counting formulas of the first three statistics are established by Riordan arrays related to S(a,b;x) , the weighted generating function of (a,b) -Schröder paths. By a useful and surprising relations satisfied by S(a,b;x) , several identities related to these counting formulas are also described. Keywords : Dyck path; Riordan array; (a,b) -Schröder path; (a,b) -Schröder number. 2000 Mathematics Subject Classification : Primary 05A15; Secondary 05A10, 05A19. 1. Introduction A Dyck path of length 2n is a lattice path from (0,0) to (2n,0) in the first quadrant of the XY -plane and consists of n up-steps \mathbf{u}=(1,1) and n down-steps \mathbf{d}=(1,-1) . See [ 49 , p.204] and [ 18 ] . Let \mathcal{D}_{n} be the set of Dyck paths of length 2n and \mathcal{D}=\bigcup_{n\geq 0}\mathcal{D}_{n} . It is well known [ 48 ] that |\mathcal{D}_{n}|=C_{n}=\frac{1}{n+1}\binom{2n}{n} , the n th Catalan number. An r -colored Dyck path is a Dyck path with all \mathbf{d} -steps having one of r colors in [r]=\{1,2,\dots,r\} . A Motzkin path of length n is a lattice path from (0,0) to (n,0) in the first quadrant of the XY -plane and consists of up-steps \mathbf{u}=(1,1) , down-steps \mathbf{d}=(1,-1) and horizontal-steps \mathbf{h}=(1,0) . A Schröder path of length 2n is a path from (0,0) to (2n,0) in the first quadrant of the XY-plane that consists of up steps \mathbf{u}=(1,1) , down steps \mathbf{d}=(1,-1) and horizontal steps \mathbf{H}=(2,0) . An (a,b) -Dyck path is a weighted Dyck path with \mathbf{u} -steps weighted by 1 , \mathbf{d} -steps in peaks (called \mathbf{ud} -steps) weighted by a and other \mathbf{d} -steps weighted by b . An (a,b) -Motzkin path of length n is a weighted Motzkin path with \mathbf{u} -steps weighted by 1 , \mathbf{h} -steps weighted by a and \mathbf{d} -steps weighted by b . An (a,b) -Schröder path is a weighted Schröder path such that the \mathbf{u} -steps, \mathbf{H} -steps, and \mathbf{d} -steps are weighted respectively by 1,a and b . The weight of a path \mathbf{P} , denoted by w(\mathbf{P}) , is the product of the weight of each step of \mathbf{P} . The weight of a set \mathcal{A} of any weighted paths, denoted by w(\mathcal{A}) , is the sum of the total weights of all paths in \mathcal{A} . Let \mathcal{C}_{n}(a,b),\mathcal{M}_{n}(a,b) and \mathcal{S}_{n}(a,b) be respectively the sets of (a,b) -Dyck paths of length 2n , (a,b) -Motzkin paths of length n and (a,b) -Schröder paths of length 2n . Let C_{n}(a,b) , M_{n}(a,b) and S_{n}(a,b) be their weights with C_{0}(a,b)=M_{0}(a,b)=S_{0}(a,b)=1 respectively. It is known [ 12 ] that C_{n}(a,b),M_{n}(a,b) and S_{n}(a,b) have the explicit formulas: (1.1) \displaystyle C_{n}(a,b)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt\sum_{k=1}^{n}\frac{1}{n}\binom{n}{k-1}\binom{n}{k}a^{k}b^{n-k}, \displaystyle M_{n}(a,b)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt\sum_{k=0}^{n}\binom{n}{2k}C_{k}a^{n-2k}b^{k}, (1.2) \displaystyle S_{n}(a,b)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt\sum_{k=0}^{n}\binom{n+k}{2k}C_{k}a^{n-k}b^{k}, and their generating functions \displaystyle C(a,b;x)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt\sum_{n=0}^{\infty}C_{n}(a,b)x^{n}=\frac{1-(a-b)x-\sqrt{(1-(a-b)x)^{2}-4bx}}{2bx}, \displaystyle M(a,b;x)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt\sum_{n=0}^{\infty}M_{n}(a,b)x^{n}=\frac{1-ax-\sqrt{(1-ax)^{2}-4bx^{2}}}{2bx^{2}}, (1.3) \displaystyle S(a,b;x)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt\sum_{n=0}^{\infty}S_{n}(a,b)x^{n}=\frac{1-ax-\sqrt{(1-ax)^{2}-4bx}}{2bx}, which satisfy the functional equations: \displaystyle C(a,b;x)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt1+(a-b)xC(a,b;x)+bxC(a,b;x)^{2}, \displaystyle M(a,b;x)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt1+axM(a,b;x)+bx^{2}M(a,b;x)^{2}, (1.4) \displaystyle S(a,b;x)\hskip-6.25963pt \displaystyle= \displaystyle\hskip-6.25963pt1+axS(a,b;x)+bxS(a,b;x)^{2}. There are closely relations between C_{n}(a,b) , M_{n}(a,b) and S_{n}(a,b) . Exactly, Chen and Pan [ 12 ] derived the following equivalent relations (1.5) \displaystyle S_{n}(a,b)=C_{n}(a+b,b)=(a+b)M_{n-1}(a+2b,(a+b)b) for n\geq 1 and provided some combinatorial proofs by weighted Dyck, Motzkin and Schröder paths. Other combinatorial proofs of ( 1.5 ) have been given by [ 55 ] using weighted generalized Motzkin paths. When a=b=1 , C_{n}(a,b),M_{n}(a,b) and S_{n}(a,b) reduce to the Catalan number C_{n} [ 18 , 48 ] , the Motzkin number M_{n} [ 1 , 3 , 19 ] and the large Schröder number S_{n} [ 9 , 45 ] respectively. Write C(x),M(x),S(x) instead of C(a,b;x),M(a,b;x) , S(a,b;x) respectively when a=b=1 . Let \varepsilon be the empty path, i.e., the path of length 0 . If both \mathbf{P}_{1} and \mathbf{P}_{2} are of same type (Dyck, Motzkin or Schröder paths), then we define \mathbf{P}_{1}\mathbf{P}_{2} as the concatenation of \mathbf{P}_{1} and \mathbf{P}_{2} . Any non-empty Dyck path \mathbf{P} has a unique first return decomposition [ 4 , 18 ] of the form \mathbf{P}=\mathbf{u}\alpha\mathbf{d}\beta , where \alpha and \beta are two Dyck paths in \mathcal{D} . For any path such as Dyck, Motzkin or Schröder path, a point of a path with ordinate \ell is said to be at level \ell . A step of a path is said to be at level \ell if the ordinate of its endpoint is \ell . By a return step we mean a \mathbf{d} -step at level 0 . A peak (valley) in a path is an occurrence of \mathbf{ud} ( \mathbf{du} ). By the level of a peak (valley) we mean the level of the intersection point of its two steps. Dyck paths that have exactly one return step are said to be primitive . In the literature, many papers deal with the enumeration of Dyck paths or their restricted classes according to different statistics, e.g. peak , valley , pyramid , water capacity , number of \mathbf{udu}^{\prime}s [ 2 , 8 , 14 , 15 , 17 , 18 , 20 , 21 , 22 , 23 , 24 , 29 , 30 , 31 , 34 , 35 , 36 , 39 , 51 , 52 ] , and very important statistics such as area, dinv, bounce of Dyck paths, see for example [ 16 , 25 , 27 , 58 , 59 ] and references therein. Other papers deal with Motzkin paths, Schröder paths or various generalized paths using similar methods [ 3 , 5 , 10 , 13 , 19 , 32 , 38 , 55 , 56 , 57 ] . For instance, the Shapiro’s Catalan triangle [ 40 ] \mathcal{B}=(B_{n,k})_{n\geq k\geq 0} with B_{n,k}=\frac{k+1}{n+1}\binom{2n+2}{n-k} counts the number of points at level k of Dyck paths of length 2n [ 13 ] , or counts the number of peaks at level k+1 of Dyck paths of length 2n+2 [ 13 ] . Note that this triangle forms a well-kown Riordan array [ 53 , 54 ] (C(x)^{2},xC(x)^{2}) . Another example is that the general entry A_{n,k}=\frac{2k+3}{2n+3}\binom{2n+3}{n-k} of the Riordan array [ 53 , 54 ] (C(x)^{3},xC(x)^{2}) counts the number of \mathbf{u} -steps at level k+1 of Dyck paths of length 2n+2 [ 13 ] . Recall that Riordan array [ 37 , 42 , 41 , 43 , 47 ] is an infinite lower triangular matrix \mathscr{D}=(d_{n,k})_{n,k\in\mathbb{N}} such that its k -th column has generating function d(x)h(x)^{k} , where d(x) and h(x) are formal power series with d(0)\neq 0 and