Schröderin numerot

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. kesäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Schröder-luvut ( saksa: Schröder ) (tarkemmin sanottuna suuret Schröder-luvut) kuvaavat kombinatoriikassa polkujen määrää n × n -neliöhilan vasemmasta alakulmasta diagonaalisesti vastakkaiseen kulmaan käyttämällä vain ylös, oikealle tai ylös-oikealle. liikkuu (" Kuninkaan siirto ") lisäehdolla, että polut eivät nouse mainitun diagonaalin yläpuolelle. Tämä lisäehto erottaa tämän sekvenssin Delannoy-luvuista . Nimetty saksalaisen matemaatikon Ernest Schröderin mukaan .

Suurten Schroeder-lukujen sarja alkaa näin:

1, 2, 6, 22, 90, 394, 1806, 8558, …. sekvenssi A006318 OEIS : ssä .

Richard Stanley, professori Massachusetts Polytechnic Institutesta, väittää, että Hipparkhos laski 10. Schroeder-luvun 1037718 mainitsematta, miten hän päätyi siihen.

Esimerkki

Alla oleva kuva näyttää 6 Schroeder-polkua 2 × 2 -ruudukossa:

Suuret ja pienet Schroeder-numerot

Suuret Schroeder-luvut laskevat polkujen määrän pisteestä (0, 0) pisteeseen (2 , 0) käyttämällä vain oikealle ylös- tai oikealle alas -askeleita (vaiheet (1, 1) tai (1, -1)) tai kaksoisaskeleita oikealle (2, 0), jotka eivät putoa x- akselin alapuolelle . $S_{n+1}$ $n$

Pienet Schroeder-numerot erottuvat siitä, että kaksinkertaiset askeleet oikealle, makaavat abskissa-akselilla, ovat kiellettyjä. Ilmeisesti . Loput pienet Schroeder-luvut ovat puolet vastaavista suurista luvuista: at . $s_{n}$ $s_{0}=S_{0}=1$ $S_{n}=2s_{n}$ $n>0$

Tämän yhtäläisyyden todistamiseksi rakennamme bijektion Schroeder-polkujen, joissa on abskissa-akselilla oleva askelma, ja samanpituisten polkujen, joissa ei ole tällaista askelmaa, välille. Jos Schroeder-polussa on vähintään yksi vaakasuora askel, joka on samalla tasolla polun alun kanssa, harkitse vasemmanpuoleisinta (punaista) tällaista askelta ja aseta seuraava (sininen) muuttamatta edellistä (vihreää) osaa osa "jaloilla" .

Vastaavat määritelmät

Suuri Schroeder-luku on yhtä suuri kuin kuinka monta tapaa jakaa suorakulmio n + 1 pienemmäksi suorakulmioksi käyttämällä n leikkausta sillä rajoituksella, että suorakulmion sisällä on n pistettä, joista kaksi ei ole samalla viivalla sivujen suuntaisesti ja jokainen leikkaus kulkee yhden näistä pisteistä läpi ja jakaa vain yhden suorakulmion kahdeksi. Kuvassa on kuusi tapaa leikata kolmeen suorakulmioon kahdella leikkauksella:

Suuret Schroeder-luvut sijaitsevat seuraavan taulukon diagonaalissa: , jossa on - :nnen sarakkeen -: nnen rivin numero . $S_{n}=T(n,n)$ $T(n,k)$ $n$ $k$

	0	yksi	2	3	neljä	5	6
0	yksi
yksi	yksi	2
2	yksi	neljä	6
3	yksi	6	16	22
neljä	yksi	kahdeksan	kolmekymmentä	68	90
5	yksi	kymmenen	48	146	304	394
6	yksi	12	70	264	714	1412	1806

Taulukko täytetään rekursiivisen säännön mukaisesti positiivisille ja , ja ja for . Voidaan osoittaa, että tämän taulukon :nnen rivin summa on yhtä suuri kuin pieni Schroeder-luku . $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))$

Ominaisuudet

Schroeder-luvut täyttävät toistuvuussuhteen : $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\;.

Luova toiminto :

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

Sovellukset

Schroeder-lukuja voidaan käyttää atsteekkien timantin halkeamien lukumäärän laskemiseen .

Katso myös

Linkit

Weisstein, Eric W. Schröder Numero (englanniksi) Wolfram MathWorld -verkkosivustolla .
Richard P. Stanley: Liite katalaanien numeroista enumeratiivisessa kombinatoriikassa , nide 2 ( Enumerative Combinatoriics )