Enumerative combinatoricsEnumerative 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'entiersEn 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 NarayanaEn 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 .
Langage de DyckEn 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.
Partition d'un ensemblevignette|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 binomialeEn 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).
Arbre binaireEn informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.
Série génératriceEn mathématiques, et notamment en analyse et en combinatoire, une série génératrice (appelée autrefois fonction génératrice, terminologie encore utilisée en particulier dans le contexte de la théorie des probabilités) est une série formelle dont les coefficients codent une suite de nombres (ou plus généralement de polynômes) ; on dit que la série est associée à la suite. Ces séries furent introduites par Abraham de Moivre en 1730, pour obtenir des formules explicites pour des suites définies par récurrence linéaire.
Nombre de BellEn mathématiques, le n-ième nombre de Bell (du nom de Eric Temple Bell) est le nombre de partitions d'un ensemble à n éléments distincts ou, ce qui revient au même, le nombre de relations d'équivalence sur un tel ensemble. Ces nombres forment la suite d'entiers de l'OEIS, dont on peut calculer à la main les premiers termes :Le premier vaut 1 car il existe exactement une partition de l'ensemble vide : la partition vide, formée d'aucune partie. En effet, ses éléments (puisqu'il n'y en a aucun) sont bien non vides et disjoints deux à deux, et de réunion vide.
Coefficient binomialEn mathématiques, les coefficients binomiaux, ou coefficients du binôme, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties à k éléments d'un ensemble à n éléments. On les note - qui se lit « k parmi n » - ou , la lettre C étant l'initiale du mot « combinaison » Les coefficients binomiaux s'expriment à l'aide de la fonction factorielle : Ils interviennent dans de nombreux domaines des mathématiques : développement du binôme en algèbre, dénombrements, développement en série, lois de probabilités, etc.
