Nombre de Narayana

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 .