Număr Narayana

În combinatorică, numerele Narayana formează o matrice triunghiulară de numere naturale, numit triunghi Narayana, care apar în diferite probleme de combinatorică. Ele sunt numite după matematicianul canadian de origine indiană Tadepalli Venkata Narayana[1] (1930–1987).

Număr Narayana
Numit dupăTadepalli Venkata Narayana
Nr. de termeni cunoscuțiinfinit
Formula
Index OEIS

FormulaModificare

Numerele Narayana pot fi exprimate în funcție de coeficienții binomiali:[1][2]

 

Valori numericeModificare

Primele opt rânduri ale triunghiului Narayana sunt:[2]

k =       1   2   3   4   5   6   7   8
n = 1  |  1
    2  |  1   1
    3  |  1   3   1
    4  |  1   6   6   1
    5  |  1  10  20  10   1
    6  |  1  15  50  50  15   1
    7  |  1  21 105 175 105  21   1
    8  |  1  28 196 490 490 196  28   1

Interpretări combinatoriceModificare

Cuvinte DyckModificare

Un exemplu de problemă a cărei soluție poate fi dată de numerele Narayana  , este numărul de cuvinte care conțin   perechi de paranteze, care se împerechează corect (cunoscute drept cuvinte Dyck) și care conțin   perechi distincte încorporate. De exemplu,  , deoarece cu patru perechi de paranteze pot fi create șase secvențe care conțin fiecare două apariții submodelului ():

(()(()))  ((()()))  ((())())
()((()))  (())(())  ((()))()

Din acest exemplu ar trebui să fie evident că  , deoarece singurul mod de a obține un singur submodel () este ca toate parantezele de deschidere să fie în primele   poziții, urmate de toate parantezele de închidere. De asemenea  , deci   perechi incluse distincte pot fi realizate numai prin modelul repetitiv ()()()…().

Se poate arăta că triunghiul Narayana este simetric:

 

Sumele elementelor de pe rândurile triunghiului sunt numere Catalan:

 

Căi monotone în rețeaModificare

Numerele Narayana indică și numărul de căi în rețea de la   la  , cu pași doar spre nord-est și sud-est, fără a coborî sub axa x, cu vârfuri  .

Următoarele figuri reprezintă numerele Narayana  , ilustrând simetriile menționate mai sus.

  Căi
N(4, 1) = 1 cale cu 1 vârf:  
N(4, 2) = 6 căi cu 2 vârfuri:  
N(4, 3) = 6 căi cu 3 vârfuri:  
N(4, 4) = 1 cale cu 4 vârfuri:  

Suma lui   este 1 + 6 + 6 + 1 = 14, care este al patrulea număr Catalan,  . Această sumă coincide cu interpretarea numerelor Catalan ca număr de căi monotone de-a lungul marginilor unei grile   care nu trec deasupra diagonalei.

Arbori cu rădăcinăModificare

 
Cei 6 arbori cu rădăcină ordonați cu 4 niveluri și două noduri terminale, corespunzând numărului Narayana N(4, 2)

Numărul arborilor cu rădăcină ordonați neetichetați cu   muchii și   noduri terminale („frunze”) este egal cu  .

Acest lucru este analog exemplelor de mai sus:

  • Fiecare cuvânt Dyck poate fi reprezentat ca un arbore cu rădăcină. Se începe cu un singur nod — nodul rădăcină. Inițial acesta este nodul activ. Citind cuvântul de la stânga la dreapta, atunci când simbolul este o paranteză de deschidere, se adaugă un fiu la nodul activ și se stabilește acest fiu ca nod activ. Când simbolul este o paranteză de închidere, se stabilește părintele nodului activ ca nod activ. Astfel se obține un arbore în care fiecare nod care nu este vârful (nodul rădăcină) corespunde unei perechi de paranteze, iar fiii săi sunt nodurile corespunzătoare cuvintelor Dyck succesive din aceste perechi de paranteze. Nodurile terminale corespund parantezelor goale: (). Similar, putem construi un cuvânt Dyck dintr-un arbore cu rădăcină printr-o căutare în profunzime. Astfel, există un izomorfism între cuvintele Dyck și arborii cu rădăcină.
  • În figurile de mai sus ale căilor din rețea, fiecare segment ascendent față de orizontală de la înălțimea   până la  +1 corespunde unui arc între nodul   și fiul său. Un nod   are atâția fii câte arce ascendente urcă spre el de la linia orizontală la înălțimea  . De exemplu, în prima cale pentru  , nodurile 0 și 1 vor avea câte doi fii fiecare; în ultima cale (a șasea), nodul 0 va avea trei fii iar nodul 1 va avea un fiu. Pentru a construi un arbore cu rădăcină pentru o cale în rețea și invers, se poate folosi un algoritm similar cu cel menționat în paragraful anterior. Ca și în cazul cuvintelor Dyck, există un izomorfism între căile în rețea și arborii cu rădăcină.

Partiții care nu se intersecteazăModificare

 
Cele 1,6,6,1 partiții care nu se intersectează cu submulțimi de 1, 2, 3 sau 4 elemente dintr-o mulțime cu 4 elemente

În studiul partițiilor, se vede că o mulțime formată din   elemente se poate partiționa în   moduri diferite, unde   este al  -lea număr Bell. Mai mult, numărul de moduri de partiționare a unei mulțimi în exact   submulțimi (blocuri) este dat de numerele Stirling de speța a doua  . Ambele aceste concepte sunt puțin alături de subiectul articolului, dar sunt o bază necesară pentru înțelegerea utilizării numerelor Narayana. În ambele noțiuni de mai sus sunt numărate partițiile care se intersectează.

Pentru a elimina partițiile care se intersectează și a număra doar cele care nu se intersectează se pot folosi numerele Catalan pentru a număra partițiile care nu se intersectează pentru toate blocurile de   elemente ale mulțimii,  . Pentru a număra partițiile care nu se intersectează dintr-o mulțime partiționată în exact   blocuri se folosește numărul Narayana  .

Funcția generatoareModificare

Funcția generatoare a numerelor Narayana este [3]

 

NoteModificare

  1. ^ a b Marius Coman, Enciclopedia matematică a claselor de numere întregi, Columbus, Ohio: Education Publishing, 2013, ISBN: 978-1-59973-237-4, p. 53
  2. ^ a b Șirul A001263 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  3. ^ Petersen 2015, p. 25.

BibliografieModificare

  • en P. A. MacMahon (). Combinatorial Analysis. Cambridge University Press. 
  • en Petersen, T. Kyle (). „Narayana numbers” (PDF). Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Basel: Birkhäuser. doi:10.1007/978-1-4939-3091-3. ISBN 978-1-4939-3090-6. 

Vezi șiModificare

Legături externeModificare