Numerele Schroeder

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 5 iunie 2019; verificările necesită 8 modificări .

Numerele Schröder ( germană: Schröder ) (mai precis, numerele Schröder mari) în combinatorică descriu numărul de căi de la colțul din stânga jos al unei rețele pătrate n × n până la colțul diagonal opus, folosind doar sus, dreapta sau sus se mută („ Mișcarea regelui ”), cu condiția suplimentară ca căile să nu se ridice deasupra diagonalei menționate. Această condiție suplimentară este cea care distinge această secvență de numerele Delannoy . Numit după matematicianul german Ernest Schröder .

Secvența numerelor mari Schroeder începe astfel:

1, 2, 6, 22, 90, 394, 1806, 8558, …. secvența A006318 în OEIS .

Richard Stanley, profesor la Institutul Politehnic din Massachusetts, susține că Hipparchus a calculat al 10-lea număr Schroeder 1037718 fără a menționa cum a ajuns la el.

Exemplu

Figura de mai jos arată 6 căi Schroeder pe o grilă 2×2:

Numerele Schroeder mari și mici

Numerele Schroeder mari numără numărul de căi de la punctul (0, 0) la (2 , 0) folosind doar pași în sus sau în jos (pași (1, 1) sau (1, -1)) sau pași dubli la dreapta ( 2, 0), care nu se încadrează sub axa x . $S_{n+1}$ $n$

Numerele Schroeder mici se disting prin faptul că pașii dubli spre dreapta, situati pe axa absciselor, sunt interziși. Evident . Numerele Schroeder mici rămase sunt jumătate din numerele mari corespunzătoare: la . $s_{n}$ $s_{0}=S_{0}=1$ $S_{n}=2s_{n}$ $n>0$

Pentru a demonstra această egalitate, construim o bijecție între căile Schroeder care au un pas situat pe axa absciselor și căi de aceeași lungime care nu au un astfel de pas. Dacă există cel puțin o treaptă orizontală în traseul Schroeder care se află la același nivel cu începutul căii, luați în considerare pasul din stânga (roșu) și, fără a schimba partea anterioară (verde), puneți următorul (albastru) parte pe „picioare” .

Definiții echivalente

Un număr Schroeder mare este egal cu numărul de moduri de a împărți un dreptunghi în n + 1 dreptunghiuri mai mici folosind n tăieturi, cu constrângerea că există n puncte în interiorul dreptunghiului, dintre care două nu se află pe aceeași linie paralelă cu laturile. a dreptunghiului, iar fiecare tăietură trece printr-unul dintre aceste puncte și împarte doar un dreptunghi în două. Figura arată 6 moduri de a tăia în 3 dreptunghiuri folosind 2 tăieturi:

Numerele mari Schroeder sunt situate de-a lungul diagonalei următorului tabel: , unde este numărul rândului --lea al coloanei --lea. $S_{n}=T(n,n)$ $T(n,k)$ $n$ $k$

	0	unu	2	3	patru	5	6
0	unu
unu	unu	2
2	unu	patru	6
3	unu	6	16	22
patru	unu	opt	treizeci	68	90
5	unu	zece	48	146	304	394
6	unu	12	70	264	714	1412	1806

Tabelul este completat conform regulii recursive pentru pozitiv și , și și pentru . Se poate dovedi că suma celui de-al treilea rând al acestui tabel este egală cu al treilea număr Schroeder mic . $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)$ $\sum _{k=0}^{n}T(n,k)=s_{n+1)$

Proprietăți

Numerele Schroeder satisfac relația de recurență : $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\;.

Funcție generatoare :

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

Aplicații

Numerele Schroeder pot fi folosite pentru a calcula numărul de despărțiri dintr-un diamant aztec .

Vezi și

Link -uri

Weisstein, Eric W. Schröder Number (engleză) pe site-ul Wolfram MathWorld .
Richard P. Stanley: Anexă la numerele catalane în combinatorică enumerativă, volumul 2 ( Combinatorică enumerativă )