Concept
Permutation
Concepts associés (54)
Twelvefold way
In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer. Let N and X be finite sets. Let and be the cardinality of the sets. Thus N is an n-set, and X is an x-set.
Dérangement partiel
En combinatoire, le nombre de rencontres d'une permutation d'un ensemble fini de n objets est le nombre de points fixes de cette permutation. Ce nombre intervient dans le problème des rencontres. On notera le nombre de permutations de présentant exactement rencontres ; ces permutations, qui ont donc un support de cardinal , sont appelées des dérangements partiels d'ordre . La permutation présente 2 rencontres ; c'est un dérangement partiel d'ordre 4.
Formule du multinôme de Newton
En mathématiques, la formule du multinôme de Newton est une relation donnant le développement d'une puissance entière n d'une somme d'un nombre fini m de termes sous forme d'une somme de produits de puissances de ces termes affectés de coefficients, lesquels sont appelés des coefficients multinomiaux. La formule du binôme s'obtient comme cas particulier de la formule du multinôme, pour m=2 ; et dans ce cas les coefficients multinomiaux sont les coefficients binomiaux.
Groupe du Rubik's Cube
Cet article présente un modèle mathématique et une présentation du groupe du Rubik's Cube. est le groupe des mouvements légaux ou le groupe des états (sans démonter le cube !). est le groupe élargi ou le groupe des états étendus (ici on peut démonter le cube, mais les mouvements des sommets et des arêtes doivent rester chaqu'un dans leur camp). est l'ensemble des classes d'équivalence pour la congruence modulo n. Il est isomorphe au groupe des n-èmes de tour d'axe donné.
Matrice de permutation
Une matrice de permutation est une matrice carrée qui vérifie les propriétés suivantes : les coefficients sont 0 ou 1 ; il y a un et un seul 1 par ligne ; il y a un et un seul 1 par colonne. Ainsi : est une matrice de permutation. Les matrices de permutations carrées de taille n sont en bijection avec les permutations de l'ensemble {1,2,...n}. Si σ est une telle permutation, la matrice correspondante est de terme général Cette bijection est un morphisme de groupes : En utilisant cette identité avec deux permutations inverses l'une de l'autre, on obtient le fait qu'une matrice de permutation est inversible, et que son inverse est la matrice de la permutation inverse.
Ensembles disjoints
vignette|Trois ensembles disjoints En mathématiques, deux ensembles sont dits disjoints s'ils n'ont pas d'éléments en commun. Par exemple, et sont deux ensembles disjoints. De manière formelle, deux ensembles A et B sont disjoints si leur intersection est l'ensemble vide, c'est-à-dire si (Dans le cas contraire, on dit que A et B « se rencontrent ».) Cette définition s'étend à une famille d'ensembles. Les ensembles d'une famille sont dits disjoints deux à deux ou mutuellement disjoints si deux ensembles quelconques de cette famille sont disjoints.
Polynôme symétrique
En mathématiques, un polynôme symétrique est un polynôme en plusieurs indéterminées, invariant par permutation de ses indéterminées. Ils jouent notamment un rôle dans les relations entre coefficients et racines. Soit A un anneau commutatif unitaire. Un polynôme Q(T, ..., T) en n indéterminées à coefficients dans A est dit symétrique si pour toute permutation s de l'ensemble d'indices {1, ..., n}, l'égalité suivante est vérifiée : Exemples Pour n = 1, tout polynôme est symétrique.
Symmetric inverse semigroup
NOTOC In abstract algebra, the set of all partial bijections on a set X ( one-to-one partial transformations) forms an inverse semigroup, called the symmetric inverse semigroup (actually a monoid) on X. The conventional notation for the symmetric inverse semigroup on a set X is or . In general is not commutative. Details about the origin of the symmetric inverse semigroup are available in the discussion on the origins of the inverse semigroup. When X is a finite set {1, ...
Carré latin
vignette|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.
Principe d'inclusion-exclusion
thumb|Exemple d'inclusion-exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion-exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d'une réunion finie d'ensembles finis en fonction du nombre d'éléments de ces ensembles et de leurs intersections. Il se généralise en termes de probabilités. Il est attribué au mathématicien Abraham de Moivre, et connu également (lui ou sa version probabiliste) sous le nom de formule du crible de Poincaré, formule de Poincaré, ou formule du crible.