Permutation

Dans plusieurs domaines de mathématiques la permutation terme est utilisé avec des significations différentes, mais étroitement liés. Ils se rapportent tous à la notion de (ré) organisation éléments d'une donnée ensemble fini dans une séquence .

Définitions

Le concept général de permutation peut être défini de façon plus formelle dans des contextes différents:

Dans combinatoire

En combinatoire , une permutation est généralement comprise comme une séquence contenant chaque élément d'un ensemble fini une fois, et une seule fois. Le concept de la séquence est différente de celle d'un ensemble, en ce que les éléments d'une séquence apparaissent dans un certain ordre: la séquence présente un premier élément (sauf se il est vide), un deuxième élément (à moins que sa longueur est inférieure à 2), et ainsi de suite. En revanche, les éléments d'un ensemble ont pas d'ordre; {1, 2, 3} et {3, 2, 1} sont différentes façons pour désigner le même ensemble.

Toutefois, il existe également une signification plus générale classique du terme "permutation" utilisée dans la combinatoire. En ce sens plus général, ces permutations sont des séquences dans lesquelles, comme précédemment, chacun des éléments se produit au plus une fois, mais pas tous les éléments de l'ensemble suivant doivent être utilisés.

Pour une notion associée dans laquelle l'ordre des éléments sélectionnés forment un ensemble, dont l'ordre ne est pas pertinent, voir Combinaison.

Dans la théorie des groupes

Dans la théorie des groupes et des domaines connexes, les éléments d'une permutation n'a pas besoin d'être disposés dans un ordre linéaire, ou même dans ne importe quel ordre à tous. Selon cette définition raffinée, une permutation est un une bijection de ensemble fini sur lui-même. Cela permet la définition des groupes de permutations; voir groupe de permutation.

Compter permutations

Dans ce seul article, la définition traditionnelle de la combinatoire est utilisé: une permutation est une séquence ordonnée d'éléments choisis parmi un ensemble fini donné, sans répétitions, et pas nécessairement en utilisant tous les éléments d'un ensemble donné. Par exemple, compte tenu de l'ensemble des lettres {C, E, G, I, N, R}, quelques permutations sont RING, RIZ, NICER, règne et grincer des dents, mais aussi RNCGI -. La séquence n'a pas besoin d'épeler un mot existant MOTEUR , d'autre part, ne est pas une permutation, car il utilise des éléments E et N deux fois.

Si n désigne la taille de l'ensemble - le nombre d'éléments disponibles pour la sélection - et seuls sont considérés les permutations qui utilisent tous les éléments N, alors le nombre total de permutations possibles est égal à n, où "!" est la factorielle opérateur. Cela peut être démontré de manière informelle comme suit. Dans la construction d'une permutation, il existe n choix possibles pour le premier élément de la séquence. Une fois qu'il a été choisi,

les éléments sont à gauche, si pour le deuxième élément il n'y a que

choix possibles. Pour les deux premiers éléments, qui nous donne

n × (n - 1) permutations possibles.

Pour sélectionner le troisième élément, il existe alors

éléments gauche, donnant, pour les trois premiers éléments,

n × (n - 1) × (n - 2) permutations possibles.

Continuer ainsi jusqu'à ce que il n'y a que deux éléments de gauche, il ya deux choix, donnant le nombre de permutations possibles, comprenant des

éléments:

n × (n - 1) × (n - 2) × ... × 2.

Le dernier choix est maintenant forcé, comme il ya exactement un élément gauche. Dans une formule, ce est le nombre

n × (n - 1) × (n - 2) × ... × 2 × 1

(Qui est le même que précédemment parce que le facteur 1 ne fait pas de différence). Ce numéro est, par définition, le même que n!.

En général, le nombre de permutations est désignée par P (n, r), _n P _r, ou parfois Où:

• n est le nombre d'éléments pouvant être sélectionnés, et
• r est le nombre d'éléments à sélectionner (0 ≤ r ≤ n).

Pour le cas où

il vient d'être montré que

. Le cas général est donné par la formule:

Comme précédemment, ceci peut être localisée de manière informelle en considérant la construction d'une permutation arbitraire, mais ce temps d'arrêt lorsque la longueur r est atteinte. La construction se déroule d'abord comme ci-dessus, mais se arrête à longueur r. Le nombre de permutations possibles qui a été atteint, est:

P (n, r) = n × (n - 1) × (n - 2) × ... × (n - r + 1).

Donc:

n! = N × (n - 1) × (n - 2) × ... × 2 × 1

= N × (n - 1) × (n - 2) × ... × (n - r + 1) × (n - r) × ... × 2 × 1

= P (n, r) × (n - r) × ... × 2 × 1

= P (n, r) × (n - r) !.

Mais si n! = P (n, r) × (n - r) !, puis

. Par exemple, se il existe un total de 10 éléments et sont sélection d'une séquence de trois éléments de cet ensemble, la première est une sélection à partir de 10 éléments, le côté de l'une restante 9, et enfin de la 8 restant, ce qui donne

. Dans ce cas, n = 10 et r = 3. En utilisant la formule pour calculer P (10,3),

Dans le cas particulier où n = r la formule ci-dessus se simplifie en:

La raison pour laquelle 0! 1 = 0, ce est que! est un vide produit, qui est toujours égal à 1.

Dans l'exemple donné dans l'en-tête de cet article, avec 6 entiers {1..6}, ce serait: P (6,6) = 6! / (6-6)! = (1 × 2 × 3 × 4 × 5 × 6) / 0! = 720/1 = 720.

Les autres notations, âgés comprennent ^{le n} P _r, P _{n, r, n} ou P _r. Une notation moderne commun est (n) _r qui est appelé un tomber factorielle. Cependant, la même notation est utilisée pour la la hausse factorielle (également appelé Symbole Pochhammer)

n (n + 1) (n + 2) ⋯ (n + r - 1) r.

Avec la notation factorielle en hausse, le nombre de permutations est (n - r + 1) _r.

Permutations dans la théorie des groupes

Comme expliqué dans une section précédente, en théorie des groupes la permutation terme (d'un ensemble) est réservée à un bijection ( bijection) à partir d'un ensemble fini sur lui-même. L'exemple précédent, de faire des permutations de numéros de 1 à 10, serait traduit par une carte de l'ensemble {1, ..., 10} pour lui-même.

Notation

Il ya deux principales notations pour ces permutations. Dans la notation de relation, on peut juste arranger l'ordre "naturel" des éléments étant permuté sur une ligne, et la nouvelle commande sur une autre ligne:

signifie la permutation s de l'ensemble {1,2,3,4,5} définie par s (1) = 2, S (2) = 5, S (3) = 4, s (4) = 3, s (5) = 1.

Si nous avons un ensemble fini E de n éléments, il est par définition bijection avec l'ensemble {1, ..., n}, où cette bijection f correspond juste pour numéroter les éléments. Une fois qu'ils sont numérotés, nous pouvons identifier les permutations de l'ensemble E avec permutations de l'ensemble {1, ..., n}. (En termes plus mathématiques, la fonction qui associe une permutation de E s à la permutation de fosof ^-1 {1, ..., n} est un morphisme de la groupe symétrique de E dans celui de {1, ..., n}, voir ci-dessous.)

Sinon, nous pouvons écrire la permutation en termes de la façon dont les éléments changent lorsque la permutation est successivement appliquée. Ceci est désigné comme la décomposition de la permutation dans un produit de disjointe cycles. Il fonctionne comme suit: partant d'un élément x, nous écrivons la séquence (x s (x) s ² (x) ...) jusqu'à ce que nous serons de retour l'élément de départ (à quel point nous fermons la parenthèse sans écrire pour une deuxième fois ). Ceci est appelé le cycle associé à x 's orbite suivante s. Puis nous prenons un élément, nous ne avons pas écrit encore et faisons la même chose, jusqu'à ce que nous avons considéré tous les éléments. Dans l'exemple ci-dessus, on obtient: s = (2 1 5) (3 4).

Chaque cycle (x ₁ x ₂ ... x _L) signifie que la permutation cartes x _i x _i sur _une (i = 1 ... L -1) et x _L x sur _1, et tous les autres éléments laisse invariante. L est appelée la durée du cycle. Étant donné que ces cycles ont par construction disjoints des supports (ce est à dire qu'ils agissent non triviale sur des sous-ensembles disjoints de E), ils ne commutent (par exemple, (1 2 5) (3 4) = (3 4) (2 1 5)). L'ordre des cycles dans le (composition) produit n'a pas d'importance, alors que l'ordre des éléments dans chaque cycles ne importe ( jusqu'à changement cyclique; voir aussi cycles et points fixes).

De toute évidence, un 1 cycle (cycle de longueur 1) est le même que la fixation de l'élément qu'il contient, donc il est inutile de l'écrire explicitement. La définition de certains auteurs d'un cycle ne incluent pas les cycles de longueur 1.

Cycles de longueur deux sont appelés transpositions; ces permutations simplement échanger la place de deux éléments. (A l'inverse, un transposition matricielle est lui-même un exemple important d'une permutation.)

Produit et inverse de permutations

On peut définir le produit de deux permutations comme suit. Si nous avons deux permutations, P et Q, l'action de la première exécution de P et Q sera le même que l'exécution certaine permutation unique R. Le produit de P et Q est alors défini comme étant que R permutation. Regarde permutations que bijections, le produit de deux permutations est donc le même que leur composition que des fonctions. Il n'y a aucune notation universellement acceptée pour le fonctionnement du produit entre les permutations, et selon l'auteur une formule comme PQ peut signifier soit P ∘ ∘ Q ou Q P. Depuis la composition de fonctions est associative , est donc le fonctionnement du produit sur des permutations: (P ∘ Q) ∘ ∘ R = P (Q ∘ R).

De même, étant donné que bijections ont inverses , alors ne permutations, et les deux P ∘ P et P ^{-1 -1} ∘ P sont la "permutation identité" (voir ci-dessous) qui laisse toutes les positions inchangées. Ainsi, on peut voir que les permutations forment un groupe .

Comme pour ne importe quel groupe, il existe un groupe isomorphisme de groupes de permutation, obtenus en attribuant à chaque permutation inverse son, et ce est un isomorphisme involution, donnant une double vision sur un résultat abstrait. Depuis (P ∘ Q) ^-1 = Q ^-1 ∘ P ^-1, d'un point de vue abstrait il est indifférent que PQ représente "P avant Q" ou "P après Q". Pour permutations concrètes, la distinction est, bien sûr, tout à fait matériel.

Permutations spéciales

Si nous pensons à une permutation que «changements» la position du premier élément au premier élément, la seconde à la seconde, et ainsi de suite, nous avons vraiment ne ont pas changé les positions des éléments du tout. En raison de son action, nous décrivons ce que la permutation identité, car elle agit comme un fonction identité. Inversement, une permutation qui change la position de tous les éléments (pas d'élément est mappé sur lui-même) est appelé un dérangement.

Si l'on a une certaine permutation, appelé P, on peut décrire une permutation, P ^-1 écrite, qui défait l'action de l'application P. En substance, l'exécution P alors P ^-1 équivaut à effectuer la permutation identité. On a toujours une telle permutation depuis une permutation est une bijection. Une telle permutation est appelé le permutation inverse. Il est calculé en échangeant chaque numéro et le numéro de la place qu'il occupe.

Une même permutation est une permutation qui peut être exprimé comme le produit d'un nombre pair de transpositions, et la permutation est une permutation identité même si elle est égale à (1 2) (1 2). Une permutation impaire est une permutation qui peut être exprimé comme le produit d'un nombre impair de transpositions. Il peut être démontré que chaque permutation est soit pair ou impair et ne peut pas être à la fois.

Un théorème concernant la permutation inverse est l'effet d'une conjugaison d'une permutation par une permutation dans un groupe de permutation. Si nous avons une permutation Q = ₍₁ i i i ... _{2 n)} et une permutation P, alors RPQ ^-1 = (P (i ₁₎ P (i ₂₎ ... P (i _n)).

Nous pouvons également représenter une permutation de matrice forme; la matrice résultante est appelée matrice de permutation.

Permutations en informatique

Certains des anciens manuels Regardons permutations, les affectations, comme mentionné ci-dessus. En sciences informatiques termes, ce sont opérations d'affectation, avec des valeurs

1, 2, ..., n

affecté aux variables

x _1, x _2, ..., x _n.

Chaque valeur doit être attribuée qu'une seule fois.

La différence cession / substitution est alors illustre une manière dont programmation fonctionnelle et la programmation impérative différer - programmation fonctionnelle pure a pas de mécanisme d'affectation. La convention de mathématiques est aujourd'hui que permutations sont juste des fonctions et l'opération sur eux est la composition de fonctions ; programmeurs fonctionnels suivent cette. Dans la langue d'affectation une substitution est une instruction pour basculer autour des valeurs attribuées, simultanément; un problème bien connu.

Numérotation permutations

Factoradic numéros peuvent être utilisés pour attribuer des numéros uniques aux permutations, telle que donnée une factoradic de k, on peut trouver rapidement la permutation correspondante.

Les algorithmes pour générer des permutations

Génération non ordonnée

! Pour tout nombre k, avec 0 ≤ k <n, l'algorithme suivant génère une permutation unique de _{la j} de la séquence initiale, j = 1 ... n:

  la fonction de permutation (k, s) {
      var int factorielle: = 1;
      pour j = 2 à la longueur (s) {
         factorial: = * factorielle (j-1);  // Factorielle = (j-1)!
         [la j- ((k / factoriel) mod j)] de swap avec s [j];
      }
      retourner s;
  }

La génération de l'ordre lexicographique

! Pour tout nombre k, avec 0 ≤ k <n, l'algorithme suivant génère la permutation correspondant lexicographique de _{la j} de la séquence initiale, j = 1 ... n:

  la fonction de permutation (k, s) {
      int var n: = longueur (s);  factorielle: = 1;
      pour j = 2 à n-1 {// calculer (n-1)!
          factorielle: = factorielle * j;
      }
      pour j = 1 à N-1 {
          tempj: = (k / factorielle) mod (n + 1- j);
          Temps: = s [j] + tempj
          pour i = j + tempj à j + 1 étape -1 {
              S [i]: = s [i-1];  // Changer le droit de la chaîne
          }
          s [j]: = temps;
          factorial: = factorielle / (n- j);
      }
      retourner s;
  }

Notation

• k / j représente la division entière de k par j, ce est à dire l'intégrale quotient sans reste, et
• k mod j est le reste suit division entière de k par j.
• s [n] désigne le n ième élément de la séquence s.

Implémentations logicielles et matérielles

Fonctions de calcul

La plupart des calculatrices ont une fonction intégrée pour calculer le nombre de permutations, appelé nPr ou PERM sur un grand nombre. La fonction de permutations ne est souvent disponible à travers plusieurs couches de menus; comment accéder à la fonction est généralement indiqué dans la documentation de calculatrices qui le soutiennent.

Les fonctions de tableur

Plus tableur fournit également une fonction intégrée pour calculer le nombre de permutations, appelé PERMUT dans de nombreux tableurs populaires. Apple logiciels Numéros notamment ne comprend pas actuellement une telle fonction.