PermutationEn mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation d'objets distincts rangés dans un certain ordre correspond à un changement de l'ordre de succession de ces objets. La permutation est une des notions fondamentales en combinatoire, c'est-à-dire pour des problèmes de dénombrement et de probabilités discrètes. Elle sert ainsi à définir et à étudier le carré magique, le carré latin, le sudoku, ou le Rubik's Cube.
Design combinatoireLa théorie du design combinatoire est une partie des mathématiques combinatoires ; elle traite de l'existence, de la construction et des propriétés de systèmes d'ensembles finis dont les arrangements satisfont certains concepts d'équilibre et/ou de symétrie. Ces concepts sont assez imprécis pour qu'une large gamme d'objets puisse être considérée comme relevant de ces notions. Parfois, cela peut concerner la taille des intersections comme dans les plans en blocs, d'autres fois on est intéressé par la disposition des entrées dans un tableau comme dans les grilles de sudoku.
Combinaison sans répétitionLes 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.
Falling and rising factorialsIn mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, rising sequential product, or upper factorial) is defined as The value of each is taken to be 1 (an empty product) when These symbols are collectively called factorial powers. The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation (x)_n , where n is a non-negative integer.
Carré latinvignette|Example of TAQ algorithm Un carré latin est un tableau carré de n lignes (donc de n colonnes) remplies de n éléments distincts dont chaque ligne et chaque colonne ne contient qu'un seul exemplaire. L'exemple historique du carré latin est le carré Sator ; la construction de telles curiosités combinatoires se transpose facilement à l'arithmétique en substituant un nombre à une lettre : la plupart du temps, les n éléments utilisés sont les entiers compris entre 0 et n-1.
CombinatoireEn 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»).
MultiensembleUn multiensemble (parfois appelé sac, de l'anglais bag utilisé comme synonyme de multiset) est une sorte d'ensemble dans lequel chaque élément peut apparaître plusieurs fois. C'est une généralisation de la notion d'ensemble : un ensemble ordinaire est un multiensemble dans lequel chaque élément apparaît au plus une seule fois ; ce qu'impose, pour les ensembles usuels, l'axiome d'extensionnalité. On nomme multiplicité d'un élément donné le nombre de fois où il apparaît.
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.
Plan en blocsEn mathématiques combinatoires, un plan en blocs est un ensemble, muni d'une famille de sous-ensembles (avec des répétitions possibles) dont les membres satisfont un ensemble de propriétés considérées dans une application particulière. Les applications proviennent de nombreux domaines, notamment les plans d'expériences, la géométrie finie, la chimie physique, les tests de logiciels, la cryptographie et la géométrie algébrique.
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.
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.
Triangle de Pascalthumb|Premières lignes du triangle de Pascal. En mathématiques, le triangle de Pascal est une présentation des coefficients binomiaux dans un tableau triangulaire. Il a été nommé ainsi en l'honneur du mathématicien français Blaise Pascal. Il est connu sous l'appellation « triangle de Pascal » en Occident, bien qu'il ait été étudié par d'autres mathématiciens, parfois plusieurs siècles avant lui, en Inde, en Perse (où il est appelé « triangle de Khayyam »), au Maghreb, en Chine (où il est appelé « triangle de Yang Hui »), en Allemagne et en Italie (où il est appelé « triangle de Tartaglia »).
Combinatorial principlesIn 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.
Partition d'un entierEn mathématiques, une partition d'un entier (parfois aussi appelée partage d'un entier) est une décomposition de cet entier en une somme d'entiers strictement positifs (appelés parties ou sommants), à l'ordre près des termes (à la différence du problème de composition tenant compte de l'ordre des termes). Une telle partition est en général représentée par la suite des termes de la somme, rangés par ordre décroissant. Elle est visualisée à l'aide de son diagramme de Ferrers, qui met en évidence la notion de partition duale ou conjuguée.
Family of setsIn set theory and related branches of mathematics, a collection of subsets of a given set is called a family of subsets of , or a family of sets over More generally, a collection of any sets whatsoever is called a family of sets, set family, or a set system. A family of sets may be defined as a function from a set , known as the index set, to , in which case the sets of the family are indexed by members of .
Nombre de CatalanEn 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).
Mathématiques appliquéesvignette|280px|En théorie des graphes, principales topologies typiques de graphes. Les mathématiques appliquées sont une branche des mathématiques qui s'intéresse à l'application du savoir mathématique aux autres domaines.
Permutation aléatoireUne permutation aléatoire de taille N, est une permutation prise de manière uniforme dans l'ensemble des permutations de taille N. De nombreux paramètres ont été étudiés sur les permutations aléatoires, par exemple, le nombre moyen de points fixes ou la longueur des cycles. Plusieurs algorithmes existent pour générer des permutations aléatoires à partir d'un générateur de nombres aléatoires, par exemple le mélange de Fisher-Yates. Soit une suite de variables aléatoires i.i.d.
Théorie de RamseyEn mathématiques, et plus particulièrement en combinatoire, la théorie de Ramsey, nommée d'après Frank Ramsey, tente typiquement de répondre à des questions de la forme : « combien d'éléments d'une certaine structure doivent être considérés pour qu'une propriété particulière se vérifie ? » Le premier exemple de résultat de cette forme est le principe des tiroirs, énoncé par Dirichlet en 1834. Supposons, par exemple, que n chaussettes soient rangées dans m tiroirs.
Problème des rencontresEn mathématiques, le problème des rencontres, ou problème de Montmort, ou encore problème des chapeaux, consiste à déterminer la probabilité que, n jetons numérotés de 1 à n ayant été mis au hasard dans des cases elles-mêmes numérotées de 1 à n, aucun jeton ne soit à sa place (ou celle de l'évènement contraire). De façon plus savante, c'est la recherche de la probabilité qu'une permutation prise au hasard soit un dérangement, c'est-à-dire ne possède pas de « rencontre », autrement dit de point fixe.
