Schroeder nummer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 5 juni 2019; kontroller kräver 8 redigeringar .

Schröder-tal ( tyska: Schröder ) (mer exakt, stora Schröder-tal) i kombinatorik beskriver antalet banor från det nedre vänstra hörnet av ett n × n kvadratiskt gitter till det diagonalt motsatta hörnet, med endast upp, höger eller uppåt höger drag (" Kungens drag ") , med det ytterligare villkoret att stigarna inte stiger över nämnda diagonal. Det är detta ytterligare villkor som skiljer denna sekvens från Delannoy-nummer . Uppkallad efter den tyske matematikern Ernest Schröder .

Sekvensen av stora Schroeder-tal börjar så här:

1, 2, 6, 22, 90, 394, 1806, 8558, …. sekvens A006318 i OEIS .

Richard Stanley, professor vid Massachusetts Polytechnic Institute, hävdar att Hipparchus beräknade det 10:e Schroeder-talet 1037718 utan att nämna hur han kom fram till det.

Exempel

Bilden nedan visar 6 Schroeder-banor på ett 2×2-rutnät:

Stora och små Schroeder-nummer

Stora Schroeder-tal räknar antalet vägar från punkt (0, 0) till (2 , 0) med endast höger-upp eller höger-ner-steg (steg (1, 1) eller (1, -1)) eller dubbla steg åt höger ( 2, 0), som inte faller under x- axeln . $S_{n+1}$ $n$

Små Schroeder-nummer kännetecknas av det faktum att dubbla steg till höger, liggande på abskissaxeln, är förbjudna. Uppenbarligen . De återstående små Schroeder-talen är hälften av motsvarande stora tal: vid . ${\displaystyle s_{n))$ $s_{0}=S_{0}=1$ $S_{n}=2s_{n}$ $n>0$

För att bevisa denna likhet konstruerar vi en bijektion mellan Schroeder-banor som har ett steg liggande på abskissaxeln och banor av samma längd som inte har ett sådant steg. Om det finns minst ett horisontellt steg i Schroeder-banan som ligger på samma nivå som början av banan, överväg det (röda) steget längst till vänster och, utan att ändra den föregående (gröna) delen, sätt följande (blått) del på "benen".

Motsvarande definitioner

Ett stort Schroeder-tal är lika med antalet sätt att bryta en rektangel i n + 1 mindre rektanglar med n snitt, med begränsningen att det finns n punkter inuti rektangeln, varav inte två ligger på samma linje parallellt med sidorna av rektangeln, och varje snitt går genom en av dessa punkter och delar bara en rektangel i två. Figuren visar 6 sätt att skära i 3 rektanglar med 2 snitt:

Stora Schroeder-tal finns längs diagonalen i följande tabell: , där är numret på den -: e raden i den -: e kolumnen. $S_{n}=T(n,n)$ $T(n,k)$ $n$ $k$

	0	ett	2	3	fyra	5	6
0	ett
ett	ett	2
2	ett	fyra	6
3	ett	6	16	22
fyra	ett	åtta	trettio	68	90
5	ett	tio	48	146	304	394
6	ett	12	70	264	714	1412	1806

Tabellen fylls enligt den rekursiva regeln för positiva och , och och för . Det kan bevisas att summan av den : e raden i denna tabell är lika med det : e lilla Schroeder - talet . $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))$

Egenskaper

Schroeder-tal uppfyller återkommande relationen : $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\;.

Genererande funktion :

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

Applikationer

Schroeder-tal kan användas för att beräkna antalet delningar i en aztekisk diamant .

Se även

Länkar

Weisstein, Eric W. Schröder nummer (engelska) på Wolfram MathWorlds webbplats .
Richard P. Stanley: Appendix on Catalan Numbers in Enumerative Combinatorics, Volym 2 ( Enumerative Combinatorics )