Accueil / Combinatoire / Combinatoire Permutations / Permutations up-down

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

Le programme écrit en javascript détermine au choix, pour tout naturel n (de n0 à n1)
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]

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


Permutations permutations quelconques     dérangements    down-up (alternantes)    up-down    

Indiquez la valeur de n ou deux bornes :

Nombre maximum de permutations à afficher ou 0 pour toutes :

Affichage des cycles





Suites numériques définies par des nombres de permutations

1) Le nombre de permutations Pn de [n] est Pn=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.


Accueil / Combinatoire / Combinatoire Permutations / Permutations up-down

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014