Permutation circulaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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 a1, ..., ak distincts tels que σ envoie l'élément a1 sur a2, puis a2 sur a3 etc, et enfin ak sur a1 et si tous les autres éléments restent inchangés.

Un tel cycle se note habituellement sous la forme (a1, ..., ak). Avec cette notation (a1, ..., ak)=(a2, ..., ak, a1).

Propriétés[modifier | modifier le code]

Exponentiation[modifier | modifier le code]

Si c est la permutation circulaire c = (a1,a2, …, an), 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 c2=(1,3)(2,4) est un produit de deux permutations circulaires, des transpositions. Plus précisément ck est une permutation circulaire si et seulement si k et n sont premiers entre eux.

Parité[modifier | modifier le code]

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 a2, a3, …, an-2, an-1, a1)
    (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[modifier | modifier le code]

La conjuguée d'une permutation circulaire d'ordre k, c = (a1,a2, …, ak) par une permutation σ, est la permutation σ ∘ c ∘ σ−1. Il s'agit encore d'une permutation circulaire d'ordre k :

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

et réciproquement, toute permutation circulaire d'ordre k peut s'écrire sous cette forme en choisissant convenablement σ, ce qui signifie que la classe de conjugaison (ensemble des conjuguées) d'une permutation circulaire c d'ordre k est l'ensemble de toutes les permutations circulaires d'ordre k.

Elles sont au nombre de

{n\choose k}\frac{k!}k=\frac{n!}{(n-k)!k}.

D'après la formule des classes, le centralisateur de c est donc d'ordre (n – k)!k. Il est par conséquent réduit à l'ensemble des produits, par l'une des k puissances de c, de l'une des (n – k)! permutations de support disjoint de celui de c.