Număr Narayana

Număr Narayana

Numit după	Tadepalli Venkata Narayana
Nr. de termeni cunoscuți	infinit
Formula	$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}$
Index OEIS	A001263 Triangle of Narayana

În combinatorică, numerele Narayana $\operatorname {N} (n,k),n\in \mathbb {N} ^{+},1\leq k\leq 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:

$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose 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 $\operatorname {N} (n,k)$, este numărul de cuvinte care conțin $n$ perechi de paranteze, care se împerechează corect (cunoscute drept cuvinte Dyck) și care conțin $k$ perechi distincte încorporate. De exemplu, $\operatorname {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ă $\operatorname {N} (n,1)=1$, deoarece singurul mod de a obține un singur submodel () este ca toate parantezele de deschidere să fie în primele $n$ poziții, urmate de toate parantezele de închidere. De asemenea $\operatorname {N} (n,n)=1$, deci $n$ perechi incluse distincte pot fi realizate numai prin modelul repetitiv ()()()…().

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

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

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

$\operatorname {N} (n,1)+\operatorname {N} (n,2)+\operatorname {N} (n,3)+\cdots +\operatorname {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 x, cu vârfuri $k$.

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

$\operatorname {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 $\operatorname {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 $\operatorname {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 $y$ până la $y$+1 corespunde unui arc între nodul $y$ și fiul său. Un nod $y$ are atâția fii câte arce ascendente urcă spre el de la linia orizontală la înălțimea $y$. De exemplu, în prima cale pentru $\operatorname {N} (4,3)$, 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ă

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 $n$ elemente se poate partiționa în $B_{n}$ moduri diferite, unde $B_{n}$ este al $n$-lea număr Bell. Mai mult, numărul de moduri de partiționare a unei mulțimi în exact $k$ 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 $n$ elemente ale mulțimii, $C_{n}$. Pentru a număra partițiile care nu se intersectează dintr-o mulțime partiționată în exact $k$ blocuri se folosește numărul Narayana $\operatorname {N} (n,k)$.

Funcția generatoare

Funcția generatoare a numerelor Narayana este

$\sum _{n=1}^{\infty }\sum _{k=1}^{n}\operatorname {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

• en P. A. MacMahon (1915). Combinatorial Analysis. Cambridge University Press. 
• en Petersen, T. Kyle (2015). „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. Arhivat din original (PDF) la 21 aprilie 2021. Accesat în 28 mai 2021. 

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

• en Eric W. Weisstein, Narayana Number la MathWorld.