Concept
Nombre de Catalan
Concepts associés (16)
Enumerative combinatorics
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n.
Suite d'entiers
En mathématiques, une suite d'entiers est une séquence (c'est-à-dire une succession ordonnée) de nombres entiers. Une suite d'entiers peut être précisée explicitement en donnant une formule pour son n-ième terme générique, ou implicitement en donnant une relation entre ses termes. Par exemple la suite de Fibonacci (0, 1, 1, 2, 3, 5, 8, 13, ...) peut être définie : implicitement, par récurrence : ; explicitement, par la formule de Binet : .
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 .
Combinatorial class
In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size. The counting sequence of a combinatorial class is the sequence of the numbers of elements of size i for i = 0, 1, 2, ...; it may also be described as a generating function that has these numbers as its coefficients. The counting sequences of combinatorial classes are the main subject of study of enumerative combinatorics.
Langage de Dyck
En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l'ensemble des mots bien parenthésés, sur un alphabet fini de parenthèses ouvrantes et fermantes. Par exemple, sur la paire de parenthèses formée de '(' et ')', le mot '(())()' est un mot bien parenthésé, alors que le mot '())(' ne l'est pas. Les langages de Dyck jouent un rôle important en informatique théorique pour caractériser les langages algébriques.
Associaèdre
thumb|K5 est le diagramme de Hasse du treillis de Tamari T4. thumb|Les 9 faces de K5. Chaque sommet du diagramme de Hasse possède les ovales des trois faces adjacente. Les faces dont les ovales s'intersectent ne se touchent pas. En mathématiques, et notamment en combinatoire algébrique, un associaèdre est une réalisation géométrique d'un treillis de Tamari. L'associaèdre Kn est un polytope (polyèdre convexe et borné) de dimension n-2 dans lequel chaque sommet correspond à une façon d'insérer des parenthèses ouvrantes et fermantes dans un mot de n lettres, et les arêtes correspondent à une application de la règle d'associativité.
Motif (permutations)
En combinatoire et en informatique théorique, un motif dans une permutation, aussi appelé sous-permutation, est une notion permettant de restreindre une permutation pour obtenir une permutation plus petite. Toute permutation de longueur n peut être écrite en notation à une ligne comme une suite de chiffres représentant le résultat de l'application de la permutation aux entiers 1,...,n. Par exemple, la suite d'entiers 213 représente la transposition de longueur 3 qui échange 1 et 2.
Partition d'un ensemble
vignette|Les 52 partitions d'un ensemble à 5 éléments. Les points noirs représentent les éléments de l'ensemble. Une région colorée correspond à un bloc de la partition qui regroupe plusieurs points noirs. Un point noir isolé signifie que cet élément appartient à un bloc qui est un singleton. En mathématiques, une partition d'un ensemble X est un ensemble de parties non vides de X deux à deux disjointes et dont l'union est X. Soit un ensemble X.
Transformation binomiale
En mathématiques, dans le domaine de l'analyse combinatoire, une suite est la transformation binomiale d'une autre si elle calcule les différences d'ordre successif entre les termes consécutifs. Cette transformation est en rapport avec la transformation d'Euler, qui est le lien entre les séries génératrices ordinaires de deux suites qui sont la transformée binomiale l'une de l'autre. Un cas particulier de la transformation d'Euler est parfois utilisé pour accélérer la convergence de séries alternées (voir l'accélération des séries).
Partition non croisée
vignette|Au dessus, les 42 partitions non croisées d'un ensemble à 5 éléments. En dessous, les 10 partitions restantes. En mathématiques, une partition non croisée est une partition d'un ensemble fini en blocs qui ne se croisent pas. Soit un entier naturel et une partition de l'ensemble . Cette partition est dite non croisée si pour tout , les blocs et ne sont pas croisés, c'est-à-dire que pour tout il n'est pas vrai que . Par exemple est une partition non croisée pour mais n'en est pas une.