Numărul Narayana

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 iunie 2020; verificările necesită 2 modificări .

Numărul Narayana este un număr exprimat în termeni de coeficienți binomi ( ): $k\leqslant n$

N(n,k)={\frac {1}{n}}{n \alegeți k}{n \alegeți k-1}

;

astfel de numere formează triunghiul Narayana , o matrice triunghiulară inferioară de numere naturale care apare într-un număr de probleme de combinatorie enumerativă .

Au fost descoperite de matematicianul canadian de origine indiană Tadepalli Narayana (1930-1987) la rezolvarea următoarei probleme: găsiți numărul de vaci și juninci care au apărut de la o vacă în 20 de ani, cu condiția ca vaca la începutul fiecărui an să dea naștere la o junincă, iar juninca naște același pui la începutul anului, atingând vârsta de trei ani.

Primele opt rânduri de numere Narayana [1] :

k = 1 2 3 4 5 6 7 8 n = 1 | unu 2 | unsprezece 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

Aplicații și proprietăți

Un exemplu de problemă de numărare a cărei soluție poate fi dată în termeni de numere Narayana este numărul de expresii care conțin perechi de paranteze care sunt potrivite corect și care conțin imbricații diferite. De exemplu, cum patru perechi de paranteze formează șase secvențe diferite care conțin două cuibări (prin cuibărire, înțelegem un model ): $N(n,k)$ $n$ $k$ $N(4,2)=6$ ()

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

Exemplul demonstrează că , deoarece singura modalitate de a obține un singur model este deschiderea parantezelor și apoi închiderea parantezelor. De asemenea , deoarece singura opțiune este secvența . Mai general, se poate demonstra că triunghiul lui Narayana are următoarea proprietate de simetrie: $N(n,1)=1$ () $n$ $n$ $N(n,n)=1$ ()()() … ()

N(n,k)=N(n,n-k+1)

Suma rândurilor triunghiului Narayana este egală cu numerele catalane corespunzătoare :

N(n,1)+N(n,2)+N(n,3)+\cdots +N(n,n)=C_{n)

astfel, numerele Narayana numără, de asemenea, numărul de căi pe o rețea întreagă bidimensională de la până la când se deplasează numai de-a lungul diagonalelor de nord-est și sud-est, fără a devia sub axa x , cu maxime locale. Cifre rezultate din : $(0, 0)$ $(2n,0)$ $k$ $N(4,k)$

$N(4,k)$	Căi
$N(4,1)=1$ cale cu un maxim:
$N(4,2)=6$ căi cu două maxime:
$N(4,3)=6$ căi cu trei maxime:
$N(4,4)=1$ cale cu patru maxime:

Suma este 1 + 6 + 6 + 1 = 14, care este numărul catalan . $N(4,k)$ $C_{4}$

Funcția de generare a numerelor Narayana [2] :

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

Note

↑ Secvența OEIS A001263 _
↑ Petersen, 2015 , p. 25.

Literatură

PA MacMahon. Analiza combinatorie (nedefinita) . - Cambridge University Press , 1915-1916.
Petersen, T. Kyle. Numerele Narayana // Numerele euleriene (neopr.) . - Basel: Birkhauser, 2015. - doi : 10.1007/978-1-4939-3091-3 .

Clase de numere naturale

Puteri și
numere aferente

Numerele de forma
a × 2 b ± 1

Alte numere
polinomiale

Numere
definite recursiv

Seturi de numere
cu
proprietăți specifice

Exprimat
în termeni de sume

Non-ipotenuză
Practic
Principalul semisimplu
Ulama
Wolsenholm

Obținut
cu o sită

numere norocoase

Coduri înrudite
_

Mirtens

numere ondulate

2-dimensională

centrat _	triunghiular pătrat pentagonal hexagonal heptagonală octogonală neunghiulară decagonală stelat
decentrat _	triunghiular pătrat triunghiular pătrat hexagonal octogonală

3 dimensionale

centrat _	tetraedric cub octaedric dodecaedral icosaedric
decentrat _	tetraedric octaedric dodecaedral icosaedric Steaua-octaedrică
piramidal _	pătrat pentagonal hexagonal heptagonală

4-dimensională

centrat _	pentachoric triunghiular într-un pătrat
decentrat _	pentatop

Pseudosimple

Carmichael
Catalana
eliptic
Euler
Euler-Jacobi
Fermă
Frobenius
Luca
Somera - Luca
puternic pseudosimplu

numere combinatorii

Funcții aritmetice

σ( n )	redundant aproape perfect aritmetic colosal de redundant Descartes numere hemiperfecte numere extrem de redundante numere cu componente înalte numere hiperperfecte numere multiperfecte comise practic redundant primitiv usor redundante numerele tau numere maiestuoase numere supraabundente numere supercompozite numere superperfecte
Ω( n )	aproape simplu semisimplu
φ( n )	foarte covalent înalt cu răbdare perfect totient uşor toţios
s( n )	prietenos logodit insuficient semi-perfect

Euclid
numere de avere

Prin divizori

Alți
divizori primi sau
legați
de divizibilitate

Matematică distractivă

Sisteme numerice	număr automorf ciclic Osiris Dudeni cifre egale extravagant Factorion Friedman multumit Nivena Kita Lichrel suma cu cifra lipsă Armstrong palindromic pandigitală parazitar dăunătoare magic primitiv repdigits reunește autogenerat autodescriptivă Smarandsha - Wellena strict non-palindromic schimbatoare deplasare trimorf ondulat vampiri

secvența Aronson
numere de clătite