Решетчатая дорожка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Стэнли, Ричард (2012). Перечислительная комбинаторика, Том 1 (2-е изд.). Издательство Кембриджского университета. п. 21. ISBN 978-1-107-60262-5 .
^ Jump up to: Перейти обратно: ^а ^б ^с Стэнли, Ричард (2001). Перечислительная комбинаторика, Том 2 . Издательство Кембриджского университета. стр. 173, 239. ISBN. 978-0-521-78987-5 .
^ «Вольфрам Математический Мир» . Проверено 6 марта 2014 г.

[EC1-1] Jump up to: Перейти обратно: ^а ^б Стэнли, Ричард (2012). Перечислительная комбинаторика, Том 1 (2-е изд.). Издательство Кембриджского университета. п. 21. ISBN 978-1-107-60262-5 .

[EC2-2] Jump up to: Перейти обратно: ^а ^б ^с Стэнли, Ричард (2001). Перечислительная комбинаторика, Том 2 . Издательство Кембриджского университета. стр. 173, 239. ISBN. 978-0-521-78987-5 .

[Wolfram_Dyck-3] «Вольфрам Математический Мир» . Проверено 6 марта 2014 г.

[1]

[2]

[3]