Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Nombre de Narayana
Résumé
En combinatoire, les nombres de Narayana , pour et forment un tableau triangulaire d'entiers naturels, appelé triangle de Narayana ou triangle de Catalan. Ces nombres interviennent dans divers problèmes de dénombrements. Ils portent le nom de Tadepalli Venkata Narayana (1930-1987), mathématicien canadien.
Les nombres de Narayana s'expriment en fonction des coefficients binomiaux par la relation :
On trouve aussi la définition équivalente :
Les premiers nombres du triangle de Narayana sont les suivants :
Ils forment la . La somme des nombres d'une ligne du triangle est un nombre de Catalan :
Le nombre compte le nombre de parenthésages corrects en paires de parenthèses et qui contiennent occurrences de la paire '()'. Par exemple, compte les mots avec 4 paires de parenthèses (donc de longueur 8) et qui contiennent exactement 2 fois la paire '()'. On a , les six parenthésages sont :
()((())) (())(()) (()(())) ((()())) ((())()) ((()))()
On voit facilement que , puisque la condition implique que toutes les parenthèses ouvrantes précèdent toutes les parenthèses fermantes. De même, , le seul parenthésage possible est ()() ... (). Plus généralement, on peut prouver que le triangle de Narayan est symétrique, c'est-à-dire que
Si l'on représente un parenthésage par un chemin de Dyck, le nombre compte les chemins de Dyck de longueur qui ont exactement pics, c'est-à-dire de pas montants suivis immédiatement d'un pas descendant. Les figures suivantes représentent les chemins comptés par les nombres :
thumb|Les 14 partitions non croisées de 4 éléments. Il y en a 1, 6, 6, 1 en respectivement 1, 2, 3, ou 4 parts.
Partition non croisée
thumb|Dans la partie supérieure, les 42 partitions non croisées de 5 éléments ; dans la partie inférieure, les 10 autres partitions.
On considère un ensemble à éléments qui est ordonné de manière cyclique comme les sommets d'un polygone. Une partition de est non croisée (dans la terminologie de ) si deux parties de la partition ne peuvent pas se croiser au sens suivant : si et appartiennent à un bloc et et à un autre bloc, ils ne sont pas rangés dans l'ordre .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.