Permutation circulaire

En mathématiques, une permutation circulaire ou cycle est un cas particulier de permutation. Une permutation circulaire agit comme un décalage circulaire pour un certain nombre d'éléments, et laisse tous les autres inchangés.

Les permutations circulaires permettent d'illustrer le fonctionnement général des permutations, puisqu'une permutation quelconque se décompose en un produit de cycles fonctionnant de manière indépendante.

Définition

Soit $\sigma\in {\mathfrak S}_n$ une permutation. C'est un k-cycle ou permutation circulaire d'ordre k s'il existe des éléments a₁, ..., a_k distincts tels que σ envoie l'élément a₁ sur a₂, puis a₂ sur a₃ etc, et enfin a_k sur a₁ et si tous les autres éléments restent inchangés.

Un tel cycle se note habituellement sous la forme (a₁, ..., a_k). Avec cette notation (a₁, ..., a_k)=(a₂, ..., a_k, a₁).

Propriétés

Exponentiation

Si c est la permutation circulaire c = (a₁,a₂, …, a_n), ses puissances successives vérifient

$\forall k , 1\leq k \leq n-1, \; c^k\neq {\rm Id}\qquad c^n={\rm Id}\qquad c^{-1}=c^{n-1}$

Ce qui veut dire que c engendre un groupe cyclique d'ordre n.

En revanche, les puissances de c ne sont pas toutes à proprement parler des permutations circulaires (même si ce sont encore des décalages circulaires. Par exemple si c=(1,2,3,4) alors c²=(1,3)(2,4) est un produit de deux permutations circulaires, des transpositions. Plus précisément c^k est une permutation circulaire si et seulement si k et n sont premiers entre eux.

Parité

Une permutation circulaire est

paire si le nombre d'éléments est impair ;
impaire si le nombre d'éléments est pair.

Ceci peut se démontrer par récurrence sur le nombre d'éléments :

pour un doublet, la permutation circulaire est une transposition (a, b) → (b, a), c'est donc une permutation impaire ;
pour un n-uplet, la permutation circulaire s'obtient en permutant le premier et le dernier élément, puis en appliquant une permutation circulaire sur les éléments de rang 2 à n dans la nouvelle liste (donc les éléments a₂, a₃, …, a_n-2, a_n-1, a₁)
$(a_1,a_2,...,a_{n-1},a_n) \rightarrow (a_n,[a_2,...,a_{n-1},a_1])$
la permutation circulaire de n éléments est donc le produit d'un transposition avec la permutation circulaire d'ordre n-1, il y a donc un changement de parité entre n-1 et n.

Conjugaison

La conjuguée d'une permutation circulaire c = (a₁,a₂, …, a_n) par une permutation $σ$ est la permutation $\sigma\circ c \circ\sigma^{-1}$ . Il s'agit encore d'une permutation circulaire

$\sigma\circ c \circ\sigma^{-1}=(\sigma(a_1),\sigma(a_2), \dots, \sigma(a_n))$

Ce qui signifie que la classe de conjugaison (ensemble des conjuguées) d'une permutation circulaire est l'ensemble des permutations circulaires de même ordre.

Portail des mathématiques

Catégorie :

Permutation

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Permutation circulaire de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

permutation — [ pɛrmytasjɔ̃ ] n. f. • 1474; « échange, troc » 1261; permutacion « changement de résidence » v. 1180; lat. permutatio 1 ♦ Échange d un emploi, d un poste contre un autre. Permutation de deux officiers, de deux fonctionnaires (⇒ permutant) . Par… … Encyclopédie Universelle
circulaire — [ sirkylɛr ] adj. et n. f. • 1314; circulere XIIIe; lat. circularis I ♦ Adj. 1 ♦ Qui décrit un cercle. Mouvement circulaire. ⇒ giratoire, rotatoire. Elle « tournait sur elle même, dans un envol circulaire de la jupe » (Troyat). Regard circulaire … Encyclopédie Universelle
Permutation — En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets. La… … Wikipédia en Français
Permutation impaire — Signature d une permutation En mathématiques, les permutations peuvent se décomposer en un produit de transpositions, c est à dire en une succession d échanges d éléments deux à deux. Une permutation paire est une permutation qui peut être… … Wikipédia en Français
Permutation paire — Signature d une permutation En mathématiques, les permutations peuvent se décomposer en un produit de transpositions, c est à dire en une succession d échanges d éléments deux à deux. Une permutation paire est une permutation qui peut être… … Wikipédia en Français
Decalage circulaire — Décalage circulaire Un décalage circulaire est une opération sur une liste ordonnée (ou n uplet), consistant à faire passer le dernier élément au début et à décaler tous les autres ; ou à l inverse, faire passer le premier élément à la fin,… … Wikipédia en Français
Décalage Circulaire — Un décalage circulaire est une opération sur une liste ordonnée (ou n uplet), consistant à faire passer le dernier élément au début et à décaler tous les autres ; ou à l inverse, faire passer le premier élément à la fin, et décaler les… … Wikipédia en Français
Décalage circulaire — Un décalage circulaire est une opération sur une liste ordonnée (ou n uplet), consistant à faire passer le dernier élément au début et à décaler tous les autres ; ou à l inverse, faire passer le premier élément à la fin, et décaler les… … Wikipédia en Français
Groupe de permutation — Groupe symétrique Cette notion est différente de celle de groupe de symétrie. En mathématiques, plus particulièrement en algèbre, le groupe symétrique d un ensemble E est le groupe des permutations de E, c est à dire des bijections de E sur lui… … Wikipédia en Français
Parité d'une permutation — Signature d une permutation En mathématiques, les permutations peuvent se décomposer en un produit de transpositions, c est à dire en une succession d échanges d éléments deux à deux. Une permutation paire est une permutation qui peut être… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Permutation circulaire

Sommaire

Définition