Număr Schröder

Format:Infocaseta Șiruri de numere întregi În matematică, un număr Schröder $S_n,$ numit și număr Schröder mare, descrie numărul de căi dintr-o grilă de la colțul de sud-vest $(0,0)$ al grilei $n\times n$ până la colțul de nord-est $(n,n),$ folosind doar pași simpli spre nord, $(0,1)$, nord-est, $(1,1)$ sau spre est, $(1,0)$ care nu se ridică deasupra diagonalei SW–NE.

Primele câteva numere Schröder sunt:

1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926, 3236724317174, 17518619320890, 95149655201962, 518431875418926, 2832923350929742, 15521467648875090, ...

Ele au fost numite după matematicianul german Ernst Schröder.

Exemple

Următoarea figură arată cele 6 astfel de căi într-o grilă $2\times 2$:

Construcții

O cale Schröder de lungime $n$ este o cale în grilă de la $(0,0)$ la $(2n,0)$ cu pași spre nord-est, $(1,1),$ est, $(2,0)$ și sud-est, $(1,-1),$ care nu coboară sub axa $x$. Al Format:Mvar-lea număr Schröder este numărul căilor Schröder de lungime $n$. Următoarea figură arată cele 6 căi Schröder de lungime 2:

Similar, numerele Schröder enumeră modalitățile de a împărți un dreptunghi în $n+1$ dreptunghiuri mai mici folosind $n$ tăieturi prin $n$ puncte oarecare date în interiorul dreptunghiului, fiecare tăietură intersectând unul dintre puncte și împărțind doar un singur dreptunghi în două (adică, numărul de structuri de tip partiții ghilotină diferite). Acest lucru este similar cu procesul de triangulare, în care o formă este împărțită în triunghiuri care nu se suprapun în loc de dreptunghiuri. Următoarea figură arată cele 6 astfel de împărțiri ale unui dreptunghi în 3 dreptunghiuri folosind două tăieturi:

În imaginea de mai jos sunt cele 22 de împărțiri ale unui dreptunghi în 4 dreptunghiuri folosind trei tăieturi:

Numărul Schröder $S_n$ indică și permutările separabile de lungime $n-1.$

Secvențe asociate

Numerele Schröder sunt numite uneori numere Schröder „mari” deoarece există o altă succesiune Schröder: „numerele Schröder mici”, cunoscute și sub numele numere Schröder–Hiparh sau „ numere super Catalan”. Conexiunile dintre aceste căi pot fi văzute în câteva moduri:

• Fie căile de la $(0,0)$ la $(n,n)$ cu pașii $(1,1),$ $(2,0)$ și $(1,-1)$ care nu se ridică deasupra diagonalei principale. Există două tipuri de căi: cele care au mișcări de-a lungul diagonalei principale și cele care nu. Numerele Schröder (mari) enumeră ambele tipuri de căi, iar numerele Schröder mici enumeră doar căile care ating diagonala, dar nu au pași de-a lungul ei.

• Așa cum există căi Schröder (mari), o cale Schröder mică este o cale Schröder care nu are trepte orizontale pe axa $x$.

• Dacă $S_n$ este al Format:Mvar-lea număr Schröder și $s_n$ este al Format:Mvar-lea număr Schröder mic, atunci $S_n=2s_n$ pentru $n>0$ $(S_0=s_0=1).$

Căile Schröder sunt similare cu căile Dyck, dar admit și pasul orizontal în loc de doar pașii diagonali. Alte căi similară sunt căile Motzkin, care sunt aceleași căi diagonale, dar admit doar un singur pas orizontal, (1,0), și enumeră astfel de căi de la $(0,0)$ la $(n,0)$.

Există și o matrice triunghiulară asociată cu numerele Schröder, care dă o relație de recurență(însă nu doar între numerele Schröder). Primii termeni din matrice sunt:

1, 1, 2, 1, 4, 6, 1, 6, 16, 22, ...

Este mai ușor de văzut conexiunea cu numerele Schröder atunci când secvența este în forma sa triunghiulară:

Format:Mvar Format:Mvar	0	1	2	3	4	5	6
0	1
1	1	2
2	1	4	6
3	1	6	16	22
4	1	8	30	68	90
5	1	10	48	146	304	394
6	1	12	70	264	714	1412	1806

Aici numerele Schröder apar pe diagonală, de exemplu $S_n=T(n,n)$ unde $T(n,k)$ este valoarea din rândul Format:Mvar și coloana Format:Mvar. Relația de recurență dată de această aranjare este

$T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)$

cu $T(1,k)=1$ și $T(n,k)=0$ pentru $k>n$. O altă observație interesantă este că suma din cel de al Format:Mvar-lea rând este al (Format:Mvar+1)-lea număr Schröder mic, adică

$\sum _{k=0}^{n}T(n,k)=s_{n+1}$.

Relația de recurență

$S_n=3S_{n-1}+\sum _{k=1}^{n-2}{S}_k{S}_{n-k-1}$ pentru $n\ge 2$ cu $S_0=1$, $S_1=2$.

Funcția generatoare

Funcția generatoare $G(x)$ a $(S_n)$ este

$G(x)=\frac{1-x-\sqrt{x^2-6x+1}}{2x}=\sum _{n=0}^{\mathrm{\infty }}{S}_n{x}^n$.

Utilizări

Diamant aztec de ordinul 4

Un subiect al combinatoricii sunt formele pavărilor, iar un exemplu particular al acestora este pavarea cu dominouri. În acest caz întrebarea este: „câte dominouri (adică câte dreptunghiuri $1\times 2$ sau $2\times 1$) se pot aranja într-o formă astfel încât niciuna dintre dominouri să nu se suprapună, întreaga formă să fie acoperită și niciunul dintre dominouri să nu iasă afară din formă?". Forma cu care au legătură numerele Schröder este diamantul aztec. Alături este prezentat un diamant aztec de ordinul 4 cu o posibilă pavare domino.

Se pare că determinantul unei matrice Hankel $(2n-1)\times (2n-1)$ de numere Schröder, adică matricea pătrată al cărei element $(i,j)$ este $S_{i+j-1},$ este numărul de pavări cu dominouri ale unui diamant aztec de ordinul $n$, care este $2^{n(n+1)/2}.$

$\left|\begin{array}{cccc}{S}_1& S_2& \cdots & S_n\\ S_2& S_3& \cdots & S_{n+1}\\ ⋮& ⋮& \ddots & ⋮\\ S_n& S_{n+1}& \cdots & S_{2n-1}\end{array}\right|=2^{n(n+1)/2}.$

Exemple:

• $\left|\begin{array}{c}2\end{array}\right|=2=2^{1(2)/2}$

• $\left|\begin{array}{cc}2& 6\\ 6& 22\end{array}\right|=8=2^{2(3)/2}$

• $\left|\begin{array}{ccc}2& 6& 22\\ 6& 22& 90\\ 22& 90& 394\end{array}\right|=64=2^{3(4)/2}$

Lectură suplimentară

• Stanley, Richard P.: Catalan addendum to Enumerative Combinatorics, Volume 2

Vezi și

• Număr Delannoy
• Număr Motzkin
• Număr Narayana
• Număr Schröder–Hiparh
• Număr Catalan

Legături externe

• Format:En icon Format:MathWorld