Bijections Between Walks Inside a Triangular Domain and Motzkin Paths of Bounded Amplitude

Julien Courtiel, Andrew Elvey Price, Ana BušićThe Electronic Journal of Combinatorics 2021 · DOI

TL;DR

This paper provides the first explicit combinatorial bijections to solve a long-standing open problem concerning the enumeration of triangular lattice walks and Motzkin paths. The authors introduce novel techniques, including "scaffoldings," to establish these bijections and extend their findings to higher dimensions, revealing surprising connections between different types of lattice paths.

What Problem Does This Paper Address?

The paper tackles an open question posed by Mortimer and Prellberg in 2015 concerning the equinumeracy of two seemingly different types of combinatorial objects:

  1. Triangular Walks: These are 2D walks confined within a triangular lattice. They can move in six specific directions (0°, 60°, 120°, 180°, 240°, 300°).
  2. Motzkin Paths of Bounded Amplitude: These are paths on a 1D grid that use up, horizontal, and down steps, starting and ending at height 0, with the additional constraint that their "amplitude" (related to their maximum height) is bounded.

Mortimer and Prellberg showed, using analytic methods, that the number of triangular walks starting from a corner of the triangle is equal to the number of Motzkin paths with bounded height. However, they lacked a combinatorial explanation – an explicit step-by-step mapping (a bijection) – to demonstrate why these counts are the same. This lack of a combinatorial proof was a significant open problem in the field. The paper also addresses extensions of these results to walks starting at any point within the triangle and to higher dimensions.

Methods

The authors employ a variety of combinatorial techniques to construct their bijections:

  • Inductive Proofs: Several results are established through induction, building up solutions for longer paths from shorter ones.
  • Symmetry Arguments: The paper leverages symmetry properties of the triangular lattice and its walks to establish key relationships, such as the equinumeracy of forward and backward paths.
  • "Flips" (Swap and Last-Step): A core mechanism for transforming paths involves elementary reversible operations called "flips." Swap flips exchange consecutive steps, while last-step flips alter the direction of the final step. These are used to change the "direction vector" of a path.
  • "Folded Paths": To handle certain transformations more symmetrically, the authors introduce "folded paths," which are paths that traverse forward and then backward along the same sequence.
  • "Cell Representation" and "Profiles": For more complex bijections, particularly those involving higher dimensions and "scaffoldings," the authors represent points in the lattice by sets of cells (profiles). These profiles encode combinatorial information about the point and its neighborhood.
  • "Scaffoldings": This is a novel concept introduced in the paper. A scaffolding is a data structure that guides the construction of bijections by dictating choices at each step, based on the current state of the path and the chosen cell representation. These scaffoldings are parameterized, allowing for the generation of a family of bijections.
  • Geometric Interpretations: The paper uses diagrams and geometric representations to illustrate the bijections, making them more intuitive.

Datasets

Not discussed in the paper. The paper deals with theoretical combinatorial objects (lattice walks) rather than empirical data.

Key Insights and Ideas

  • The 2ⁿ Factor: The paper explains why generic triangular paths are counted by $2^n$ times the number of forward-only triangular paths of the same length. This is achieved by showing a bijection between paths with different sequences of forward and backward steps.
  • "Scaffoldings" as a General Bijection Framework: The introduction of scaffoldings provides a powerful and flexible way to construct numerous bijections between triangular paths and Motzkin paths. This framework allows for parameterization and customization of the bijections.
  • Higher-Dimensional Analogues: The paper successfully extends the concept of triangular walks and their bijections to higher-dimensional simplices (pyramids) and finds surprising connections to other types of walks (waffle walks).
  • Profile-Based Bijections: The use of "profiles" and "cell representations" offers a new way to encode and manipulate combinatorial information within lattice structures, enabling more complex bijections.
  • Solving a Long-Standing Open Problem: The primary insight is providing the first explicit combinatorial proofs for the equinumeracy observed by Mortimer and Prellberg, resolving a question that had been open for several years.

Key Results

  • Explicit Bijections: The paper provides several explicit bijections between triangular walks and Motzkin paths of bounded amplitude, solving Mortimer and Prellberg's open question.
  • Linear-Time Bijections: The authors develop parameterized bijections using "scaffoldings" that have linear-time complexity, making them computationally efficient.
  • Generalization to Higher Dimensions: The results are extended to higher dimensions, establishing bijections between pyramidal walks and waffle walks in 3D.
  • Generating Function for Pyramid Walks: The paper derives a formula for the generating function of pyramid walks starting from a corner, which was also an open question.
  • Symmetry Property: A new symmetry property is discovered: the number of triangular paths starting from a point with a given sequence of forward and backward steps is independent of the specific sequence of steps.

Limitations and Future Work

  • Complexity of Exponential Bijection: While a recursive bijection is presented, its computation can be complex and take exponential time. The authors note that it's unclear if this bound is tight.
  • Higher Dimensions (d ≥ 4): The paper leaves open the question of whether bijections exist between triangular walks in dimension $d \ge 4$ and walks in dimension $d-1$. The methods used for 2D and 3D do not seem to directly apply.
  • Conjecture on Double-Tandem Walks: The authors mention a conjecture about a length-preserving involution on double-tandem walks and suggest that techniques from this paper might help in discovering it.
  • Generic Framework for Bijections: The paper raises the question of whether a generic framework for bijections involving endpoint constraints exists, similar to the ones presented.

Summary updated

Abstract

This paper solves an open question of Mortimer and Prellberg asking for an explicit bijection between two families of walks. The first family is formed by what we name triangular walks, which are two-dimensional walks moving in six directions (0°, 60°, 120°, 180°, 240°, 300°) and confined within a triangle. The other family is comprised of two-colored Motzkin paths with bounded height, in which the horizontal steps may be forbidden at maximal height. We provide several new bijections. The first one is derived from a simple inductive proof, taking advantage of a 2n-to-one function from generic triangular walks to triangular walks only using directions 0°, 120°, 240°. The second is based on an extension of Mortimer and Prellberg's results to triangular walks starting not only at a corner of the triangle, but at any point inside it. It has a linear-time complexity and is in fact adjustable: by changing some set of parameters called a scaffolding, we obtain a wide range of different bijections. Finally, we extend our results to higher dimensions. In particular, by adapting the previous proofs, we discover an unexpected bijection between three-dimensional walks in a pyramid and two-dimensional simple walks confined in a bounded domain shaped like a waffle.
BibTeX
@article{courtiel2021bijections,
  author = {Julien Courtiel and Andrew Elvey Price and Ana Bušić},
  title = {{Bijections Between Walks Inside a Triangular Domain and Motzkin Paths of Bounded Amplitude}},
  journal = {The Electronic Journal of Combinatorics},
  year = {2021},
  doi = {10.37236/9724},
}
Figure