Meanders and Dyck-Path Billiards
Sen-Peng Eu, Tung-Shan Fu, Hsiang-Chun Hsu · 2025
Read Meanders and Dyck-Path Billiards by Sen-Peng Eu, Tung-Shan Fu, Hsiang-Chun Hsu (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-2509-18981.txt.
Introduction
Sen-Peng Eu and two co-authors count paths in a combinatorial game played on pairs of Dyck paths. A Dyck path steps up and down but never drops below its start line. Put one path above a mirrored copy of another and the region between them forms a grid polygon. Inside it, a billiard ball bounces around, and the authors count its possible trajectories.
That count turns out to match a known statistic for meanders, curves that wind across a line. The team builds a pairing scheme on path pairs that raises or lowers the count by exactly one. With it they prove a result about how meanders with even and odd numbers of pieces compare, settling a claim by Di Francesco and co-authors. They also study generating functions for restricted families of paths.
Catalog record
| CREATOR | Sen-Peng Eu, Tung-Shan Fu, Hsiang-Chun Hsu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18981
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Meanders and Dyck-Path Billiards Thanks: This research was supported in part by National Science and Technology Council, Taiwan through grants 113-2115-M-003-010 (S.-P. Eu), 113-2115-M-153-002 (T.-S. Fu) and 112-2115-M-032-002 (H.-C. Hsu). Sen-Peng Eu, Tung-Shan Fu, Hsiang-Chun Hsu Abstract . We study a statistic 𝗍𝗋𝖺𝗃 {\mathsf{traj}} on the ordered pairs ( P , Q ) (P,Q) of Dyck paths of size n n , which counts the number of billiard trajectories in the grid polygon enclosed by P P and − Q -Q , where − Q -Q is the path obtained by reflecting Q Q over the ground line. In terms of grid polygon, we establish an involution on the set of such ordered pairs ( P , Q ) (P,Q) which either increases or decreases 𝗍𝗋𝖺𝗃 ( P , Q ) {\mathsf{traj}}(P,Q) by 1. This proves a result by Di Francesco–Golinelli–Guitter that the numbers of semimeanders (meanders, respectively) of order n n with even and odd numbers of components are equal if n n is even and differ by a Catalan number (the square of a Catalan number, respectively) if n n is odd. Some results about ( − 1 ) (-1) -evaluation of the generating functions for the statistic 𝗍𝗋𝖺𝗃 {\mathsf{traj}} on restricted sets of Dyck paths are also presented. 1991 Mathematics Subject Classification 05A19 1. Introduction 1.1. Trajectory statistic for Dyck paths A Dyck path of size n is a lattice path in the plane {\mathbb{Z}}^{2} from (0,0) to (n,n) using north steps \mathsf{N}=(0,1) and east steps \mathsf{E}=(1,0) which never goes below the line y=x . Sometimes, we use the notation \mathsf{N}^{k} ( \mathsf{E}^{k} , respectively) for k consecutive north steps (east steps, respectively). Let {\mathcal{D}}_{n} denote the set of Dyck paths of size n . It is known that |{\mathcal{D}}_{n}|=c_{n}=\frac{1}{n+1}\binom{2n}{n} , the n th Catalan number. For any P\in{\mathcal{D}}_{n} , let -P denote the lattice path obtained by reflecting the path P over the line y=x , called a negative Dyck path . Let P,Q\in{\mathcal{D}}_{n} . We associate the ordered pair (P,Q) with a grid polygon in the plane {\mathbb{Z}}^{2} enclosed by P and -Q . The boundary of the grid polygon consists of the steps of P and -Q , which are numbered 1,2,\dots,4n clockwise. For example, the grid polygon associated to (P,Q) , where P=\mathsf{N}\mathsf{N}\mathsf{E}\mathsf{N}\mathsf{N}\mathsf{E}\mathsf{N}\mathsf{E}\mathsf{E}\mathsf{E} and Q=\mathsf{N}\mathsf{N}\mathsf{E}\mathsf{E}\mathsf{N}\mathsf{E}\mathsf{N}\mathsf{N}\mathsf{E}\mathsf{E} , is shown in Figure 1 . Motivated by the study of rainbow meanders and Cartesian billiards by Fiedler–Castañeda [ 5 ] (see also [ 6 , Section 2.7] ), we consider billiard trajectories, which are also interpreted as trajectories of light beams, in the grid polygon (P,Q) . Pick some step p on the boundary of the grid polygon, say with label i . Emit a beam of light from the midpoint of p into the interior of the polygon so that the light beam forms a 45 ∘ angle with p and travels either northeast, southeast, southwest, or northwest (depending on the orientation of p ). The light beam will travel through the interior of the polygon until reaching the midpoint of another step, with label \pi(i) , meeting it at a 45 ∘ angle. This defines a permutation \pi:[4n]\rightarrow[4n] . As shown in Figure 1 , the cycle decomposition of \pi of that polygon is \pi=(1,10,11,14,7,8,13,12,9,4,17,20)(2,3,18,19)(5,6,15,16) . Each cycle of \pi corresponds to a trajectory of a beam of light (cf. [ 5 , 6 ] ). Figure 1. A grid polygon with three trajectories of light beams. Let {\mathsf{traj}}(P,Q) denote the number of trajectories of light beams in the grid polygon associated to (P,Q) . The initial values for the distribution of the ordered pairs (P,Q)\in{\mathcal{D}}_{n}\times{\mathcal{D}}_{n} with respect to {\mathsf{traj}}(P,Q) are shown in Table 1 . Table 1. The number of ordered pairs (P,Q)\in{\mathcal{D}}_{n}\times{\mathcal{D}}_{n} with k trajectories of light beams for 1\leq k\leq n\leq 7 . n\backslash k 1 2 3 4 5 6 7 1 1 2 2 2 3 8 12 5 4 42 84 56 14 5 262 640 580 240 42 6 1828 5236 5894 3344 990 132 7 13820 45164 60312 42840 17472 4004 429 In particular, we define the statistic {\mathsf{traj}} on Dyck paths as follows. Let L_{n} denote the Dyck path \mathsf{N}^{n}\mathsf{E}^{n} . For any P\in{\mathcal{D}}_{n} , let {\mathsf{traj}}(P)={\mathsf{traj}}(P,L_{n}) for short. For n=3 , the values of {\mathsf{traj}}(P) for the five Dyck paths P of size 3 shown in Figure 2 are 3, 2, 1, 1, and 2 accordingly. The initial values for the distribution of Dyck paths with respect to the statistic {\mathsf{traj}} are shown in Table 2 . Figure 2. The trajectories of light beams for the paths in {\mathcal{D}}_{3} . Table 2. The number of Dyck path P\in{\mathcal{D}}_{n} with {\mathsf{traj}}(P)=k for 1\leq k\leq n\leq 7 . n\backslash k 1 2 3 4 5 6 7 1 1 2 1 1 3 2 2 1 4 4 6 3 1 5 10 16 11 4 1 6 24 48 37 17 5 1 7 66 140 126 66 24 6 1 1.2. Meanders/Semimeanders Fix a straight line in the plane {\mathbb{R}}^{2} and 2n points on it. A meander of order n is a collection of closed self-avoiding and noncrossing curves that intersect the line in exactly those 2n points. Two configurations are considered as equivalent if they are smooth deformations of one another. We consider only the inequivalent meanders. For example, the four meanders of order 2 are shown in Figure 3 . Let {\mathcal{M}}_{n} denote the set of meanders of order n . Let {\mathsf{comp}}(T) denote the number of components of a meander T\in{\mathcal{M}}_{n} . Note that the triangular array in Table 1 coincides with the distribution of the meanders in {\mathcal{M}}_{n} with respect to the number of components [ 9 , A008828] ; see also [ 4 ] . We refer the readers to [ 10 ] for historical backgrounds and recent developments of the enumeration of meanders. Figure 3. The four meanders of order 2. Now, fix a ray in the plane {\mathbb{R}}^{2} and n points on it. A semimeander of order n is a collection of closed self-avoiding and noncrossing curves that intersect the ray in exactly those n points. For example, the five semimeanders of order 3 are shown in Figure 4 . Let {\mathcal{M}}^{*}_{n} denote the set of semimeanders of order n . Note that the triangular array in Table 2 coincides with the distribution of the semimeanders in {\mathcal{M}}^{*}_{n} with respect to the number of components [ 9 , A046726] ; see also [ 4 ] . Recently, Cori and Hetyei [ 2 ] present a bijection between meanders (semimeanders, respectively) of order n and specialized hypermaps, called the spanning hypertrees of the reciprocal of a dipole with n parallel edges (a monopole with n/2 nested edges, respectively). Figure 4. The five semimeanders of order 3. 1.3. Main results There is a standard bijection between ordered pairs of Dyck paths and meanders; see [ 3 , 7 ] . Our first result is to describe the bijective properties in Theorem 1.1 Theorem 1.1 . The following results hold. (i) There is a bijection (P,Q)\mapsto T of {\mathcal{D}}_{n}\times{\mathcal{D}}_{n} onto {\mathcal{M}}_{n} with {\mathsf{traj}}(P,Q)={\mathsf{comp}}(T) . (ii) There is a bijection P\mapsto S of {\mathcal{D}}_{n} onto {\mathcal{M}}^{*}_{n} with {\mathsf{traj}}(P)={\mathsf{comp}}(S) . Our