Număr Schröder

Număr Schröder

Numit după	Ernst Schröder
Nr. de termeni cunoscuți	infinit
Primii termeni	1, 2, 6, 22, 90, 394, 1806
Index OEIS	A006318 Large Schröder

În matematică, un număr Schröder ${\displaystyle S_{n},}$ numit și număr Schröder mare^[1], descrie numărul de căi dintr-o grilă de la colțul de sud-vest ${\displaystyle (0,0)}$ al grilei ${\displaystyle n\times n}$ până la colțul de nord-est ${\displaystyle (n,n),}$ folosind doar pași simpli spre nord, ${\displaystyle (0,1)}$, nord-est, ${\displaystyle (1,1)}$ sau spre est, ${\displaystyle (1,0)}$ care nu se ridică deasupra diagonalei SW–NE.^[2]

Primele câteva numere Schröder sunt:^[1][2]

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ă ${\displaystyle 2\times 2}$:

Construcții

O cale Schröder de lungime ${\displaystyle n}$ este o cale în grilă de la ${\displaystyle (0,0)}$ la ${\displaystyle (2n,0)}$ cu pași spre nord-est, ${\displaystyle (1,1),}$ est, ${\displaystyle (2,0)}$ și sud-est, ${\displaystyle (1,-1),}$ care nu coboară sub axa ${\displaystyle x}$. Al n-lea număr Schröder este numărul căilor Schröder de lungime ${\displaystyle n}$.^[3] 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 ${\displaystyle n+1}$ dreptunghiuri mai mici folosind ${\displaystyle n}$ tăieturi prin ${\displaystyle 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 ${\displaystyle S_{n}}$ indică și permutările separabile de lungime ${\displaystyle 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 ${\displaystyle (0,0)}$ la ${\displaystyle (n,n)}$ cu pașii ${\displaystyle (1,1),}$ ${\displaystyle (2,0)}$ și ${\displaystyle (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.^[4]

• 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 ${\displaystyle x}$.^[5]

• Dacă ${\displaystyle S_{n}}$ este al n-lea număr Schröder și ${\displaystyle s_{n}}$ este al n-lea număr Schröder mic, atunci ${\displaystyle S_{n}=2s_{n}}$ pentru ${\displaystyle n>0}$ ${\displaystyle (S_{0}=s_{0}=1).}$^[5]

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 ${\displaystyle (0,0)}$ la ${\displaystyle (n,0)}$.^[6]

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

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ă:

m n	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 ${\displaystyle S_{n}=T(n,n)}$ unde ${\displaystyle T(n,k)}$ este valoarea din rândul n și coloana k. Relația de recurență dată de această aranjare este

${\displaystyle T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)}$

cu ${\displaystyle T(1,k)=1}$ și ${\displaystyle T(n,k)=0}$ pentru ${\displaystyle k>n}$.^[7] O altă observație interesantă este că suma din cel de al n-lea rând este al (n+1)-lea număr Schröder mic, adică

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

Relația de recurență

${\displaystyle S_{n}=3S_{n-1}+\sum _{k=1}^{n-2}S_{k}S_{n-k-1}}$ pentru ${\displaystyle n\geq 2}$ cu ${\displaystyle S_{0}=1}$, ${\displaystyle S_{1}=2}$.^[9]

Funcția generatoare

Funcția generatoare ${\displaystyle G(x)}$ a ${\displaystyle (S_{n})}$ este^[9]

${\displaystyle G(x)={\frac {1-x-{\sqrt {x^{2}-6x+1}}}{2x}}=\sum _{n=0}^{\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 ${\displaystyle 1\times 2}$ sau ${\displaystyle 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 ${\displaystyle (2n-1)\times (2n-1)}$ de numere Schröder, adică matricea pătrată al cărei element ${\displaystyle (i,j)}$ este ${\displaystyle S_{i+j-1},}$ este numărul de pavări cu dominouri ale unui diamant aztec de ordinul ${\displaystyle n}$, care este ${\displaystyle 2^{n(n+1)/2}.}$^[10]

${\displaystyle {\begin{vmatrix}S_{1}&S_{2}&\cdots &S_{n}\\S_{2}&S_{3}&\cdots &S_{n+1}\\\vdots &\vdots &\ddots &\vdots \\S_{n}&S_{n+1}&\cdots &S_{2n-1}\end{vmatrix}}=2^{n(n+1)/2}.}$

Exemple:

• ${\displaystyle {\begin{vmatrix}2\end{vmatrix}}=2=2^{1(2)/2}}$

• ${\displaystyle {\begin{vmatrix}2&6\\6&22\end{vmatrix}}=8=2^{2(3)/2}}$

• ${\displaystyle {\begin{vmatrix}2&6&22\\6&22&90\\22&90&394\end{vmatrix}}=64=2^{3(4)/2}}$

Note

1. ^ Marius Coman, Enciclopedia matematică a claselor de numere întregi, Columbus, Ohio: Education Publishing, 2013, ISBN: 978-1-59973-237-4, p. 77
2. ^ Șirul A006318 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
3. en Ardila, Federico (2015). „Algebraic and geometric methods in enumerative combinatorics”. Handbook of enumerative combinatorics. Boca Raton, FL: CRC Press. p. 3–172. 
4. Șirul A001003 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
5. ^ en Drake, Dan (2010). „Bijections from weighted Dyck paths to Schröder paths”. arXiv:1006.1959  [math.CO]. 
6. en Deng, Eva Y. P.; Yan, Wei-Jun (2008). „Some identities on the Catalan, Motzkin, and Schröder numbers”. Discrete Applied Mathematics. 156 (166–218X): 2781–2789. doi:10.1016/j.dam.2007.11.014. 
7. ^ en Sloane, N. J. A. „Triangular array associated with Schroeder numbers”. The On-Line Encyclopedia of Integer Sequences. Accesat în 5 martie 2018. 
8. Șirul A033877 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
9. ^ en Oi, Feng; Guo, Bai-Ni (2017). „Some explicit and recursive formulas of the large and little Schröder numbers”. Arab Journal of Mathematical Sciences. 23 (1319–5166): 141–147. doi:10.1016/j.ajmsc.2016.06.002 . 
10. en Eu, Sen-Peng; Fu, Tung-Shan (2005). „A simple proof of the Aztec diamond theorem”. Electronic Journal of Combinatorics. 12 (1077–8926): Research Paper 18, 8. 

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

• en Eric W. Weisstein, Schröder Number la MathWorld.