NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 16/11/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths    

            

RUBRIQUE   Nombres

 

Débutants

Général

Formes permutées

 

Glossaire

Général

 

INDEX

 

Permutations

 

Motifs

 

Général

Divisibilité

12345 et permutations

Permutations de n

Algorithmes simples de permutation

Algorithmes rapides

Cycles dans les permutations

Calcul quantité de cycles

 

Sommaire de cette page

>>> Permutations et cycles – Notion

>>> Notions avancées

>>> Groupe de permutation (1, 2, 3, 4)

>>> Programmation

>>> Groupe de permutation (1, 2, 3, 4, 5)

 

 

 

 

PERMUTATIONS et CYCLES

 

On peut trouver de nombreuses permutations parmi un ensemble d'éléments. Certaines d'entre-elles font "tourner en rond" et elles constituent des cycles. Une permutation est particulièrement intéressante si les cycles sont indépendants, disjoints. Comment calculer la quantité de cycles dans une permutation? Avec les nombres de Stirling.

 

Exemple

 

 

Permutations et cycles – Notion

 

Approche

Le tableau définit une permutation avec en haut le départ et en bas le résultat: le 1 devient 2, le 2 devient4, etc.

L'exemple montre clairement que le 3 ne change pas de position, alors que le 1 suit un cycle: 1 => 2 => 4 => 1  et ça recommence.

 

On note la permutation: P = (1, 2, 4) (3).

Elle est constituée de deux sous-ensembles disjoints.

On dit que l'orbite de 1 est (1, 2, 3).

 

Exemple de permutation des nombres 1 à 4

 

Toute permutation peut être décomposée en un produit unique de cycles disjoints.

 

 

Permutation circulaire

C'est le cas où le cycle est complet pour chacun des éléments: P = (1, 2, 3, 4).

 

Note: généralement la permutation circulaire est celle qui enregistre un simple décalage des éléments (come dans un registre à décalage). Ici, on entend toutes les permutations où chaque élément fait le tour de tour les éléments avant de reprendre sa place (un seul cycle).

Groupe de permutations

E, un ensemble fini non vide comme E = (1, 2, 3, 4).

Groupe des bijections de E sur E (exemples du tableau).

La permutation en bas du tableau est la permutation identité (application identique).

 

 

Notions avancées

Cette notation indique que le 1 est transposé en 3 et réciproquement; et que le 4 devient 6, le 6 devient 7 et le 7 devient 1.

P = (1, 3) (4, 6, 7)

La réunion de tous les éléments permutés est appelé le support de permutation.

Le plus grand élément permuté est le degré de la permutation.

Les éléments non touchés par une permutation sont les éléments fixes.

S = (1, 3, 4, 6 ,7)

 

d = 7

 

F = (2, 5)

 

 

Groupe de permutations avec E = (1, 2, 3, 4)

Soit les 24 (= 4!) permutations possibles des quatre éléments (1, 2, 3, 4).

Les cycles se déduisent de la configuration d'arrivée (Pk) par à rapport à celle de départ (E).

Exemple

P1: 1, 2, 3, 4

P2: 1, 2, 4, 3

1 et 2 sont fixes et, 3 et 4 se transposent.

Bilan: (1) (2) (3, 4).

Quantité k = 3.

Sur chaque ligne, on indique les cycles produits et leur quantité k:

*        k = 1: 6 permutations circulaires à un seul cycle;

*        k = 2: 11 permutations avec transpositions à deux cycles; et

*        k = 3: 6 permutations à trois cycles.

*        k = 4: 1 permutation à quatre cycles (identité);

Peut-on déterminer (formuler) cette répartition selon la valeur de k ?

R4 = [6, 11, 6, 1]

La colonne de droite montre ce que calcule le logiciel Maple.

 

 

Programme Maple

 

Réinitialisation du logiciel.

Apple aux logiciels de traitements combinatoires.

Entrée de la liste L à permuter.

Toutes les permutations sont logées dans LL et avec q la quantité de permutations.

 

Lancement d'une boucle d'exploration des permutations de k = 1 à q.

Conversion de la liste numéro k (une des permutations) en ses cycles.

 

Impression du rang k, de la kième permutation LL et des cycles détectés en c (l'instruction op élimine une paire de crochets)

 

Résultats de traitement en bleu

Le logiciel ne donne que les cycles en ignorant les éléments fixes. Le cycle n'est pas ordonné.

 

 

Notez: appel à une conversion particulière calculant directement les cycles: 'disjcyc' mis entre apostrophes classiques (code 0027).

Voir ProgrammationIndex

 

 

Permutations de cinq éléments et leurs cycles

 

Rang, [Permutation], [cycle], quantité cycles + éléments fixes

 

Représentation circulaire des 24 cycles k = 1 (permutations circulaires)

 

 

Merci à Alain Rodot pour sa majeure contribution à la création de cette page,

 

 

 

Retour

*       Formes permutées

Suite

*       Calcul de la quantité de cycles de permutation – Démonstration 

Autres

*       Permutations en combinatoire

*       Parties d'une ensemble – Dénombrement

*       PermutationsIndex

Voir

*       Chiffres en miroir

*       Factorielle

*       Motifs

*       Multiplication ABCDE = F x GGGGGG

*       Nombre 1089 et magie

*       Nombres de Friedman

*       Nombres en 4 fois 4

*       Procédé de Kaprekar

*       PuzzlesIndex

*       Somme et produit des chiffres

Sites

*       Permutations et cycles – M. Deléglise

*       OEIS A132393 – Triangle of unsigned Stirling numbers of the first kind

*       Stirling numbers of the first kind – Robert's Math Figures

*       Stirling number – Combinatorial proof – Wikipedia

*       Partitions and permutations – Columbia.edu – Allez à page 25

*       Partitions and Permutations – Gordon Royle

Cette page

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