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

Soit
Une permutation c de {1, 2, . . . , n} est dite déconnectée lorsque qu'il existe un interval I avec   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

Merci !

voici l'énoncé:

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

pour tout k[[1,n-1]],              ([[1,k]])[[1,k]]

montrer que, pour tout nN\{0},

n!=

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

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

Merci les gars.

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 .

Par exemple, le cycle (1 2 3) de 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

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 et

juste une remarque  :

fplanina @ 30-09-2022 à 19:53

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

pour tout k[[1,n-1]],              ([[1,k]])[[1,k]]

Ulmiere , merci de tes réponses.

Donc si j'ai bien saisi ,je prends un exemple pour





A partir de là je souhaite utiliser
n!=

pour
comment je calcule ? si alors j'ai trois choix différents ? (2 , 3 et 4) ?
donc =3 ?

c'est comme cela qu'il faut voir les choses ?
combien valent ? quel est  la méthode de recherche stp , je ne retrouve pas le compte...

Encore merci !

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

est le nombre d'éléments de tels que . Y'en a qu'une, et c'est la transposition .

est le nombre d'éléments de tels que
a)
b) et .

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 , on aura forcément donc ça fait une possibilité qui est

* 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 , ce qui coincide avec la formule car 6 = 3! et 3*0! + 1*1! + 1*2! = 3 + 1 + 2 = 6



Tu peux trouver maintenant

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 , on aura forcément

pour 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é.

mince c'est pour !!! la liste

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 : par exemple
dans le second cas 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

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

En fait tu voulais donner , 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)
b)
c)

Soit f une telle permutation. Je l'appelle f pour ne pas avoir à mettre des balises tex partout pour écrire .
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

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

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

Yes !

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

Merci encore !

Ca m'a l'air correct, mais tu n'as pas répondu à l'exercice, qui demandait de montrer que

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