Vizualizare sursă pentru „Număr Narayana”

{{Infocaseta Șiruri de numere întregi
| named_after = Tadepalli Venkata Narayana
| terms_number = [[infinit]]
| formula = <math>\operatorname{N}(n, k) = \frac{1}{n} {n \choose k} {n \choose k-1}</math>
| OEIS = A001263
| OEIS_name = Triangle of Narayana 
}}
În [[combinatorică]], '''numerele Narayana''' <math>\operatorname{N}(n,k), n \in \mathbb{N}^+, 1 \le k \le n</math> formează un [[tablou triunghiular]] de [[număr natural |numere naturale]], numit '''triunghi Narayana,''' care apar în diferite probleme de combinatorică. Ele sunt numite după [[matematician]]ul [[canadian]] de origine [[india]]nă [[Tadepalli Venkata Narayana]]<ref name=C53>Marius Coman, ''Enciclopedia matematică a claselor de numere întregi'', Columbus, Ohio: Education Publishing, 2013, {{ISBN|978-1-59973-237-4}}, p.&nbsp;53</ref> (1930–1987).

== Formula ==
Numerele Narayana pot fi exprimate în funcție de [[coeficient binomial |coeficienții binomiali]]:<ref name=C53/><ref name=OEIS>{{OEIS|A001263}}</ref>
: <math>\operatorname{N}(n, k) = \frac{1}{n} {n \choose k} {n \choose k-1}</math>

== Valori numerice ==
Primele opt rânduri ale triunghiului Narayana sunt:<ref name=OEIS/>

 <u>''k'' =       1   2   3   4   5   6   7   8</u>
 ''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 <math>\operatorname{N}(n, k)</math>, este numărul de cuvinte care conțin {{tmath|n}} perechi de paranteze, care se împerechează corect (cunoscute drept [[cuvânt Dyck |cuvinte Dyck]]) și care conțin {{tmath|k}} perechi distincte încorporate. De exemplu, <math>\operatorname{N}(4, 2) = 6</math>, deoarece cu patru perechi de paranteze pot fi create șase secvențe care conțin fiecare două apariții submodelului <code>()</code>:

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

Din acest exemplu ar trebui să fie evident că <math>\operatorname{N}(n, 1) = 1</math>, deoarece singurul mod de a obține un singur submodel <code>()</code> este ca toate parantezele de deschidere să fie în primele {{tmath|n}} poziții, urmate de toate parantezele de închidere. De asemenea <math>\operatorname{N}(n, n) = 1</math>, deci {{tmath|n}} perechi incluse distincte pot fi realizate numai prin modelul repetitiv <code>()()()…()</code>.

Se poate arăta că triunghiul Narayana este simetric:
:<math>\operatorname{N}(n, k) = \operatorname{N}(n, n-k+1)</math>

Sumele elementelor de pe rândurile triunghiului sunt [[număr Catalan |numere Catalan]]:
:<math>\operatorname{N}(n, 1) + \operatorname{N}(n, 2) + \operatorname{N}(n, 3) + \cdots + \operatorname{N}(n, n) = C_n</math>

=== Căi monotone în rețea ===
Numerele Narayana indică și numărul de căi în rețea de la <math>(0, 0)</math> la <math>(2n, 0)</math>, cu pași doar spre nord-est și sud-est, fără a coborî sub axa {{mvar|x}}, cu vârfuri {{tmath|k}}.

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

{| class="wikitable"
|-
! <math>\operatorname{N}(4, k)</math>
! Căi
|-
| ''N''(4,&nbsp;1) = '''1''' cale cu 1 vârf:
| [[Fișier:Narayana N(4, 1).svg]]
|-
| ''N''(4,&nbsp;2) = '''6''' căi cu 2 vârfuri:
| [[Fișier:Narayana N(4, 2).svg]]
|-
| ''N''(4,&nbsp;3) = '''6''' căi cu 3 vârfuri:
| [[Fișier:Narayana N(4, 3).svg]]
|-
| ''N''(4,&nbsp;4) = '''1''' cale cu 4 vârfuri:
| [[Fișier:Narayana N(4, 4).svg]]
|}

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

=== Arbori cu rădăcină ===
[[Fișier:Unlabeled ordered rooted trees of 4 edges and 2 leaves.svg|thumb|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 [[arbore (teoria grafurilor) |arborilor cu rădăcină]] ordonați neetichetați cu <math>n</math> muchii și <math>k</math> noduri terminale („frunze”) este egal cu <math>\operatorname{N}(n, k)</math>.

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&nbsp;— 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: <code>()</code>. 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 {{tmath|y}} până la {{tmath|y}}+1 corespunde unui arc între nodul {{tmath | y}} și fiul său. Un nod {{tmath|y}} are atâția fii câte arce ascendente urcă spre el de la linia orizontală la înălțimea {{tmath|y}}. De exemplu, în prima cale pentru <math>\operatorname{N}(4, 3)</math>, nodurile {{math|0}} și {{math|1}} vor avea câte doi fii fiecare; în ultima cale (a șasea), nodul {{math|0}} va avea trei fii iar nodul {{math|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ă ==
[[Fișier:Noncrossing partitions 4; Hasse.svg|thumb|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 {{tmath|n}} elemente se poate partiționa în <math>B_n</math> moduri diferite, unde <math>B_n</math> este al {{tmath|n}}-lea [[număr Bell]]. Mai mult, numărul de moduri de partiționare a unei mulțimi în exact {{tmath|k}} submulțimi (blocuri) este dat de [[Numere Stirling de speța a doua |numerele Stirling de speța a doua]] <math>S(n, k)</math>. 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ție care nu se intersectează|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 {{tmath|n}} elemente ale mulțimii, <math>C_n</math>. Pentru a număra partițiile care nu se intersectează dintr-o mulțime partiționată în exact {{tmath|k}} blocuri se folosește numărul Narayana <math>\operatorname{N}(n, k)</math>.

== Funcția generatoare ==
Funcția generatoare a numerelor Narayana este {{sfn|Petersen|2015|p=25}}
:<math>
\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} \;.
</math>
<!--
  Petersen indexează k de la 0 la n-1.
  Petersen pune un "1" pentru termenul constant, definind C_0(t)=1 și apoi însumând de la n=0.
-->
== Note ==
<references />

== Bibliografie ==
* {{en icon}} {{cite book |author=P. A. MacMahon |title=Combinatorial Analysis |publisher=Cambridge University Press |year=1915–1916}}
* {{en icon}} {{cite book |first=T. Kyle |last=Petersen |chapter=Narayana numbers |title=Eulerian Numbers |series=Birkhäuser Advanced Texts Basler Lehrbücher |publisher=Birkhäuser |place=Basel |year=2015 |chapter-url=https://www.springer.com/cda/content/document/cda_downloaddocument/9781493930906-c1.pdf |doi=10.1007/978-1-4939-3091-3 |isbn=978-1-4939-3090-6 |access-date=2021-05-28 |archive-date=2021-04-21 |archive-url=https://web.archive.org/web/20210421120051/https://www.springer.com/cda/content/document/cda_downloaddocument/9781493930906-c1.pdf |dead-url=yes }}

== 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 icon}} {{MathWorld|title=Narayana Number|urlname=NarayanaNumber}}

[[Categorie:Șiruri de numere întregi|Narayana]]
[[Categorie:Combinatorică]]
[[Categorie:Triunghiuri de numere|Narayana]]