The degree of symmetry of tuples of non-crossing lattice paths (watermelons)

The degree of symmetry of a lattice path — the number of its steps in the left half that are mirror images of the corresponding steps in the right half under reflection in the vertical line through the path's midpoint — was introduced by Elizalde (Annals of Combinatorics, 2021), who determined its distribution on grand Dyck paths (algebraic generating function, Rayleigh limiting law), on partitions with conjugation symmetry, and on unimodal bargraphs with a centered maximum, and left the extension to tuples of non-crossing paths (watermelons) as an open problem (Problem 8.5 of that paper). The problem is to determine the distribution of this statistic on $k$ -tuples of non-crossing lattice paths ( $k\ge2$ ): combinatorial encodings of such tuples refined by their degree of symmetry, generating functions counting tuples by size and degree of symmetry (explicitly, or as algebraic/D-finite or functional-equation characterizations), and the resulting limiting distribution laws, generalizing the single-path results; the base instance is a pair of grand Dyck paths with common endpoints, one weakly above the other. The problem is open.

Background

A grand Dyck path of semilength $n$ is a lattice path from $(0,0)$ to $(2n,0)$ using up-steps $U=(1,1)$ and down-steps $D=(1,-1)$ ; a Dyck path is one that never goes below the $x$ -axis. Reflecting such a path in the vertical line $x=n$ through its midpoint pairs the $i$ -th step with the $(2n+1-i)$ -th; a step is called symmetric if it is the mirror image of its partner under this reflection, and the degree of symmetry $\operatorname{ds}(P)$ is the number of symmetric steps. This refines the classical notion of a symmetric path (one equal to its own reflection): $\operatorname{ds}$ ranges from $0$ for a completely asymmetric path to $n$ for a symmetric one, so it measures "how symmetric" a path is.

Elizalde (2021) determined the behavior of this statistic on single paths and related objects. For grand Dyck paths, a bijection to bicolored grand Motzkin paths (Motzkin paths — which also allow horizontal steps — whose horizontal steps come in two colors) yields the algebraic generating function (a function satisfying a polynomial equation in it and $z$ ) $\sum_{n\ge0}\sum_{P}s^{\operatorname{ds}(P)}z^{n}=1/(2(1-s)z+\sqrt{1-4z})$ , and the degree of symmetry of a uniformly random path, normalized by $\sqrt{n}$ , converges to a Rayleigh distribution (the law with density $(x/\sigma^{2})e^{-x^{2}/2\sigma^{2}}$ on $x\ge0$ ). Analogous algebraic generating functions and Rayleigh or half-normal (the law of the absolute value of a centered normal random variable) limiting laws hold for partitions, with symmetry given by conjugation of the Young diagram (transposing rows and columns; the degree of symmetry counts indices $i$ with $\lambda_{i}=\lambda'_{i}$ , where $\lambda'$ is the conjugate partition), counted by the side length of the smallest containing square ( $\max(\lambda_{1},\lambda'_{1})$ ) or by semiperimeter (half the perimeter of the shape, equal to $\lambda_{1}+\lambda'_{1}$ for a partition), and for unimodal bargraphs with a centered maximum (bar charts of compositions whose column heights increase then decrease, with the maximum in the middle), counted by semiperimeter. The Dyck-path case is of a different nature: the generating function $D(s,z)$ is characterized only through a functional equation, obtained via a chain of bijections to walks in the first quadrant with steps $E,W$ , NW, SE (with a two-coloring of NW steps leaving the $x$ -axis and weight $s$ on axis steps), and it is conjectured — based on computer-algebra experiments — to be D-finite (satisfying a linear differential equation with polynomial coefficients) but not algebraic. The paper likewise studies the companion statistic counting symmetric vertices (vertices of the path that are mirror images of vertices in the opposite half).

Tuples of non-crossing lattice paths with common starting and ending configurations, known as watermelons and studied as vicious-walker models of polymers in statistical physics, form a classical exactly-solved family: several walkers that never cross are enumerated by determinant formulas. The degree-of-symmetry statistic, however, has only been studied for single paths, and the encodings that solve the single-path cases (bicolored Motzkin paths, quadrant walks) have no known multi-path analogue. Elizalde's paper closes by posing the extension of the statistic to this setting as an open problem.

Problem Statement

Elizalde's Problem 8.5 asks to study the distribution of the degree of symmetry on tuples of non-crossing lattice paths, also known as watermelons. In the source's base instance — a pair of grand Dyck paths of semilength $n$ with common endpoints in which one path stays weakly above the other — the degree of symmetry of the tuple can be defined as the number of steps in the left half of either path that are mirror images of steps in the right half of the same path under reflection in the vertical line through the midpoint (a natural variant instead counts steps in the left half of either path that are mirror images of the corresponding steps in the right half of either path; an answer must state which variant it treats, and both variants are in scope).

The problem is to carry out for such tuples what is already known for single paths: (i) combinatorial encodings — for example bijections to Motzkin-type or quarter-plane walk families — of $k$ -tuples of non-crossing paths ( $k\ge2$ ), in both the unconstrained setting exemplified by pairs of grand Dyck paths and the wall-constrained setting where the tuple stays weakly above the $x$ -axis, refined by the degree of symmetry of the tuple; (ii) the generating functions counting such tuples by size (semilength) and degree of symmetry — as explicit closed forms, algebraic or D-finite specifications, or proved functional-equation characterizations — which determine the exact distribution of the statistic for every size; and (iii) the limiting distribution of the degree of symmetry on uniformly random non-crossing tuples as the size grows (for example, whether it obeys a Rayleigh or half-normal law as in the single-path cases).

These deliverables jointly serve one objective — determining the distribution of the degree of symmetry on non-crossing path tuples — with the encodings of (i) providing the route to the enumeration of (ii), and the limiting laws of (iii) following from (ii) by singularity analysis (the standard method that reads asymptotics off the singularities of a generating function). The single-path grand-Dyck case is already solved and serves as the model and base case; the pair case $k=2$ is the natural first instance of the open generalization. A resolution of the task requires the three deliverables (i)–(iii) for general $k\ge2$ in both the unconstrained and the wall-constrained settings; a result covering only a single case, such as the base instance $k=2$ , is partial progress toward that resolution rather than a resolution in itself, and every answer must state the settings and the tuple sizes (or the family of $k$ ) that it treats.

References

Sergi Elizalde, "The degree of symmetry of lattice paths", Annals of Combinatorics 25(4) (2021) 877–911. DOI: 10.1007/s00026-021-00551-6; arXiv:2002.12874. https://doi.org/10.1007/s00026-021-00551-6 (full text also at https://arxiv.org/abs/2002.12874)
Sergi Elizalde, Emeric Deutsch, "The degree of asymmetry of sequences", Enumerative Combinatorics and Applications 2 (2022), Article #S2R7. DOI: 10.54550/eca2022v2s1r7; arXiv:2107.06188. https://doi.org/10.54550/eca2022v2s1r7
Walaa Asakly, Noor Kezil, "Counting symmetric and non-symmetric peaks in a set partition", arXiv:2401.01687 (2024). https://arxiv.org/abs/2401.01687
Yuliy Baryshnikov, Kaitian Jin, Robin Pemantle, "Coefficient Asymptotics of Algebraic Multivariable Generating Functions", La Matematica 3 (2024) 293–336. DOI: 10.1007/s44007-024-00086-1. https://doi.org/10.1007/s44007-024-00086-1
Torin Greenwood, Stephen Melczer, Tiadora Ruza, Mark C. Wilson, "Asymptotics of coefficients of algebraic series via embedding into rational series (extended abstract)", arXiv:2112.04601 (2021). https://arxiv.org/abs/2112.04601