Решетчатый путь - Lattice path - Wikipedia

Путь решетки длиной 5 дюймов ${\displaystyle \mathbb {Z} ^{2}}$ с ${\displaystyle S=\left\{(2,0),(1,1),(0,-1)\right\}}$.

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

Решетчатые дорожки Северо-Восток

А Северо-восточный (NE) решетчатый путь решетчатый путь в ${\displaystyle \mathbb {Z} ^{2}}$ с шагами в ${\displaystyle S=\lbrace (0,1),(1,0)\rbrace }$. В ${\displaystyle (0,1)}$ шаги называются северными шагами и обозначаются ${\displaystyle N}$s; ${\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)}$.

Подсчет решетчатых путей

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

• Дайковые тропы подсчитываются ${\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}$-ось.^[2] Эквивалентно, путь Дика - это путь решетки NE от ${\displaystyle (0,0)}$ к ${\displaystyle (n,n)}$ который лежит строго ниже (но может касаться) диагонали ${\displaystyle y=x}$.^[2][3]
• В Числа Шредера подсчитать количество путей решетки из ${\displaystyle (0,0)}$ к ${\displaystyle (n,n)}$ с шагами в ${\displaystyle (1,0),(0,1)}$ и ${\displaystyle (1,1)}$ которые никогда не поднимаются выше диагонали ${\displaystyle y=x}$.^[2]
• Количество путей решетки 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}$.

Число путей решетки от ${\displaystyle (0,0)}$ к ${\displaystyle (n,k)}$ равно биномиальный коэффициент ${\displaystyle {\binom {n+k}{n}}}$. Схема показывает это для ${\displaystyle 0\leq k\leq n=4}$. Если повернуть диаграмму на 135 ° по часовой стрелке вокруг начала координат и расширить ее, чтобы включить все ${\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 из ${\displaystyle (0,0)}$ к ${\displaystyle (n,n)}$. Каждый из этих путей решетки NE пересекает ровно одну из точек решетки в прямоугольном массиве с координатами ${\displaystyle (x,n-x)}$ за ${\displaystyle x\in \lbrace 0,1,\ldots ,n\rbrace }$. Это показано на рисунке ниже для ${\displaystyle n=4}$: Каждый путь решетки NE от ${\displaystyle (0,0)}$ к ${\displaystyle (4,4)}$ пересекает ровно один из цветных узлов.

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

С левой стороны биномиальный коэффициент в квадрате ${\displaystyle {\binom {n}{k}}^{2}}$, представляет собой две копии набора путей решетки NE из${\displaystyle (0,0)}$ к ${\displaystyle (k,n-k)}$ присоединенная конечная точка к начальной точке. Поверните вторую копию на 90 ° по часовой стрелке. Это не меняет комбинаторику объекта: ${\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-е изд.). Издательство Кембриджского университета. п. 21. ISBN  978-1-107-60262-5.
2. Стэнли, Ричард (2001). Перечислительная комбинаторика, Том 2. Издательство Кембриджского университета. С. 173, 239. ISBN  978-0-521-78987-5.
3. "Wolfram MathWorld". Получено 6 марта 2014.