Schroederova čísla

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. června 2019; kontroly vyžadují 8 úprav .

Schröderova čísla ( německy : Schröder ) (přesněji velká Schröderova čísla) v kombinatorice popisují počet cest z levého dolního rohu n × n čtvercové mřížky do diagonálně protějšího rohu, a to pouze pomocí up, right nebo up-right. tahy (" King 's move ") , s dodatečnou podmínkou, že cesty nestoupají nad uvedenou úhlopříčku. Je to tato další podmínka, která odlišuje tuto sekvenci od Delannoyových čísel . Pojmenována po německém matematikovi Ernestu Schröderovi .

Posloupnost velkých Schroederových čísel začíná takto:

1, 2, 6, 22, 90, 394, 1806, 8558, …. sekvence A006318 v OEIS .

Richard Stanley, profesor Massachusettského polytechnického institutu, tvrdí, že Hipparchos vypočítal 10. Schroederovo číslo 1037718, aniž by uvedl, jak k němu dospěl.

Příklad

Obrázek níže ukazuje 6 Schroederových cest na mřížce 2×2:

Velká a malá Schroederova čísla

Velká Schroederova čísla počítají počet cest z bodu (0, 0) do (2 , 0) pouze pomocí kroků doprava nahoru nebo doprava dolů (kroky (1, 1) nebo (1, -1)) nebo dvojitými kroky doprava ( 2, 0), které neklesají pod osu x . $S_{n+1}$ $n$

Malá Schroederova čísla se vyznačují tím, že dvojité kroky doprava vleže na ose úsečky jsou zakázány. Samozřejmě . Zbývající malá Schroederova čísla jsou poloviční než odpovídající velká čísla: v . ${\displaystyle s_{n))$ $s_{0}=S_{0}=1$ $S_{n}=2s_{n}$ $n>0$

Abychom tuto rovnost dokázali, sestrojíme bijekci mezi Schroederovými cestami, které mají krok ležící na ose úsečky, a cestami stejné délky, které takový krok nemají. Pokud je na Schroederově cestě alespoň jeden vodorovný krok, který leží na stejné úrovni jako začátek cesty, zvažte takový krok zcela vlevo (červený) a beze změny předchozí (zelené) části vložte následující (modrý) část na „nohách“.

Ekvivalentní definice

Velké Schroederovo číslo se rovná počtu způsobů, jak rozdělit obdélník na n + 1 menších obdélníků pomocí n řezů, s podmínkou, že uvnitř obdélníku je n bodů, z nichž žádné dva neleží na stejné čáře rovnoběžné se stranami. obdélníku a každý řez prochází jedním z těchto bodů a rozděluje pouze jeden obdélník na dva. Obrázek ukazuje 6 způsobů řezání na 3 obdélníky pomocí 2 řezů:

Velká Schroederova čísla jsou umístěna podél úhlopříčky následující tabulky: , kde je číslo -tého řádku -tého sloupce. $S_{n}=T(n,n)$ $T(n,k)$ $n$ $k$

	0	jeden	2	3	čtyři	5	6
0	jeden
jeden	jeden	2
2	jeden	čtyři	6
3	jeden	6	16	22
čtyři	jeden	osm	třicet	68	90
5	jeden	deset	48	146	304	394
6	jeden	12	70	264	714	1412	1806

Tabulka se vyplňuje podle rekurzivního pravidla pro kladné a , a a pro . Lze dokázat, že součet t. řádku této tabulky je roven tému malému Schroederovu číslu . $T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)$ $n$ $k$ $T(1,k)=1$ $T(n,k)=0$ $k>n$ $n$ $(n+1)$ ${\displaystyle \sum _{k=0}^{n}T(n,k)=s_{n+1))$

Vlastnosti

Schroederova čísla splňují rekurenci opakování : $S_{n}$

S_{0}=1;\qquad S_{n}=S_{n-1}+\sum _{i=0}^{n-1}S_{i}S_{n-1-i} ,\quad n\geq 1\;.

Funkce generování :

\sum _{n=1}^{\infty }S_{n}x^{n}={\frac {1-x-{\sqrt {1-6x+x^{2)))) {2x}}

Aplikace

Schroederova čísla lze použít k výpočtu počtu štěpů v aztéckém diamantu .

Viz také

Odkazy

Weisstein, Eric W. Schröder Number (anglicky) na webových stránkách Wolfram MathWorld .
Richard P. Stanley: Dodatek o katalánských číslech ve výčtové kombinatorice, svazek 2 ( výčtová kombinatorika )