Permutations et dérangements de [n] = {1,2, ... n}
Permutations alternantes ou down-up
Permutations up-down

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.

Le programme écrit en javascript détermine au choix, pour tout naturel n (de n₀ à n₁)

1) les permutations de [n] = {1,...,n}. [Exemple], [Exemple]
2) les dérangements de [n], [Exemple]
3) les permutations alternantes (ou down-up) de [n]. [Exemple]
4) les permutations up-down de [n]. [Exemple]

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

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.

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 Nⁿ sur N.
Les dérangements sont à la base du problème des chapeaux en probabilités.