Решетчатый путь

Последовательность сквозных векторов через точки решетки

Решетчатый путь длины 5 в ℤ ² с S = { (2,0), (1,1), (0,-1) }.

В комбинаторике решетчатый путь L в d -мерной целочисленной решетке ⁠ ⁠ ${\displaystyle \mathbb {Z} ^{d}}$ длины k с шагами в множестве S , представляет собой последовательность векторов ⁠ ⁠ ${\displaystyle v_{0},v_{1},\ldots ,v_{k}\in \mathbb {Z} ^{d}}$ такую, что каждая последующая разность лежит в S . ^[1] Решетчатый путь может лежать в любой решетке из ⁠ ⁠ , ^[1] но целочисленная решетка ⁠ ⁠ используется чаще всего. ${\displaystyle v_{i}-v_{i-1}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {Z} ^{d}}$

Примером решетчатого пути в ⁠ ⁠ ${\displaystyle \mathbb {Z} ^{2}}$ длиной 5 с шагами в является . ${\displaystyle S=\lbrace (2,0),(1,1),(0,-1)\rbrace }$ ${\displaystyle L=\lbrace (-1,-2),(0,-1),(2,-1),(2,-2),(2,-3),(4,-3)\rbrace }$

Северо-восточные решетчатые пути

Путь решетки северо -восток (СВ) — это путь решетки в с шагами в . Шаги называются северными шагами и обозначаются 's; шаги называются восточными шагами и обозначаются 's. ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle S=\lbrace (0,1),(1,0)\rbrace }$ ${\displaystyle (0,1)}$ ${\displaystyle N}$ ${\displaystyle (1,0)}$ ${\displaystyle E}$

Решетчатые пути NE чаще всего начинаются в начале координат. Это соглашение позволяет нам кодировать всю информацию о решетчатом пути NE в одном перестановочном слове . Длина слова дает нам количество шагов решетчатого пути, . Порядок ' и ' передает последовательность . Кроме того, количество ' и количество ' в слове определяют конечную точку . ${\displaystyle L}$ ${\displaystyle k}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle L}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle L}$

Если слово перестановки для пути решетки NE содержит шаги и шаги, и если путь начинается в начале, то путь обязательно заканчивается в . Это следует из того, что вы «прошли» ровно шагов на север и шагов на восток от . ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle e}$ ${\displaystyle E}$ ${\displaystyle (e,n)}$ ${\displaystyle n}$ ${\displaystyle e}$ ${\displaystyle (0,0)}$

NE решетчатые пути, начинающиеся с ровно с одного и трех '. Конечная точка обязательно находится в . ${\displaystyle (0,0)}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle (3,1)}$

Подсчет путей решетки

Решетчатые пути часто используются для подсчета других комбинаторных объектов. Аналогично, существует множество комбинаторных объектов, которые подсчитывают количество решетчатых путей определенного вида. Это происходит, когда решетчатые пути находятся в биекции с рассматриваемым объектом. Например,

• Пути Дика подсчитываются с помощью числа Каталана . Путь Дика — это решетчатый путь от до с шагами в , который никогда не проходит ниже оси . ^[2] Эквивалентно, путь Дика — это NE-решетчатый путь от до , который лежит строго ниже (но может касаться) диагонали . ^{[2] [3]} ${\displaystyle n^{\text{th}}}$ ${\displaystyle C_{n}}$ ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle (0,0)}$ ${\displaystyle (2n,0)}$ ${\displaystyle S=\lbrace (1,1),(1,-1)\rbrace }$ ${\displaystyle x}$ ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle y=x}$
• Числа Шредера подсчитывают количество путей решетки от до со ступенями в и которые никогда не поднимаются выше диагонали . ^[2] ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle (1,0),(0,1)}$ ${\displaystyle (1,1)}$ ${\displaystyle y=x}$
• Число путей NE-решетки от до подсчитывает количество комбинаций объектов из набора объектов. ${\displaystyle (0,0)}$ ${\displaystyle (a,b)}$ ${\displaystyle a}$ ${\displaystyle a+b}$

Комбинации и пути NE-решетки

Пути решетки NE имеют тесные связи с числом комбинаций , которые подсчитываются биномиальным коэффициентом и располагаются в треугольнике Паскаля . Диаграмма ниже демонстрирует некоторые из этих связей.

Число путей решетки от до равно . ${\displaystyle (0,0)}$ ${\displaystyle (2,3)}$ ${\displaystyle {\binom {2+3}{2}}={\binom {5}{2}}=10}$

Число путей решетки от до равно биномиальному коэффициенту . Диаграмма показывает это для . Если повернуть диаграмму на 135° по часовой стрелке вокруг начала координат и расширить ее, включив все , то получится треугольник Паскаля. Этот результат неудивителен, поскольку запись строки треугольника Паскаля — это биномиальный коэффициент . ${\displaystyle (0,0)}$ ${\displaystyle (n,k)}$ ${\displaystyle {\binom {n+k}{n}}}$ ${\displaystyle 0\leq k\leq n=4}$ ${\displaystyle n,k\in \mathbb {N} \cup \lbrace 0\rbrace }$ ${\displaystyle k^{\text{th}}}$ ${\displaystyle n^{\text{th}}}$ ${\displaystyle {\binom {n}{k}}}$

Проблемы и доказательства

Графическое представление путей NE-решетки позволяет проводить множество биективных доказательств, включающих комбинации. Вот несколько примеров.

• ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}}$.

Доказательство : Правая часть равна числу путей решетки NE от до . Каждый из этих путей решетки NE пересекает ровно одну из точек решетки в прямоугольном массиве с координатами для . Это показано на рисунке ниже для : Каждый путь решетки NE от до пересекает ровно один из цветных узлов. ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle (x,n-x)}$ ${\displaystyle x\in \lbrace 0,1,\ldots ,n\rbrace }$ ${\displaystyle n=4}$ ${\displaystyle (0,0)}$ ${\displaystyle (4,4)}$

Каждый путь решетки NE проходит ровно через один цветной узел.

С левой стороны квадрат биномиального коэффициента , , представляет две копии набора путей решетки NE от до присоединенной конечной точки до начальной точки. Поверните вторую копию на 90° по часовой стрелке. Это не изменит комбинаторику объекта: . Таким образом, общее количество путей решетки останется прежним. ${\displaystyle {\binom {n}{k}}^{2}}$ ${\displaystyle (0,0)}$ ${\displaystyle (k,n-k)}$ ${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$

Наборы NE-путей решетки, возведенные в квадрат, причем вторая копия повернута на 90° по часовой стрелке.

Наложите квадраты путей решетки NE на тот же прямоугольный массив, как показано на рисунке ниже. Мы видим, что все пути решетки NE от до учтены. В частности, обратите внимание, что любой путь решетки, проходящий через красную точку решетки (например), учитывается квадратом множества путей решетки (также показанных красным). ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle \Box }$

Наложенные наборы квадратов решетчатых путей NE. Все решетчатые пути NE учтены.

Смотрите также

• Тадепалли Венката Нараяна

Ссылки

1. Стэнли, Ричард (2012). Перечислительная комбинаторика, том 1 (2-е изд.). Cambridge University Press. стр. 21. ISBN 978-1-107-60262-5.
2. Стэнли, Ричард (2001). Перечислительная комбинаторика, том 2. Cambridge University Press. стр. 173, 239. ISBN 978-0-521-78987-5.
3. "Wolfram MathWorld" . Получено 6 марта 2014 г.

^[1]

^[2]

1. Нараяна, Тадепалли Венката (15 декабря 1979 г.). Комбинаторика решеточных путей со статистическими приложениями (1-е изд.). Торонто: Издательство Торонтского университета. ISBN 978-1487587284.
2. Song, Chunwei (2024). Lattice Path Combinatorics and Special Counting Sequences: From an Enumerative Perspective (1-е изд.). Boca Raton: CRC Press. doi : 10.1201/9781003509912. ISBN 978-1032671758.