Nombres de Narayana et son triangle

Édition du: 06/01/2024

INDEX Dénombrement Graphe Jeux et énigmes Logique Topologie	Types de Nombres – GRILLES
	Suites pour dénombrer	Nombres de Catalan	Chemin sur réseau
	Nombres Manhattan	Nombres de Narayana	Chemin auto-évitant
	Taxi dans Manhattan	Nombres de Delannoy	Chemin le plus court
	Périple du cavalier	Nombres octaédriques	Diagramme de Voronoï
	Périple de la tour	Nombres de Motzkin	Nombres de Dyck

Faites un double-clic pour un retour en haut de page

Nombres de NARAYANA

Nombres qui se présentent en triangle comme le triangle Pascal. Nombreuses applications en combinatoire. Par exemple, pour le comptage de la quantité de configurations de parenthèses.

Nom donné d'après Tadepalli Venkata Narayana (1930-1987), un mathématicien indo-canadien.

Sommaire de cette page

>>> Triangle de Narayana ou triangle de Catalan

>>> Exemple de dénombrement: parenthèses

>>> Exemple de dénombrement: chemins

>>> Propriétés des nombres de Narayana

>>> Listes des nombres de Narayana

Débutants

Dénombrement

Glossaire

Combinatoire

Triangle de Narayana ou triangle de Catalan

haut

Nombres de Narayna

Ils se présentent sous la forme d'un triangle selon la valeur de n et de k
N(n, k) est le k-ième nombre sur la ligne n.

Les applications sont nombreuses. Certaines ont présentées en OEIS A001263.

Par exemple: nombre de permutations qui évite {1,3, 2} et qui a k – 1 descentes; nombre de chemins à travers n plaques de verre, entrant et sortant d'un côté, de longueur 2n et avec k réflexions.

Triangle de Narayana

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

Suite >>>

Formule de calcul

Ils sont exprimés en utilisant les coefficients binomiaux.

Rappel du calcul de ces coefficients

Exemple

Voir Suite de Narayana et super nombre d'or

Exemple de dénombrement: parenthèses

haut

N(4,2) = 6

N(4,3) = 6

Quantité de configurations de 4 paires de parenthèses avec soit 2 paires internes (rouge) ou 3 paires.

Pour être complet: configurations avec 1 seule paire et avec quatre paires de parenthèses enfouies.

2 paires internes
dans 4 jeux de parenthèses

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

1 paire interne
dans 4 jeux de parenthèses

(

)

3 paires internes
dans 4 jeux de parenthèses

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

4 paires internes
dans 4 jeux de parenthèses

(

)

(

)

(

)

(

)

Exemple de dénombrement: chemins

haut

Il s'agit de la quantité de chemins de Dyck (Dyck paths) comportant exactement k sommets.

Plus précisément: quantité de chemins de coordonnées (0, 0) à (2n, 0) comportant k sommets et, construits avec des mouvements de type nord-est (1, 1) et sud-est (1, -1) avec y ≥ 0.

Ici, k = 4.

Voir Chemins sur réseaux

Propriétés des nombres de Narayana

haut

Nombres de Catalan

La somme des nombres de Narayana sur la nième ligne est égale au nième nombre de Catalan.

TABLES

Liste des nombres de Narayana (quels que soient n et k)

1, 3, 6, 10, 15, 20, 21, 28, 36, 45, 50, 55, 66, 78, 91, 105, 120, 136, 153, 171, 175, 190, 196, 336, 490, 540, 825, 1176, 1210, 1716, 1764, 2366, 2520, 3185, 4200, 4950, 5292, 5440, 6936, 8721, 9075, 10830, …

Table des nombres de Narayana en triangle jusqu'à n = 20 (donc 20 lignes)

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]

11, [1, 55, 825, 4950, 13860, 19404, 13860, 4950, 825, 55, 1]

12, [1, 66, 1210, 9075, 32670, 60984, 60984, 32670, 9075, 1210, 66, 1]

13, [1, 78, 1716, 15730, 70785, 169884, 226512, 169884, 70785, 15730, 1716, 78, 1]

14, [1, 91, 2366, 26026, 143143, 429429, 736164, 736164, 429429, 143143, 26026, 2366, 91, 1]

15, [1, 105, 3185, 41405, 273273, 1002001, 2147145, 2760615, 2147145, 1002001, 273273, 41405, 3185, 105, 1]

16, [1, 120, 4200, 63700, 496860, 2186184, 5725720, 9202050, 9202050, 5725720, 2186184, 496860, 63700, 4200, 120, 1]

17, [1, 136, 5440, 95200, 866320, 4504864, 14158144, 27810640, 34763300, 27810640, 14158144, 4504864, 866320, 95200, 5440, 136, 1]

18, [1, 153, 6936, 138720, 1456560, 8836464, 32821152, 77364144, 118195220, 118195220, 77364144, 32821152, 8836464, 1456560, 138720, 6936, 153, 1]

19, [1, 171, 8721, 197676, 2372112, 16604784, 71954064, 200443464, 367479684, 449141836, 367479684, 200443464, 71954064, 16604784, 2372112, 197676, 8721, 171, 1]

20, [1, 190, 10830, 276165, 3755844, 30046752, 150233760, 488259720, 1057896060, 1551580888, 1551580888, 1057896060, 488259720, 150233760, 30046752, 3755844, 276165, 10830, 190, 1]

21, [1, 210, 13300, 379050, 5799465, 52581816, 300467520, 1126753200, 2848181700, 4936848280, 5924217936, 4936848280, 2848181700, 1126753200, 300467520, 52581816, 5799465, 379050, 13300, 210, 1]

22, [1, 231, 16170, 512050, 8756055, 89311761, 578399976, 2478857040, 7229999700, 14620666060, 20734762776, 20734762776, 14620666060, 7229999700, 2478857040, 578399976, 89311761, 8756055, 512050, 16170, 231, 1]

23, [1, 253, 19481, 681835, 12954865, 147685461, 1075994073, 5226256926, 17420856420, 40648664980, 67255063876, 79483257308, 67255063876, 40648664980, 17420856420, 5226256926, 1075994073, 147685461, 12954865, 681835, 19481, 253, 1]

24, [1, 276, 23276, 896126, 18818646, 238369516, 1941008916, 10606227291, 40067969766, 106847919376, 203982391536, 281248448936, 281248448936, 203982391536, 106847919376, 40067969766, 10606227291, 1941008916, 238369516, 18818646, 896126, 23276, 276, 1]

25, [1, 300, 27600, 1163800, 26883780, 376372920, 3405278800, 20796524100, 88385227425, 267119798440, 582806832960, 927192688800, 1081724803600, 927192688800, 582806832960, 267119798440, 88385227425, 20796524100, 3405278800, 376372920, 26883780, 1163800, 27600, 300, 1]

26, [1, 325, 32500, 1495000, 37823500, 582481900, 5824819000, 39525557500, 187746398125, 638337753625, 1578435172600, 2869882132000, 3863302870000, 3863302870000, 2869882132000, 1578435172600, 638337753625, 187746398125, 39525557500, 5824819000, 582481900, 37823500, 1495000, 32500, 325, 1]

27, [1, 351, 38025, 1901250, 52474500, 885069900, 9735768900, 73018266750, 385374185625, 1464421905375, 4073755482225, 8394405236100, 12914469594000, 14901311070000, 12914469594000, 8394405236100, 4073755482225, 1464421905375, 385374185625, 73018266750, 9735768900, 885069900, 52474500, 1901250, 38025, 351, 1]

28, [1, 378, 44226, 2395575, 71867250, 1322357400, 15931258200, 131432880150, 766691800875, 3237143159250, 10064572367850, 23331508670925, 40680579221100, 53644719852000, 53644719852000, 40680579221100, 23331508670925, 10064572367850, 3237143159250, 766691800875, 131432880150, 15931258200, 1322357400, 71867250, 2395575, 44226, 378, 1]

29, [1, 406, 51156, 2992626, 97260345, 1945206900, 25565576400, 231003243900, 1482270815025, 6917263803450, 23896002230100, 61912369414350, 121443493851225, 181497968832600, 207426250094400, 181497968832600, 121443493851225, 61912369414350, 23896002230100, 6917263803450, 1482270815025, 231003243900, 25565576400, 1945206900, 97260345, 2992626, 51156, 406, 1]

30, [1, 435, 58870, 3708810, 130179231, 2820550005, 40293571500, 397179490500, 2791289197125, 14328617878575, 54709268263650, 157496378334750, 345280521733875, 580526591486625, 751920156592200, 751920156592200, 580526591486625, 345280521733875, 157496378334750, 54709268263650, 14328617878575, 2791289197125, 397179490500, 40293571500, 2820550005, 130179231, 3708810, 58870, 435, 1]

Haut de page (ou double-clic)

Suite	*Voir* haut de page Nombres de Delannoy Diagramme de Voronoï Chemin eulérien Chemin de la fourmi sur pavé, cylindre … Marche de l'ivrogne Mouvement browniens Courbes de Peano et autre tracés fractals Graphe – Index
Voir	Diagramme de Venn Dominos et graphe Échiquier et graphe Énigmes et paradoxes Intelligence artificielle	Jeux – Index Logique formelle Raisonnement Topologie – Glossaire
Sites	Nombre de Narayana – Wikipédia *OEIS A001263 – Triangle of Narayana numbers T(n,k) = C(n-1,k-1)C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.**
Cette page	http://villemin.gerard.free.fr/LogForm/Narayana.htm