Numero di Narayana
In matematica, data una griglia rettangolare nel 1° quadrante di un sistema di riferimento cartesiano, il numero di Narayana, , descrive il numero di cammini possibili per arrivare dal punto di coordinate al punto di coordinate e dotati di picchi, ammettendo di potersi muovere soltanto in diagonale verso destra senza poter mai scendere al di sotto della retta di equazione .[1]
Formula
I numeri di Narayana possono essere espressi in termini di coefficienti binomiali in questo modo:[2]
Interpretazioni combinatorie
La successione di tali numeri, , 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/18px-Magnifying_glass_icon_mgx2.svg.png)
Un esempio di problema di enumerazione la cui soluzione può essere data in termini di numeri di Narayana , è il numero di stringhe contenenti 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 di annidamenti distinti. Ad esempio, , 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 , poiché l'unico modo di avere una sotto-stringa ()
è avere tutte le parentesi aperte nelle prime posizioni, seguite da tutte le parentesi chiuse. Inoltre , poiché annidamenti distinti possono essere ottenuti solo con la stringa ()()()…()
.
Più in generale si può dimostrare che il triangolo di Narayana è simmetrico:
La successione delle somme dei numeri presenti nelle righe del triangolo è uguale alla successione dei numeri di Catalan:
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 al punto di coordinate aventi picchi, ammettendo di potersi muovere solo in diagonale verso destra e di non poter scendere al di sotto della retta di equazione .
Le figure seguenti mostrano i numeri di Narayana , illustrando le simmetrie sopra citate:
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 è 1 + 6 + 6 + 1 = 14, che è il quarto numero di Catalan, . Tale somma coincide con l'interpretazione dei numeri di Catalan come numero dei cammini monotoni lungo i lati di una griglia di dimensione che non passano al di sopra della retta di equazione .
Alberi con radice
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Unlabeled_ordered_rooted_trees_of_4_edges_and_2_leaves.svg/220px-Unlabeled_ordered_rooted_trees_of_4_edges_and_2_leaves.svg.png)
Il numero di alberi ordinati, e quindi radicati, con cammini e foglie è rappresentato dal numero di Narayana .[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 a un'altezza corrisponde al cammino tra un nodo e un suo figlio e tale nodo ha tanti figli quanti sono i segmenti diagonali rivolti verso nord-est che partono da un'altezza . Ad esempio, nel primo cammino per , i nodi e avranno due figli per uno; nel senso e ultimo cammino, il nodo avrà tre figli mentre il nodo 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/00/Noncrossing_partitions_4%3B_Hasse.svg/220px-Noncrossing_partitions_4%3B_Hasse.svg.png)
Nello studio delle partizioni si vede che, dato un insieme di elementi, è possibile sezionare tale insieme in modi diversi, dove è l'simo numero di Bell. In aggiunta a questo, il numero di modi in cui si può sezionare tale assieme ottenendo blocchi è dato dal numero di Stirling di seconda specie . Volendo però tenere conto solamente delle partizioni non sovrapponenti di tutti gli elementi di un insieme, si vede che esse sono rappresentate dall' numero di Catelan, mentre le partizioni non sovrapponenti che vedono l'insieme sezionato esattamente in blocchi sono rappresentate dal numero di Narayana .[6]
Funzione generatrice
La funzione generatrice dei numeri di Narayana è:[7]
Note
- ^ Mauro Fiorentini, Narayana (numeri di) (II), su bitman.name, Mauro Fiorentini. URL consultato il 5 maggio 2021.
- ^ a b (EN) Emeric Deutsch, Dyck path enumeration (PDF), in Discrete Mathematics, vol. 204, Elsevier, 1999, pp. 167-202. URL consultato il 3 maggio 2021.
- ^ (EN) N. J. A. Sloane, Sequenza A001263, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
- ^ (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.
- ^ (EN) Antonio Daziario, Statistics on multitype Galton-Watson trees (PDF), Università degli Studi di Milano, 2014. URL consultato il 3 maggio 2021.
- ^ a b (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.
- ^ (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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)