Concept
Enumerative combinatorics
Concepts associés (15)
Combinatorial principles
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion–exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets have the same number of elements. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in a discrete context.
Nombre de Catalan
En mathématiques, et plus particulièrement en combinatoire, les nombres de Catalan forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement, impliquant souvent des objets définis de façon récursive. Ils sont nommés ainsi en l'honneur du mathématicien belge Eugène Charles Catalan (1814-1894) qui les a étudiés en 1838, mais étaient déjà connus d'Euler. Le nombre de Catalan d'indice n est défini par : Pour , on peut écrire : (voir Coefficient binomial central).
Indicateur de cycles
En combinatoire, un indicateur de cycles est un polynôme en plusieurs variables qui porte certaines informations sur l'action d'un groupe de permutations. Cette manière algébrique et condensée de stocker des informations est souvent utilisée dans des problèmes de dénombrement. Toute permutation π d'un ensemble fini partitionne cet ensemble en cycles ; le monôme indicateur de cycles de π est un produit de puissances des variables a, a, ... qui décrit le « type » de cette partition, ou « type de cycles » de π : l'exposant de a est le nombre de cycles de π de longueur i.
Combinatoire analytique
En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en analytic combinatorics) est un ensemble de techniques décrivant des problèmes combinatoires dans le langage des séries génératrices, et s'appuyant en particulier sur l'analyse complexe pour obtenir des résultats asymptotiques sur les objets combinatoires initiaux. Les résultats de combinatoire analytique permettent notamment une analyse fine de la complexité de certains algorithmes.
Enumeration
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (for example, whether the set must be finite, or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem. Some sets can be enumerated by means of a natural ordering (such as 1, 2, 3, 4, ...
Compte
Le mot compte peut référer au verbe compter, au sens de dénombrer. Un compte peut aussi référer à des unités de valeur, et à des listes utilisées par exemple par des entreprises, comme les banques et instituts financiers. Le verbe compter et le substantif compte, autrefois comput dans sa forme savante ou mathématique, proviennent respectivement de l'évolution du verbe latin computāre, signifiant "égaliser des sommes d'argent, des montants de même valeur pour assurer une transaction équilibrée...
Série génératrice
En 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.
Stirling numbers of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.
Combinaison sans répétition
Les combinaisons sont un concept de mathématiques, plus précisément de combinatoire, décrivant les différentes façons de choisir un nombre donné d'objets dans un ensemble de taille donnée, lorsque les objets sont discernables et que l'on ne se soucie pas de l'ordre dans lequel les objets sont placés ou énumérés. Le nom complet, bien que peu usité est combinaison sans répétition de n éléments pris k à k. Autrement dit, les combinaisons de taille k d'un ensemble E de cardinal n sont les sous-ensembles de E qui ont pour taille k.
Combinatoire
En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait présente dans toute l'antiquité en Inde et en Chine. Donald Knuth, dans le volume 4A « Combinatorial Algorithms » de The Art of Computer Programming parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»).