Permutations et dérangements de [n] = {1,2, ... n}
Permutations alternantes ou down-up
Permutations up-down
Définitions
Pour n>0, on notera [n]={1, 2, 3, ..., n} l'ensemble des n premiers naturels non nuls et pour n=0, cet ensemble sera l'ensemble vide ø.
Une permutation s de [n]={1, 2, 3, ..., n} est une
bijection de [n] dans lui-même.
Il existe une unique bijection de l'ensemble vide ø vers lui-même.
Un dérangement s de [n]={1, 2, 3, ..., n} est une permutation de [n] pour laquelle tout élément i est différent de son image s[i].
Une permutation involutive ou involution s est sa propre inverse (réciproque) : s = s -1.
Une permutation s de [n]={1, 2, 3, ..., n} est dite alternante (ou down-up) si
s(1) > s(2), s(2) < s(3), s(3) > s(4) ...
Une permutation s de [n] est dite up-down si
s(1) <s (2), s(2) > s(3), s(3) < s(4) ...
Remarque : 'up' ou 'down' indiquent les sens de variations et non les positions (valeurs).
Ainsi une permutation 2 3 1 4 (up-down) commence par une montée de 2 à 3, alors
qu'une permutation 3 1 4 2 (down-up) débute par une descente de 3 à 1.
Exemples de permutations
Notations utilisées pour transcrire les permutations
Images des éléments successifs
Pour écrire la permutation s de cette façon, on donne la liste des
images s(1) s(2) ... s(n), dans cet ordre. [ Exemple]
Par exemple 2 1 4 3 5 correspond à la permutation de {1,..., 5}
telle que s(1)=2, s(2)=1, s(3)=4, s(4)=3, s(5)=5.
(On peut remarquer que dans ce cas très particulier, s est une involution).
Cycles
Cette fois on énumère tous les cycles. Chaque cycle (a b c ... d) est tel que
s(a)=b, s(b)=c, ... s(d)=a.
Les points fixes s(a)=a sont les cycles à un seul élément (a). Les dérangements
n'ont pas de points fixes.
Les transpositions sont les cycles (a b) tels que s(a)=b et s(b)=a.
Les involutions s (telles que s -1=s, ou encore s o s=Id) ont des cycles d'un ou deux éléments au plus, par exemple : (1 2)(3), [ Exemple].
Suites numériques définies par des nombres de permutations
1) Le nombre de permutations P n de [n] est P n=n! (factorielle n). P(n) est la suite A000142 de njas.
2) La suite des nombres de dérangements d(n) de [n] est la suite 1,0,1,2,9,44,265...
A000166 de njas.
3) Les nombres de permutations alternantes.
njas : A000111 Euler or up/down numbers: expansion of sec x + tan x . Also alternating permutations on n letters.
Bijections
Une bijection d'un ensemble (de départ) E sur un ensemble (d'arrivée) F est une
 application : tout élément de E a une image et une seule dans F
elle est injective : deux éléments quelconques et différents de E ont des images différentes
et elle est surjective : tout élément de F a un antécédent dans E.
Comme autres exemples de bijections, voir la page : Polynômes de Cantor, bijections de Nn sur N.
Les dérangements sont à la base du problème des chapeaux en probabilités.
|
