Numero di Narayana

In matematica, data una griglia rettangolare nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Narayana, ${\displaystyle N(n,k)}$, descrive il numero di cammini possibili per arrivare dal punto di coordinate ${\displaystyle (0,0)}$ al punto di coordinate ${\displaystyle (2n,0)}$ e dotati di ${\displaystyle k}$ picchi, ammettendo di potersi muovere soltanto in diagonale verso destra senza poter mai scendere al di sotto della retta di equazione ${\displaystyle y=0}$.^[1]

Formula

I numeri di Narayana possono essere espressi in termini di coefficienti binomiali in questo modo:^[2]

${\displaystyle \operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}.}$

Interpretazioni combinatorie

La successione di tali numeri, ${\displaystyle \operatorname {N} (n,k),n\in \mathbb {N} ^{+},1\leq k\leq n}$, che prendono il nome dal matematico canadese T. V. Narayana, può essere arrangiata in una disposizione triangolare di interi, chiamata "triangolo di Narayana", che compare in diversi problemi di combinatoria enumerativa.

Le prime dieci righe ti tale disposizione sono:^[3]

k =       1   2   3   4   5   6   7   8   9   10
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
    9  |  1  36 336 1176 1764 1176 336 36 1
   10  |  1  45 540 2520 5292 5292 2520 540 45 1

Parole di Dyck

Lo stesso argomento in dettaglio: Parole di Dyck.

Un esempio di problema di enumerazione la cui soluzione può essere data in termini di numeri di Narayana ${\displaystyle \operatorname {N} (n,k)}$, è il numero di stringhe contenenti ${\displaystyle n}$ coppie di parentesi, disposte in maniera completa (ad ogni parentesi aperta ne corrisponde una chiusa) e logicamente coerente (le parentesi sono correttamente annidate e non vi è mai una parentesi chiusa senza che prima ci sia la relativa parentesi aperta), e un numero ${\displaystyle k}$ di annidamenti distinti. Ad esempio, ${\displaystyle \operatorname {N} (4,2)=6}$, poiché con quattro paia di parentesi si possono creare sei stringhe ognuna delle quali contenente due soli schemi ():^[2]

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

Da questo esempio risulta evidente che ${\displaystyle \operatorname {N} (n,1)=1}$, poiché l'unico modo di avere una sotto-stringa () è avere tutte le parentesi aperte nelle prime ${\displaystyle n}$ posizioni, seguite da tutte le parentesi chiuse. Inoltre ${\displaystyle \operatorname {N} (n,n)=1}$, poiché ${\displaystyle n}$ annidamenti distinti possono essere ottenuti solo con la stringa ()()()…().

Più in generale si può dimostrare che il triangolo di Narayana è simmetrico:

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

La successione delle somme dei numeri presenti nelle righe del triangolo è uguale alla successione dei numeri di Catalan:

${\displaystyle \operatorname {N} (n,1)+\operatorname {N} (n,2)+\operatorname {N} (n,3)+\cdots +\operatorname {N} (n,n)=C_{n}.}$

Cammini reticolari monotoni

Come detto nell'incipit, dato un sistema di riferimento cartesiano, i numeri di Narayana rappresentano anche i cammini reticolari per andare dal punto di coordinate ${\displaystyle (0,0)}$ al punto di coordinate ${\displaystyle (2n,0)}$ aventi ${\displaystyle k}$ picchi, ammettendo di potersi muovere solo in diagonale verso destra e di non poter scendere al di sotto della retta di equazione ${\displaystyle y=0}$.

Le figure seguenti mostrano i numeri di Narayana ${\displaystyle \operatorname {N} (4,k)}$, illustrando le simmetrie sopra citate:

${\displaystyle \operatorname {N} (4,k)}$	Paths
N(4, 1) = 1 cammino con 1 picco
N(4, 2) = 6 cammini con 2 picchi:
N(4, 3) = 6 cammini con 3 picchi:
N(4, 4) = 1 cammino con path 4 picchi:

La somma dei numeri ${\displaystyle \operatorname {N} (4,k)}$ è 1 + 6 + 6 + 1 = 14, che è il quarto numero di Catalan, ${\displaystyle C_{4}}$. Tale somma coincide con l'interpretazione dei numeri di Catalan come numero dei cammini monotoni lungo i lati di una griglia di dimensione ${\displaystyle n\times n}$ che non passano al di sopra della retta di equazione ${\displaystyle y=x}$.

Alberi con radice

I 6 alberi alberi ordinati con 4 cammini e 2 foglie, corrispondenti al numero di Narayana ${\displaystyle N(4,2)}$.

Il numero di alberi ordinati, e quindi radicati, con ${\displaystyle n}$ cammini e ${\displaystyle k}$ foglie è rappresentato dal numero di Narayana ${\displaystyle \operatorname {N} (n,k)}$.^[4][5][6] Ciò è analogo agli esempi precedentemente illustrati:

• Ogni parola di Dyck può essere rappresentata come un albero radicato. Partendo da un singolo nodo, la radice, che sarà il nodo attivo iniziale, ciò equivale a leggere una parola da sinistra a destra, partendo da una parentesi aperta e aggiungendo poi al nodo attivo un figlio che diventa il nuovo nodo attivo. Quando si incontra il simbolo di parentesi chiusa, il nodo attivo torna a essere il genitore del precedente nodo attivo. In questo modo si ottiene un albero in cui ogni nodo che non è la radice corrisponde a una coppia di parentesi aperta e chiusa, e i cui figli sono i nodi corrispondenti alle successive parole di Dyck contenute all'interno di tali parentesi. Le foglie dell'albero corrispondono invece alle coppie di parentesi vuote, ossia agli schemi (). In modo analogo si può costruire una parola di Dyck da un albero radicato attraverso una ricerca in profondità, evidenziando quindi l'esistenza di un isomorfismo tra parole di Dyck e alberi radicati.
• Nelle soprastanti figure di cammini reticolari, ogni segmento diagonale che va da un'altezza ${\displaystyle y}$ a un'altezza ${\displaystyle y+1}$ corrisponde al cammino tra un nodo ${\displaystyle y}$ e un suo figlio e tale nodo ${\displaystyle y}$ ha tanti figli quanti sono i segmenti diagonali rivolti verso nord-est che partono da un'altezza ${\displaystyle y}$. Ad esempio, nel primo cammino per ${\displaystyle \operatorname {N} (4,3)}$, i nodi ${\displaystyle 0}$ e ${\displaystyle 1}$ avranno due figli per uno; nel senso e ultimo cammino, il nodo ${\displaystyle 0}$ avrà tre figli mentre il nodo ${\displaystyle 1}$ ne avrà soltanto uno. Per costruire un albero radicato da un cammino reticolare e viceversa, si può impiegare un algoritmo simile a quello menzionato nel paragrafo precedente. Così come accade con le parole di Dyck, esiste quindi anche un isomorfismo tra cammini reticolari e alberi radicati.

Partizioni

Le partizioni non sovrapponenti 1,6,6,1 con blocchi 1,2,3,4 di insiemi da 4 elementi

Nello studio delle partizioni si vede che, dato un insieme di ${\displaystyle n}$ elementi, è possibile sezionare tale insieme in ${\displaystyle B_{n}}$ modi diversi, dove ${\displaystyle B_{n}}$ è l'${\displaystyle n-}$simo numero di Bell. In aggiunta a questo, il numero di modi in cui si può sezionare tale assieme ottenendo ${\displaystyle k}$ blocchi è dato dal numero di Stirling di seconda specie ${\displaystyle S(n,k)}$. Volendo però tenere conto solamente delle partizioni non sovrapponenti di tutti gli ${\displaystyle n}$ elementi di un insieme, si vede che esse sono rappresentate dall'${\displaystyle n}$ numero di Catelan, mentre le partizioni non sovrapponenti che vedono l'insieme sezionato esattamente in ${\displaystyle k}$ blocchi sono rappresentate dal numero di Narayana ${\displaystyle \operatorname {N} (n,k)}$.^[6]

Funzione generatrice

La funzione generatrice dei numeri di Narayana è:^[7]

${\displaystyle \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}}.}$

Note

1. Mauro Fiorentini, Narayana (numeri di) (II), su bitman.name, Mauro Fiorentini. URL consultato il 5 maggio 2021.
2. (EN) Emeric Deutsch, Dyck path enumeration (PDF), in Discrete Mathematics, vol. 204, Elsevier, 1999, pp. 167-202. URL consultato il 3 maggio 2021.
3. (EN) N. J. A. Sloane, Sequenza A001263, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
4. (EN) Giacomo Aletti e Antonio Daziario, Full binary trees, Narayana numbers and two-dimensional decompositions of integers (PDF), arXiv, Dicembre 2014. URL consultato il 3 maggio 2021.
5. (EN) Antonio Daziario, Statistics on multitype Galton-Watson trees (PDF), Università degli Studi di Milano, 2014. URL consultato il 3 maggio 2021.
6. (EN) Nachum Dershowitz e Shmuel Zaks, Ordered trees and non-crossing partitions (PDF) ^{[collegamento interrotto]}, in Discrete Mathematics, vol. 62, Elsevier, 1986, pp. 215-218. URL consultato il 3 maggio 2021.
7. (EN) T. Kyle Petersen, Narayana numbers (PDF), in Eulerian Numbers, Birkhäuser, 2015, DOI:10.1007/978-1-4939-3091-3, ISBN 978-1-4939-3090-6. URL consultato il 3 maggio 2021 (archiviato dall'url originale il 21 aprile 2021).

Voci correlate

• Numero di Delannoy
• Numero di Motzkin
• Numero di Schröder
• Numero di Schröder-Ipparco

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Numero di Narayana

Collegamenti esterni

• (EN) Eric W. Weisstein, Numero di Narayana, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica