论文标题
在三角形域和有限振幅的Motzkin路径内行走之间的射击
Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude
论文作者
论文摘要
本文解决了Mortimer和Prellberg的一个公开问题，要求在两个步行家族之间进行明确的两次射击。第一个家庭是由我们命名的三角步行形成的，这些步行是在六个方向（0°，60°，120°，120°，180°，240°，300°）中移动的二维步行，并限制在三角形中。另一个家族由具有界面高度的两色Motzkin路径组成，其中最大高度可能禁止水平台阶。 我们提供了几种新的徒。第一个是从简单的电感证明中得出的，利用$ 2^n $的功能从通用的三角步行到三角步行，仅使用指示0°，120°，240°。第二个是基于Mortimer和Prellberg的结果扩展到三角步行，这不仅是从三角形的角落开始，而且还在其中的任何时候。它具有线性时间复杂性，实际上是可调的：通过更改一些称为脚手架的参数，我们获得了广泛的不同生物。 最后，我们将结果扩展到更高的维度。特别是，通过调整以前的证据，我们发现了金字塔中三维步行与二维简单步行之间的意外射击，这些步行被限制在形状像华夫饼干的界面域中。
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 $2^n$-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.
