Sari la conținut

Număr Schröder

De la Wikipedia, enciclopedia liberă
Număr Schröder
Numit dupăErnst Schröder
Nr. de termeni cunoscuțiinfinit
Primii termeni1, 2, 6, 22, 90, 394, 1806
Index OEIS

În matematică, un număr Schröder numit și număr Schröder mare[1], descrie numărul de căi dintr-o grilă de la colțul de sud-vest al grilei până la colțul de nord-est folosind doar pași simpli spre nord, , nord-est, sau spre est, 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.

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

O cale Schröder de lungime este o cale în grilă de la la cu pași spre nord-est, est, și sud-est, care nu coboară sub axa . Al n-lea număr Schröder este numărul căilor Schröder de lungime .[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 dreptunghiuri mai mici folosind tăieturi prin 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 indică și permutările separabile de lungime

Secvențe asociate

[modificare | modificare sursă]

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 la cu pașii și 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 .[5]
  • Dacă este al n-lea număr Schröder și este al n-lea număr Schröder mic, atunci pentru [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 la .[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 unde este valoarea din rândul n și coloana k. Relația de recurență dată de această aranjare este

cu și pentru .[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ă

.

Relația de recurență

[modificare | modificare sursă]
pentru cu , .[9]

Funcția generatoare

[modificare | modificare sursă]

Funcția generatoare a este[9]

.
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 sau ) 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 de numere Schröder, adică matricea pătrată al cărei element este este numărul de pavări cu dominouri ale unui diamant aztec de ordinul , care este [10]

Exemple:

  1. ^ a b Marius Coman, Enciclopedia matematică a claselor de numere întregi, Columbus, Ohio: Education Publishing, 2013, ISBN: 978-1-59973-237-4, p. 77
  2. ^ a b Șirul A006318 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  3. ^ en Ardila, Federico (). „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. ^ a b en Drake, Dan (). „Bijections from weighted Dyck paths to Schröder paths”. arXiv:1006.1959Accesibil gratuit [math.CO]. 
  6. ^ en Deng, Eva Y. P.; Yan, Wei-Jun (). „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. ^ a b en Sloane, N. J. A. „Triangular array associated with Schroeder numbers”. The On-Line Encyclopedia of Integer Sequences. Accesat în . 
  8. ^ Șirul A033877 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  9. ^ a b en Oi, Feng; Guo, Bai-Ni (). „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.002Accesibil gratuit. 
  10. ^ en Eu, Sen-Peng; Fu, Tung-Shan (). „A simple proof of the Aztec diamond theorem”. Electronic Journal of Combinatorics. 12 (1077–8926): Research Paper 18, 8. 

Lectură suplimentară

[modificare | modificare sursă]

Legături externe

[modificare | modificare sursă]