Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

Qu'est-ce qu'une permutation connectée?

Posté par
fplanina
30-09-22 à 13:46

Bonjour ,

Est-ce que quelqu'un parmi vous a déjà entendu parler de "permutation connectée" ?

Quelle est la différence avec une permutation quelconque ?
Je ne trouve absolument aucune source là-dessus.
Merci à vous à vos retours.
Bon courage à tous.

Posté par
carpediem
re : Qu'est-ce qu'une permutation connectée? 30-09-22 à 14:20

salut

moi non plus je ne connais pas ...

mais peut-être serait-il utile voire nécessaire de nous donner l'énoncé dans lequel se trouve cette expression ...

Posté par
Vantin
re : Qu'est-ce qu'une permutation connectée? 30-09-22 à 17:46

Soit I \subset \{1, 2, . . . , n\}
Une permutation c de {1, 2, . . . , n} est dite déconnectée lorsque qu'il existe un interval I I\subset\{1, 2, . . . , n\} avec  2\leq Card(I)\leq n-1 tel que  son image π(I) est aussi un interval.
If π n'est pas déconnectée, la permutation est dite connectée.

Source: Irreducible and connected permutations Martin Klazar

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 30-09-22 à 19:53

Merci !

voici l'énoncé:

Pour tout n\inN \{0} notons c_{n} le nombre de permutations   \sigma\inS_{n} connectées,   c''est-à-dire telles que :

pour tout k\in[[1,n-1]],              \sigma([[1,k]])\neq[[1,k]]

montrer que, pour tout n\inN\{0},

n!=\sum_{k=1}^{n}{c_{k}}(n-k)!

PS: comprenez N=symbole entier naturel (je n'ai pas trouvé dans latex)

cela veux dire que si par exemple k=3 , \sigma(1) \neq1 et 2 ; aussi \sigma(2)\neq1 et 2 ???
c'est cela qu'il faut comprendre ?

Merci les gars.

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 30-09-22 à 20:10

Il faut comprendre qu'une permutation connectée est une permutation qui ne laisse aucun {1,...,k} stable.

Ca ne veut pas dire a priori que sigma soit forcément un dérangement mais seulement que \{\sigma(1),\cdots,\sigma(k)\}\neq\{1,\cdots,k\}.

Par exemple, le cycle (1 2 3) de S_3 est une permutation connectée parce que
- sigma(1) != 1
- {sigma(1),sigma(2)} = {2,3} est différent de {1,2}

De même (1 2 4) est connectée dans S4 parce que
- sigma(1) = 2 != 1
- {sigma(1),sigma(2)} = {2,4} != {1,2}
- {sigma(1),sigma(2),sigma(3)} = {2,4,3} != {1,2,3}
et pourtant sigma(3) = 3

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 30-09-22 à 20:27

Et pour t'aider à les compter : une permutation n'est pas connectée si et seulement si elle fixe un {1,..,i} pour i entre 1 et n.

Y'a autant de permutations qui fixent {1,...,i} que de couples de permutations (u,v) avec u\in ??? et v\in ???

Posté par
carpediem
re : Qu'est-ce qu'une permutation connectée? 01-10-22 à 10:44

juste une remarque  :

fplanina @ 30-09-2022 à 13:46

Est-ce que quelqu'un parmi vous a déjà entendu parler de "permutation connectée" ?

ben il suffisait de lire l'énoncé et donc nous le donner dès le premier post :
fplanina @ 30-09-2022 à 19:53

Pour tout n\inN \{0} notons c_{n} le nombre de permutations   \sigma\inS_{n} connectées,   c''est-à-dire telles que :

pour tout k\in[[1,n-1]],              \sigma([[1,k]])\neq[[1,k]]

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 01-10-22 à 16:40

Ulmiere , merci de tes réponses.

Donc si j'ai bien saisi ,je prends un exemple pour S_{4}

\sigma (1)=2
\sigma(1),\sigma(2)=(2,4)
\sigma(1),\sigma(2),\sigma(3)=(2,4,3)

A partir de là je souhaite utiliser
n!=\sum_{k=1}^{n}{c_{k}}(n-k)!

pour \sigma (1)=2
comment je calcule c_{1}? si \sigma(1)\neq 1 alors j'ai trois choix différents ? (2 , 3 et 4) ?
donc c_{1}=3 ?

c'est comme cela qu'il faut voir les choses ?
combien valent c_{1},c_{2},c_{3} et c_{4} ? quel est  la méthode de recherche stp , je ne retrouve pas le compte...

Encore merci !

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 01-10-22 à 17:21

c_1 est le nombre d'éléments de S_1 tels que pour tout k\in\emptyset, blablabla. Une proposition qui commence par "pour tout k\in\emptyset" étant une tautologie, n'importe quelle permutation de S_1 fait l'affaire et comme il n'y en a qu'une, c_1 = 1.

c_2 est le nombre d'éléments de S_2 tels que \sigma(1)\neq 1. Y'en a qu'une, et c'est la transposition (1 2).

c_3 est le nombre d'éléments de S_3 tels que
a) \sigma(1)\neq 1
b) et \{\sigma(1),\sigma(2)\} \neq \{1, 2\}.

Une permutation qui n'envoie pas 1 sur 1 l'envoie soit sur 2 soit sur 3.
* si on envoie 1 sur 2, alors 2 ne doit pas être envoyé 1 sinon on contredit b) et bien-sûr 2 ne peut être envoyé sur 2 sinon 2 aurait deux antécédents, ce qui contredit le fait que sigma est une bijection. Donc 2 ne peut être envoyé que sur 3. 2 et 3 étant déjà dans l'image de \sigma, on aura forcément \sigma(3) = 2 donc ça fait une possibilité qui est \sigma = (1 2 3)

* si on envoie 1 sur 3, 2 est libre d'étre envoyé sur 1 (et donc 3 sur 2) ou sur 2 (et donc 3 sur 1).
Ca fait donc deux possibilités qui sont (1 3 2) et (1 3).

Au total, on a donc c_3 = 3, ce qui coincide avec la formule car 6 = 3! et 3*0! + 1*1! + 1*2! = 3 + 1 + 2 = 6



Tu peux trouver c_4 maintenant

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 01-10-22 à 17:23

Petite coquille, c'est bien-sûr

Citation :
2 ne peut être envoyé que sur 3. 2 et 3 étant déjà dans l'image de \sigma, on aura forcément \sigma(3) = 1


qu'il faut lire

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 02-10-22 à 14:34

pour c_{3} les combinaisons sont au nombre de 13 avec :

(2 3 4 1)
(2 4 1 3)
(3 2 4 1)
(3 1 4 2)
(3 4 2 1)
(2 4 3 1)
(3 4 1 2)
(4 1 3 2)
(4 2 1 3)
(4 3 2 1)
(4 1 2 3)
(4 2 3 1)
(4 3 2 1).

Je pense que c'est bon. Merci de ton explication , ça a été une grande limpidité.

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 02-10-22 à 14:35

mince c'est pour c_{4} !!! la liste

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 02-10-22 à 15:53

Citation :

(2 3 4 1)
(2 4 1 3)
(3 2 4 1)
(3 1 4 2)
(3 4 2 1)
(2 4 3 1)
(3 4 1 2)
(4 1 3 2)
(4 2 1 3)
(4 3 2 1)
(4 1 2 3)
(4 2 3 1)
(4 3 2 1)



Le nombre me semble correct mais il y a beaucoup de doublons dans ta liste

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 03-10-22 à 11:32

Salut à toi !

En quoi ce sont des doublons ?

Je veux dire , l'ordre des nombres a une importance . en quoi par exemple (3 4 2 1) est un doublon de (4 2 1 3) ? dans le premier cas : \sigma (1)=3 par exemple
dans le second cas \sigma (1)=4 etc
c'est deux cas différents , je veux dire on compte toutes les permutations possibles , j'ai bien vu que les nombres s'enchaînaient de la même manière (d'où la thèse du doublon)  , simplement admettons que j'exclus tous les doublons , il n'en reste que 6 :

(2 3 4 1)
(2 4 1 3)
(3 1 4 2)
(3 4 2 1)
(2 4 3 1)
(4 3 2 1)


d'accord quels sont les 7 autres alors ... je ne saisis pas
Merci

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 03-10-22 à 12:56

La notation (x y z) signifie que \sigma(x) = y, \sigma(y) = z et \sigma(z) = x.

En fait tu voulais donner (\sigma(i), 1\leqslant i \leqslant n), mais alors il ne faut pas oublier les virgules entre les nombres !


Ok, quelles contraintes doivent respecter les permutations connectées de {1, 2, 3, 4} ?
a) \sigma(1) \neq 1
b) \{\sigma(1),\sigma(2)\}\neq\{1,2\}
c) \{\sigma(1),\sigma(2),\sigma(3)\}\neq\{1,2,3\}

Soit f une telle permutation. Je l'appelle f pour ne pas avoir à mettre des balises tex partout pour écrire \sigma.
Par a), on sait que f(1) != 1, donc f(1) ne peut valoir que 2, 3, ou 4.


Cas 1: f(1) = 2
Alors f(2) != 1, sinon on aurait {f(1),f(2)} = {1,2}, ce qui contredit b).
Par ailleurs, f(2) ne peut valoir 2 puisque 2 = f(1). Ce serait contredire l'injectivité de f.
Ainsi f(2) vaut soit 3, soit 4.

Si f(2) = 3 alors f(3) ne peut pas valoir 1, sinon {f(1),f(2),f(3)} = {2,3,1} = {1,2,3} contredit c). Donc f(2) = 3 implique f(3) = 4, et la seule possibilité qui reste pour f(4) est 1. La permutation ainsi formée est (1 2 3 4)

Au contraire, si f(2) = 4, {f(1),f(2)} = {2,4} contient 4, donc il n'y a aucun risque de contredire b) ou c) en choisissant f(3) et f(4). Les deux permutations qu'on obtient sont (1 2 4) et (1 2 4 3).



Cas 2: f(1) = 3
Comme toujours, la valeur de f(4) est le seul élément de {1,2,3,4} qui reste quand on a fixé l'image de 1,2, et 3.
On note que {f(1),f(2)} n'a aucune chance d'être {1,2} parce que cet ensemble contient 3. Par contre {f(1),f(2),f(3)} sera égal à {1,2,3} si {f(2),f(3)} = {1,2}, contredisant c). Il s'agit donc d'interdire (f(2),f(3)) = (1,2) et (f(2),f(3)) = (2,1).
Les permutations auxquelles cela mène sont donc (1 3), (1 3)(2 4), (1 3 2 4), (1 3 4)

Cas 3: f(1) = 4
Là c'est jackpot. 4 étant toujours un élément de {f(1),f(2)} et {f(1),f(2),f(3)}, il n'y a absolument aucun risque de contredire b) ou c). Donc les valeurs de f(2), f(3), et f(4) sont totalement libres.
Les permutations auxquelles cela mène sont donc (1 4), (1 4)(2 3), (1 4 2), (1 4 2 3), (1 4 3), (1 4 3 2),

Au total on a trouvé 3 + 4 + 6 = 13 permutations connectées

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 03-10-22 à 16:26

d'accord ! donc voici la liste:

(2,3,4,1)
(2,4,3,1)
(2,4,1,3)
(3,1,4,2)
(3,4,1,2)
(3,4,2,1)
(3,2,4,1)
(4,2,3,1)
(4,3,2 ,1)
(4,1,3,2)
(4,3,1,2)
(4,2,1,3)
(4,1,2,3)
donc c_{4}=13


par contre tu cites la permutation (1 3) ce qui donne (3,2,1,4) elle ne marche pas celle là non?

T'assures de bien m'expliquer comme cela. Bon aprem.

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 04-10-22 à 11:35

Oui, je suis allé un peu vite. Si f(1) = 3, nos permutations commenceront par (1 3

Si f(3) = 1 alors f(2) != 2 sinon on contredit c) donc il n'y a que (1 3)(2 4)

Si f(3) = 2, ça commence par (1 3 2. Pas (1 3 2) sinon on contredit c), donc il ne reste que (1 3 2 4)

Si f(3) = 3, f(1) = f(3) donc 1 = 3. Absurde

Si f(3) = 4, on peut avoir f(4) = 1 et donc (1 3 4).
Ou f(4) = 2 et donc (1 3 4 2).

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 04-10-22 à 11:41

Yes !

donc c'est bon ma liste est bonne ? :p

Merci encore !

Posté par
Ulmiere
re : Qu'est-ce qu'une permutation connectée? 06-10-22 à 11:43

Ca m'a l'air correct, mais tu n'as pas répondu à l'exercice, qui demandait de montrer que n! = \sum_{k=1}^n c_k(n-k)!

Posté par
fplanina
re : Qu'est-ce qu'une permutation connectée? 07-10-22 à 17:38

car il y a décomposition entre permutation connectée de [[1,k]] et une permutation quelconque  de [[k+1,n]]



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1580 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !