Nombre de Permutations

[luigi]

Bonjour, il s'agit d'un exo que j'ai trouvé dans un livre. Je ne comprends pas très bien le corrigé :

La question : Détailler les classes de conjuggaison de (permutations) quand n = 3,4,5,6 en précisant l'ordre de chaque élément.

Dans le corrigé, pour le cas n = 4 par exemple, on a un tableau dans la première colonne, on décompose selon la structure :
n = 1+1+1+1
= 2+1+1
= 3+1
= 4
= 2+2

Puis à côté, on a le nombre de permutations :
Pour 1+1+1+1, c'est 1
Pour 2+1+1 c'est 6
Pour 3+1 c'est 8
4 -> 6
2+2 -> 3

Je sais que le nombre de p-cycles est donné par la formule (p-1)!*Cn_p
Donc en tripatouillant, je comprends comment on fait pour tous les cas SAUF le cas 2+2 où ça marche plus. Donc comment faire ? Y'a une formule générale dans ce cas ?

MErci d'avance !

[yos]

Bonjour.
Les classes de conjugaison de sont constituées des permutations qui se décomposent en un même nombre de cycles de même longueur. C'est assez facile à voir.

Par exemple dans , il y a 7 classes de conjugaison :
{Id}
{Transpositions}
{3-cycles}
{4-cycles}
{5-cycles}
{composées de 2 transpositions de supports disjoints}
{composées d'une transposition et d'un 3-cycle, de supports disjoints}

Bref c'est comme au poker.

[luigi]

Merci Yos !

J'ai bien compris pour les classes de conjugaisons :) Ce que je capte pas, c'est le "nombre de permutations" pour chaque classe de conjugaison.

[yos]

Pour 2+2 dans le cas n=4, tu choisis l'image de 1 et ta permutation est déterminée : (12)(34) ou (13)(24) ou (14)(23).

Dans le cas n=5, tu commences par choisir l'élément seul (5 choix) et pour les 4 qui restent, il y a 3 possibilités comme pour n=4. D'où 12 permutations type 2+2.

[ThSQ]

le "nombre de permutations" pour chaque classe de conjugaison.

si , une décomposition avec les c_i tous différents
il y a permut dans la classe en question.

S'ils sont pas tous différents il faut pas les compter deux fois.

[yos]

Ben faut plutôt éviter de choisir plusieurs fois les mêmes...

[luigi]

Pour 2+2 dans le cas n=4, tu choisis l'image de 1 et ta permutation est déterminée : (12)(34) ou (13)(24) ou (14)(23).

Dans le cas n=5, tu commences par choisir l'élément seul (5 choix) et pour les 4 qui restent, il y a 3 possibilités comme pour n=4. D'où 12 permutations type 2+2.

Ok ! J'ai capté le truc ! Merci ! :zen:

Sinon, dans le cas n = 5, ce serait plutôt 15 (5*3) permutations non ?

[yos]

Oui Luigi c'est bien 15.

si , une décomposition avec les c_i tous différents
il y a permut dans la classe en question.

S'ils sont pas tous différents il faut pas les compter deux fois.

Ce qui ne va pas c'est que tu prends les parmi les mêmes n éléments à chaque fois.

[ThSQ]

Ce qui ne va pas c'est que tu prends les parmi les mêmes n éléments à chaque fois.

Ah ouais .... :briques:

[ThSQ]

Comme c'était stimulant (et un peu vexant) de ne pas avoir trouvé la bonne formule donnant la taille d'une classe de conjugaison dans voici un nouvel essai un peu plus réfléchi (pendant un cours de français assez atroce ...) cette fois pour trouver une belle (et exacte tant qu'à faire...) formule !


Dans on écrit c'est-à-dire qu'on considère la classe de conjugaison avec k-cycles. Ces décompositions donnent toutes les classes de combinaisons.

Il y a n! façons de remplir les différents cycles mais il y de nombreux "sur-comptages" comme me l'a fait remarqué yos.

1- Les -cycles peuvent être décalés entre eux de façons, il faut donc diviser par
2- Chaque -cycle peut être décalé de façons, il faut donc
diviser par


Le taille de la classe de conjugaison donnée de manière unique par est donc


A noter qu'il n'était pas évident a priori que le nombre donné par
la formule étaut bien un entier ...

Est-ce correct cette fois yos ? Merci :we:

[yos]

Les -cycles

i-cycles?
Oui c'est bon.

[ThSQ]

Merci yos .