Permutation circulaire

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En mathématiques, la 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.

[modifier] 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₁).

[modifier] Propriétés

[modifier] 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.

[modifier] 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.

[modifier] 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.