Număr Narayana

Format:Infocaseta Șiruri de numere întregi În combinatorică, numerele Narayana $\mathrm{N}(n,k),n\in {\mathbb{N}}^{+},1\le k\le n$ formează un tablou 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 (1930–1987).

Formula

Numerele Narayana pot fi exprimate în funcție de coeficienții binomiali:

$\mathrm{N}(n,k)=\frac{1}{n}(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n}{k-1})$

Valori numerice

Primele opt rânduri ale triunghiului Narayana sunt:

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 combinatorice

Cuvinte Dyck

Un exemplu de problemă a cărei soluție poate fi dată de numerele Narayana $\mathrm{N}(n,k)$, este numărul de cuvinte care conțin Format:Tmath perechi de paranteze, care se împerechează corect (cunoscute drept cuvinte Dyck) și care conțin Format:Tmath perechi distincte încorporate. De exemplu, $\mathrm{N}(4,2)=6$, 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ă $\mathrm{N}(n,1)=1$, deoarece singurul mod de a obține un singur submodel () este ca toate parantezele de deschidere să fie în primele Format:Tmath poziții, urmate de toate parantezele de închidere. De asemenea $\mathrm{N}(n,n)=1$, deci Format:Tmath perechi incluse distincte pot fi realizate numai prin modelul repetitiv ()()()…().

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

$\mathrm{N}(n,k)=\mathrm{N}(n,n-k+1)$

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

$\mathrm{N}(n,1)+\mathrm{N}(n,2)+\mathrm{N}(n,3)+\cdots +\mathrm{N}(n,n)=C_n$

Căi monotone în rețea

Numerele Narayana indică și numărul de căi în rețea de la $(0,0)$ la $(2n,0)$, cu pași doar spre nord-est și sud-est, fără a coborî sub axa Format:Mvar, cu vârfuri Format:Tmath.

Următoarele figuri reprezintă numerele Narayana $operatornameN(4,k)$, ilustrând simetriile menționate mai sus.

$\mathrm{N}(4,k)$	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 $\mathrm{N}(4,k)$ este 1 + 6 + 6 + 1 = 14, care este al patrulea număr Catalan, $C_4$. Această sumă coincide cu interpretarea numerelor Catalan ca număr de căi monotone de-a lungul marginilor unei grile $n\times n$ care nu trec deasupra diagonalei.

Arbori cu rădăcină

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 $n$ muchii și $k$ noduri terminale („frunze”) este egal cu $\mathrm{N}(n,k)$.

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 Format:Tmath până la Format:Tmath+1 corespunde unui arc între nodul Format:Tmath și fiul său. Un nod Format:Tmath are atâția fii câte arce ascendente urcă spre el de la linia orizontală la înălțimea Format:Tmath. De exemplu, în prima cale pentru $\mathrm{N}(4,3)$, nodurile Format:Math și Format:Math vor avea câte doi fii fiecare; în ultima cale (a șasea), nodul Format:Math va avea trei fii iar nodul Format:Math 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ă

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 Format:Tmath elemente se poate partiționa în $B_n$ moduri diferite, unde $B_n$ este al Format:Tmath-lea număr Bell. Mai mult, numărul de moduri de partiționare a unei mulțimi în exact Format:Tmath submulțimi (blocuri) este dat de numerele Stirling de speța a doua $S(n,k)$. 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 Format:Tmath elemente ale mulțimii, $C_n$. Pentru a număra partițiile care nu se intersectează dintr-o mulțime partiționată în exact Format:Tmath blocuri se folosește numărul Narayana $\mathrm{N}(n,k)$.

Funcția generatoare

Funcția generatoare a numerelor Narayana este Format:Sfn

$\sum _{n=1}^{\mathrm{\infty }}\sum _{k=1}^n\mathrm{N}(n,k)z^n{t}^{k-1}=\frac{1-z(t+1)-\sqrt{1-2z(t+1)+z^2(t-1{)}^2}}{2tz}.$

Bibliografie

• Format:En icon Format:Cite book
• Format:En icon Format:Cite book

Vezi și

• Număr Delannoy
• Număr Motzkin
• Număr Schröder
• Număr Schröder–Hiparh
• Număr Catalan
• Triunghiul lui Pascal

Legături externe

• Format:En icon Format:MathWorld