Schroeder számok

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. június 5-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A Schröder-számok ( németül: Schröder ) (pontosabban a nagy Schröder-számok) a kombinatorikában egy n × n négyzetrács bal alsó sarkától az átlósan ellentétes sarokig tartó utak számát írják le , csak felfelé, jobbra vagy fel-jobbra. mozog (" Király lépése ") , azzal a további feltétellel, hogy az utak nem emelkednek az említett átló fölé. Ez a további feltétel különbözteti meg ezt a sorozatot a Delannoy-számoktól . Ernest Schröder német matematikusról kapta a nevét .

A nagy Schroeder-számok sorozata így kezdődik:

1, 2, 6, 22, 90, 394, 1806, 8558, …. A006318 szekvencia az OEIS -ben .

Richard Stanley, a Massachusetts Polytechnic Institute professzora azt állítja, hogy Hipparkhosz kiszámolta a 10. Schroeder-számot 1037718 anélkül, hogy megemlítette volna, hogyan jutott hozzá.

Példa

Az alábbi ábra 6 Schroeder útvonalat mutat be egy 2×2-es rácson:

Kis és nagy Schroeder számok

A nagy Schroeder-számok a (0, 0) ponttól a (2, 0) pontig tartó utak számát számolják csak jobbra vagy jobbra lefelé (1, 1 vagy (1, -1) lépések) vagy dupla lépések jobbra használatával. (2, 0), amelyek nem esnek az x tengely alá . $S_{n+1}$ $n$

A kis Schroeder-számokat az a tény különbözteti meg, hogy tilos a jobb oldali kettős lépés az abszcissza tengelyén fekve. Nyilvánvalóan . A fennmaradó kis Schroeder-számok fele a megfelelő nagy számoknak: at . $s_{n}$ $s_{0}=S_{0}=1$ $S_{n}=2s_{n}$ $n>0$

Ennek az egyenlőségnek a bizonyítására egy bijekciót készítünk az abszcissza tengelyen fekvő Schroeder-pályák és az azonos hosszúságú, ilyen lépcsővel nem rendelkező utak között. Ha van legalább egy vízszintes lépcső a Schroeder-görbében, amely ugyanazon a szinten van, mint az útvonal kezdete, vegye figyelembe a bal szélső (piros) ilyen lépést, és anélkül, hogy megváltoztatná az előző (zöld) részt, tegye a következőt (kék) rész a „lábakon” .

Egyenértékű definíciók

Egy nagy Schroeder-szám megegyezik azzal a megkötéssel, hogy egy téglalapot n + 1 kisebb téglalapra bonthatunk n darab vágással, azzal a megkötéssel, hogy a téglalap belsejében n pont legyen, amelyek közül nincs kettő ugyanazon az oldallal párhuzamos egyenesen. és minden vágás átmegy ezen pontok egyikén, és csak egy téglalapot oszt ketté. Az ábra 6 módszert mutat be 3 téglalapra 2 vágással:

A nagy Schroeder-számok a következő táblázat átlója mentén helyezkednek el: , ahol a -edik oszlop -edik sorának száma . $S_{n}=T(n,n)$ $T(n,k)$ $n$ $k$

	0	egy	2	3	négy	5	6
0	egy
egy	egy	2
2	egy	négy	6
3	egy	6	16	22
négy	egy	nyolc	harminc	68	90
5	egy	tíz	48	146	304	394
6	egy	12	70	264	714	1412	1806

A táblázat kitöltése a rekurzív szabály szerint történik pozitív és , valamint és -ra . Bizonyítható, hogy a táblázat 0. sorának összege megegyezik a kis Schroeder-számmal . $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))$

Tulajdonságok

A Schroeder-számok kielégítik az ismétlődési relációt : $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\;.

Generáló funkció :

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

Alkalmazások

A Schroeder-számok segítségével kiszámítható az azték gyémánt hasadásainak száma .

Lásd még

Linkek

Weisstein, Eric W. Schröder szám (angolul) a Wolfram MathWorld weboldalán .
Richard P. Stanley: Függelék a katalán számokról a felsoroló kombinatorikában, 2. kötet ( Enumeratív kombinatorika )