Příhradová cesta - Lattice path - Wikipedia

Příhradová dráha délky 5 palců ${ displaystyle mathbb {Z} ^ {2}}$ s ${ displaystyle S = left {(2,0), (1,1), (0, -1) right }}$.

v kombinatorika, a příhradová cesta ${ displaystyle L}$ v ${ displaystyle mathbb {Z} ^ {d}}$ délky ${ displaystyle k}$ s kroky dovnitř ${ displaystyle S}$ je sekvence ${ displaystyle v_ {0}, v_ {1}, ldots, v_ {k} in mathbb {Z} ^ {d}}$ tak, že každý následný rozdíl ${ displaystyle v_ {i} -v_ {i-1}}$ leží v ${ displaystyle S}$.^[1] Mřížová cesta může ležet v každém mříž v ${ displaystyle mathbb {R} ^ {d}}$,^[1] ale celočíselná mřížka ${ displaystyle mathbb {Z} ^ {d}}$ se nejčastěji používá.

Příklad mřížové cesty v ${ displaystyle mathbb {Z} ^ {2}}$ délky 5 s kroky v ${ displaystyle S = lbrace (2,0), (1,1), (0, -1) rbrace}$je ${ Displaystyle L = lbrace (-1, -2), (0, -1), (2, -1), (2, -2), (2, -3), (4, -3) rbrace}$.

Severovýchodní příhradové cesty

A Severovýchodní (SV) příhradová cesta je příhradová cesta dovnitř ${ displaystyle mathbb {Z} ^ {2}}$ s kroky dovnitř ${ displaystyle S = lbrace (0,1), (1,0) rbrace}$. The ${ displaystyle (0,1)}$ kroky se nazývají severní kroky a označují se ${ displaystyle N}$je ${ displaystyle (1,0)}$ kroky se nazývají Východní kroky a označují se ${ displaystyle E}$je

NE příhradové dráhy nejčastěji začínají od počátku. Tato konvence nám umožňuje zakódovat všechny informace o SV mřížkové cestě ${ displaystyle L}$v jednom permutační slovo. Délka slova nám udává počet kroků mřížkové cesty, ${ displaystyle k}$. Pořadí ${ displaystyle N}$a ${ displaystyle E}$komunikuje posloupnost ${ displaystyle L}$. Kromě toho počet ${ displaystyle N}$a počet ${ displaystyle E}$ve slově určuje konečný bod ${ displaystyle L}$.

Pokud obsahuje permutační slovo pro NE mřížkovou cestu ${ displaystyle n}$ ${ displaystyle N}$kroky a ${ displaystyle e}$ ${ displaystyle E}$ kroky, a pokud cesta začíná na počátku, pak cesta nutně končí na ${ displaystyle (e, n)}$. Toto následuje, protože jste přesně „chodili“ ${ displaystyle n}$ kroky na sever a ${ displaystyle e}$ kroky na východ od ${ displaystyle (0,0)}$.

NE mřížkové cesty začínající od ${ displaystyle (0,0)}$ s přesně jedním ${ displaystyle N}$ a tři ${ displaystyle E}$je Koncový bod je nutně na ${ displaystyle (3,1)}$.

Počítání příhradových cest

Mřížkové cesty se často používají k počítání dalších kombinatorických objektů. Podobně existuje mnoho kombinatorických objektů, které počítají počet mřížkových cest určitého druhu. K tomu dochází, když jsou mřížkové cesty uvnitř bijekce s daným objektem. Například,

• Dyckovy cesty jsou počítány podle ${ displaystyle n ^ { text {th}}}$ Katalánské číslo ${ displaystyle C_ {n}}$. A Dyckova cesta je příhradová cesta dovnitř ${ displaystyle mathbb {Z} ^ {2}}$ z ${ displaystyle (0,0)}$ na ${ displaystyle (2n, 0)}$ s kroky dovnitř ${ displaystyle S = lbrace (1,1), (1, -1) rbrace}$ který nikdy neprochází pod ${ displaystyle x}$-osa.^[2] Ekvivalentně Dyckova cesta je SV příhradová cesta z ${ displaystyle (0,0)}$ na ${ displaystyle (n, n)}$ která leží přesně pod (ale může se dotýkat) úhlopříčky ${ displaystyle y = x}$.^[2][3]
• The Schröderova čísla spočítat počet příhradových cest od ${ displaystyle (0,0)}$ na ${ displaystyle (n, n)}$ s kroky dovnitř ${ displaystyle (1,0), (0,1)}$ a ${ displaystyle (1,1)}$ které nikdy nevyrostou nad úhlopříčku ${ displaystyle y = x}$.^[2]
• Počet NE mřížkových cest z ${ displaystyle (0,0)}$ na ${ displaystyle (a, b)}$ počítá počet kombinace z ${ displaystyle a}$ objekty ze sady ${ displaystyle a + b}$ předměty.

Kombinace a NE mřížkové cesty

NE mřížkové cesty mají úzké spojení s počtem kombinace, které počítá binomický koeficient a uspořádány Pascalův trojúhelník. Níže uvedený diagram ukazuje některá z těchto připojení.

Počet příhradových cest z ${ displaystyle (0,0)}$ na ${ displaystyle (2,3)}$ je rovný ${ displaystyle { binom {2 + 3} {2}} = { binom {5} {2}} = 10}$.

Počet příhradových cest z ${ displaystyle (0,0)}$ na ${ displaystyle (n, k)}$ se rovná binomický koeficient ${ displaystyle { binom {n + k} {n}}}$. Diagram to ukazuje pro ${ displaystyle 0 leq k leq n = 4}$. Pokud jeden otočí diagram o 135 ° ve směru hodinových ručiček kolem počátku a rozšíří ho tak, aby zahrnoval všechny ${ displaystyle n, k in mathbb {N} cup lbrace 0 rbrace}$, získá se Pascalův trojúhelník. Tento výsledek není žádným překvapením, protože ${ displaystyle k ^ { text {th}}}$ vstup ${ displaystyle n ^ { text {th}}}$ řada Pascalova trojúhelníku je binomický koeficient ${ displaystyle { binom {n} {k}}}$.

Problémy a důkazy

Grafické znázornění NE mřížkových cest se hodí pro mnoho bijektivní důkazy zahrnující kombinace. Zde je několik příkladů.

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

Důkaz: Pravá strana se rovná počtu NE příhradových cest z ${ displaystyle (0,0)}$ na ${ displaystyle (n, n)}$. Každá z těchto NE mřížkových cest protíná přesně jeden z mřížových bodů v obdélníkovém poli se souřadnicemi ${ displaystyle (x, n-x)}$ pro ${ displaystyle x in lbrace 0,1, ldots, n rbrace}$. To je znázorněno na obrázku níže pro ${ displaystyle n = 4}$: Každá SV příhradová cesta z ${ displaystyle (0,0)}$ na ${ displaystyle (4,4)}$ protíná přesně jeden z barevných uzlů.

Každá NE mřížková cesta prochází přesně jedním barevným uzlem.

Na levé straně je znak binomický koeficient na druhou ${ displaystyle { binom {n} {k}} ^ {2}}$, představuje dvě kopie sady NE mřížkových cest z${ displaystyle (0,0)}$ na ${ displaystyle (k, n-k)}$ připojený koncový bod k počátečnímu bodu. Otočte druhou kopii o 90 ° ve směru hodinových ručiček. To nemění kombinatoriku objektu: ${ displaystyle { binom {n} {k}} = { binom {n} {n-k}}}$. Celkový počet příhradových drah tedy zůstává stejný.

Sady NE příhradových drah na druhou, s druhou kopií otočenou o 90 ° ve směru hodinových ručiček.

Překryjte NE mřížkové cesty na druhou do stejného obdélníkového pole, jak je vidět na obrázku níže. Vidíme, že všechny NE mřížkové cesty z ${ displaystyle (0,0)}$ na ${ displaystyle (n, n)}$ jsou účtovány. Zejména si všimněte, že jakákoli mřížková dráha procházející červeným mřížkovým bodem (například) se počítá druhou mocninou mřížkových cest (zobrazených také červeně). ${ displaystyle Box}$

Navrstvené sady NE příhradových drah na druhou. Jsou zohledněny všechny NE mřížkové cesty.

Reference