Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 19/11/2023

M'écrire

Brèves de Maths

 

INDEX

 

Permutations

Combinatoire

Motifs

Types de nombres

PERMUTATIONS

Permutations

Permutation des nombres

Permutation spirale

Combinatoire

Dérangements

Nombres d'Euler

Lexicographique

Cycles des permutations

Ondulants d'Euler

Premiers permutables

Mathématique des tissus

Faites un double-clic pour un retour en haut de page

 

 

 

PERMUTATIONS

 

Page introductive sur les permutations. Exemples et définition. Présentation de divers types de permutations.

   

 

Sommaire de cette page

>>> Permutations linéaires

>>> Permutations figurées

>>> Permutations circulaires

>>> Permutations sous-contrainte

>>> Permutations singulières

>>> Programmation

  

Débutants

Combinatoire

 

Glossaire

Combinatoire

 

 

Permuter, permutation – Linguistique

*      Prendre la place d'un élément qui vient, en retour, occuper la sienne.

*      Du latin permutare changer, formé de per par et muto, mouvoir

*      Syn. échanger, intervertir, inverser, transposer

*      Math: bijection d'un ensemble vers lui-même. Les différentes manières de disposer des objets à la suite les uns des autres.

*      Anglais: a permutation;  to permute, to swap, to switch, to interchange

 

 

Permutations linéaires

haut

 

Permutations (sans répétition)

Toutes les manières de positionner n objets les uns à côté des autres sur une ligne.

 

Quantité de permutations

Ayant choisi le premier objets, il en reste n – 1 ; ayant choisi le suivant il en reste n – 2; etc.

Soit un total:

P(n) = n (n – 1) (n – 2) … 3 · 2 · 1 = n!

 

 

 

Les six possibilités de disposer les nombres: 1, 2 et 3

 

123, 132, 213, 231, 312, 321

 

 

Permutations avec répétition

Les objets considérés peuvent être ne double, triple …

Les objets répétés sont identiques et donc non identifiables.

 

 

Permutation avec 1, 2, 2, 3

Quantité: 4! / 2! = 24 / 2 = 12

 

1223, 1232, 1322,

2123, 2132, 2213, 2231, 2312, 2321,

3122, 3212, 3221

 

Permutations de Lucas ou figurées ou en grille

haut

 

Représentation en grille: permutations de Lucas  ou permutations figurées

Elles ont été introduites en 1883 par le mathématicien Édouard Lucas.

Avec trois objets, on peut adopter cette représentation sur une grille 3 x 3 d'une permutation linéaire de trois éléments:

 

 

On liste les objets par colonne croissante en indiquant la ligne sur laquelle il se trouve.
Dit-autrement: le numéro de la colonne est implicite et celui de ligne explicite.

Ce principe de représentation des permutations linéaires impose qu'il n'existe qu'un seul objet par ligne et par colonne. Et, bien sûr, cette construction conduit à énoncer tous les cas possibles.

 

Avec quatre objets: 4! = 24 possibilités

 

Carré latin

Cette représentation est utilisée pour former les carrés latins: ce sont des sortes de carrés magiques simplifiés pour lesquels, sur une grille n x n, on dispose n fois n objets à raison d'un objet unique par ligne et par colonne.

 

Exemple de carré latin 3x3

 

Avec les nombres de 1 à n dans le carré latin, la somme sur les lignes et sur les colonnes est constante et vaut la somme des nombres de 1 à n soit n (n + 1) / 2.

 

Voir Brève 47-938

 

 

Applications des permutations en grille

haut

 

La représentation figurée en grille des permutations linéaires est implicitement utilisée dans de nombreuses applications utilisant des grilles

 

 

Permutations figurées

*    Carrés latins

*    Échiquiers (indépendance des tours)

*    Disposition trame-chaine des tissus

*    Tables additions et multiplications

*    Tours de magie, grille magique

 

 Par extension

*    Sudoku, Hidaku, …

*    Carrés magiques (diaboliques)

 

 

 

 

Permutations circulaires

haut

 

Permutation circulaire simple

Les éléments d'une liste sont tous décalés d'un cran et le premier repasse en dernier  ou inversement selon le sens du décalage.

 

 

A, B, C, D, E

B, C, D, E, A

 

 

Transposition

Permutation simple qui correspond à une simple inversion de deux éléments.

 

A, B, C, D, E

A, B, D, C, E

 

Voir Nombres permutations

 

 

 

Permutations sous-contrainte

haut

 

Permutations sous-contraintes

Permutations linéaires soumise à des conditions souvent sur les nombres qui la composent.

 

1234 est croissante

3421 est décroissante

 

Permutations d'Euler

Permutations portant sur des nombres. On ne retient que celles pour lesquelles les nombres vont en croissant (ou en décroissant).

Voire même sur une quantité définie de ces croissances.

Voir SUITE

 

1 3 2 4

Cette suite présente deux croissances (1, 3) et (2, 4).

 

Permutations ondulantes d'Euler

Permutations dont les nombres croissent puis décroissent.

Voir SUITE

 

1 3 2 4

est de ce type avec les croissances (1, 3) et (2, 4) et la décroissance (3, 2).

 

 

Permutations symétriques

Permutations de nombres tels que la somme des nombres à égale distance des extrêmes est la même.

Les permutations figurées correspondantes sont alors symétriques par rapport au centre de la grille.

 

1 3 2 4

répond à cette exigence: 1 + 4 = 3 + 2 

 

Les huit permutations symétriques sur grille 4x4

  

 

 

Permutations singulières

haut

 

Permutations spirales ou sextines

Permutation où les objets situés dans la seconde moitié s'intercalent entre ceux de la première moitié en ordre décroissant.

Voir SUITE

 

123456 devient 61 52 43

 

 

Programmation

haut

 

Instruction existante

 

Commentaires

Le logiciel mathématique Maple, et la majorité de ces logiciels, disposent d'une instruction particulière accédant directement aux permutations.

 

En bas, appel direct avec le logiciel combinat et exemple d'une liste explicite.

 

Principe de programmation par récursion (backtracking)

 

Voir Algorithmes de recherche des permutations

 

 

Programme Python

 

Source Rosetta code – Autres langages disponibles

 

 Commentaires

On définit une fonction permutation.

L'instruction list(range(3)) retourne la liste [0, 1, 2], par exemple.

Dans le reste du programme, l'instruction la plus importante et la plus déroutante est yield (produire). En gros, elle permet de retenir le résultat du dernier calcul qui reste disponible pour la prochaine itération (le prochain " tour de piste"). Elle évite de conserver tous les résultats antérieurs qui encombreraient la mémoire inutilement.

 

Voir ProgrammationIndex  /  Suites sur programmation des permutations avec récursivité

 

 

 

Haut de page (ou double-clic)

 

Retour

*      Permutations & combinatoire

Suite

*      Permutation des nombres

*      Mathématique des tissus

*      PermutationIndex 

Voir

*      Contrepèteries

*      Anagrammes

Livre

*      Récréations mathématiques par Édouard Lucas (1891) – Les permutations rectilignes – Page 195 et suite – Livre accessible sur Internet en https://gallica.bnf.fr

*      A la recherche des permutations figurées – René Descombes, Michel Criton – Auto-édition – 2021

Sites

*      Write a program to print all Permutations of given String – GeeksforGeeks – Bhavya Jain

Cette page

http://villemin.gerard.free.fr/aNombre/MOTIF/PermGene.htm