Schroeder-numre

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. juni 2019; checks kræver 8 redigeringer .

Schröder-tal ( tysk: Schröder ) (mere præcist, store Schröder-tal) i kombinatorik beskriver antallet af stier fra det nederste venstre hjørne af et n × n kvadratisk gitter til det diagonalt modsatte hjørne, kun ved hjælp af op, højre eller op-højre træk (" Kongens træk ") , med den yderligere betingelse, at stierne ikke hæver sig over den nævnte diagonal. Det er denne yderligere betingelse, der adskiller denne sekvens fra Delannoy-numre . Opkaldt efter den tyske matematiker Ernest Schröder .

Sekvensen af store Schroeder-tal begynder således:

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

Richard Stanley, professor ved Massachusetts Polytechnic Institute, hævder, at Hipparchus beregnede det 10. Schroeder-nummer 1037718 uden at nævne, hvordan han nåede frem til det.

Eksempel

Figuren nedenfor viser 6 Schroeder-stier på et 2×2-gitter:

Store og små Schroeder-tal

Store Schroeder-tal tæller antallet af stier fra punkt (0, 0) til (2 , 0) ved kun at bruge højre op eller højre ned trin (trin (1, 1) eller (1, -1)) eller dobbelte trin til højre ( 2, 0), som ikke falder under x- aksen . $S_{n+1}$ $n$

Små Schroeder-numre er kendetegnet ved, at dobbelttrin til højre, liggende på abscisseaksen, er forbudt. Åbenbart . De resterende små Schroeder-tal er halvdelen af de tilsvarende store tal: kl . ${\displaystyle s_{n))$ $s_{0}=S_{0}=1$ $S_{n}=2s_{n}$ $n>0$

For at bevise denne lighed konstruerer vi en bijektion mellem Schroeder-baner, der har et trin liggende på abscisse-aksen, og stier af samme længde, som ikke har et sådant trin. Hvis der er mindst et vandret trin i Schroeder-stien, der ligger på samme niveau som begyndelsen af stien, skal du overveje det længst til venstre (røde) sådant trin, og uden at ændre den foregående (grønne) del, indsætte følgende (blå) del på "benene".

Tilsvarende definitioner

Et stort Schroeder-tal er lig med antallet af måder at opdele et rektangel i n + 1 mindre rektangler ved hjælp af n snit, med den begrænsning, at der er n punkter inde i rektanglet, hvoraf ikke to ligger på samme linje parallelt med siderne af rektanglet, og hvert snit går gennem et af disse punkter og deler kun ét rektangel i to. Figuren viser 6 måder at skære i 3 rektangler ved hjælp af 2 snit:

Store Schroeder-tal er placeret langs diagonalen i følgende tabel: , hvor er nummeret på den -th række i den -th kolonne. $S_{n}=T(n,n)$ $T(n,k)$ $n$ $k$

	0	en	2	3	fire	5	6
0	en
en	en	2
2	en	fire	6
3	en	6	16	22
fire	en	otte	tredive	68	90
5	en	ti	48	146	304	394
6	en	12	70	264	714	1412	1806

Tabellen udfyldes efter den rekursive regel for positive og , og og for . Det kan bevises, at summen af den th række i denne tabel er lig med det th lille Schroeder-tal . $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))$