Forum : algèbre :
Groupe de permutations Invariants

Bonjour

Est ce que quelqu'un pourrait me dire s'il y a un moyen à l'aide d'une formule de dénombrer les permutations laissant 1, 2, 3,..., p éléments invariants dans un  ensemble à n éléments.
pour n=3 j'ai trouvé 1 + 3 + 2 c'est à dire l'identité laisse 3 invariants les 3
transpositions, 1 invariant et les 3-cycles , 0 invariants
Pour n = 4 j'ai trouvé 1+6+11+6.
Pour n=5? mystère, quoique j'ai une petite idée.
En fin de compte existe t il un développement de n! en somme.
Merci de votre aide.

Salut, il y a autant de permutations d'un ensemble à n éléments qui en fixent exactement p que  de permutations des (n-p) éléments restants, c'est-à-dire (n-p)!.

Merci de ta réponse.
Mais pourtant il y a bien pour n=3, 3 transpositions qui fixent 1 élément
soit (213), (321) et (132) et c'est différent de (3-1)! = 2 non?
Pourrais tu m'expliquer où est mon erreur.
Merci d'avance.

Ah oui mais là tu as fait varier l'élément invariant!

Dans ton énoncé initial, tu sous-entendais qu'on cherchait, par exemple, toutes les permutations qui fixaient l'élément 1.

Il y a Id, (23) et c'est tout si n=3.

De plus, tes dernières réponses sont de toute façon fausses:

Hormis Id, la permutation fixant 1 est (2,3), celle fixant 2 est (1,3) et celle fixant 3 est (1,2).

Les 3-cycles comme (2,1,3) n'ont aucun élément invariant.

Oui j'ai mal noté, excuse moi, mais j'avais bien mis au début

citation :
pour n=3 j'ai trouvé 1 + 3 + 2 c'est à dire l'identité laisse 3 invariants les 3 transpositions, 1 invariant et les 3-cycles , 0 invariants

Finalement peut- t- on trouver une formule qui donne le nombre de permutations donnant  tous les invariants possibles dans n éléments
C'est ce que j'avais demandé au départ,une telle formule existe t elle?

OK, dans ce cas reprends ce que je t'ai dit, il suffit de multiplier ma réponse de départ par le nombre de choix de p points invariants parmi n, qui est C_n^p.

Pour n = 4 je trouve 11 permutations qui laissent 0 invariants mais ça n'a pas l'air de coller avec ta formule.

En effet, je me rends compte que ma formule est fausse, désolé!

En effet, (n-p)! correspond au nombre de permutations qui fixent au moins p éléments donnés parmi n, et non exactement p...

Par contre, pour n=4 et p=0 il y a 30 permutations qui marchent (6 doubles-transpositions et 24 4-cycles).

Bon je me rappelle qu'on peut introduire le nombre de dérangements Dn qui n'ont aucun élément invariant.

Par conséquent, il y aura C_n^p.D_n-p permutations avec exactement p points invariants.

Pour trouver la formule donnant Dn, on peut raisonner par récurrence.

Fais une recherche sur le net, je n'ai plus cela en tête.

Bonjour
Il me semblait que pour n=4 il y avait au maximum 24 permutations mais bon
puisque tu me dis qu'il y en a 30 qui marchent, je vais vérifier.

citation :
Fais une recherche sur le net, je n'ai plus cela en tête

J'ai beau chercher , je ne trouve pas de trace d'une telle formule.

Bonjour,

décidément j'ai dit des bêtoises, désolé!

Je reprends donc:

il n'y a que 3 doubles-transpositions, qui sont (12)(34), (13)(24) et (14)(23)

Pour compter les 4-cycles, on a 3 possibilités pour l'image de 1, et 2 pour l'image de l'image de 1, ce qui détermine entièrement le 4-cycle.Il y a donc 6 4-cycles.

Seuls les 4-cycles et les doubles transpositions n'ont aucun point invariant, ce qui  donne finalement 9 permutations sans élémént invariant, sauf nouvelle erreur de ma part!

Que voyais-tu d'autre?

Voici un lien pour le nombre de dérangements:

Salut !


appelons An le nombres de permutation sans points fixe d'un ensemble à n éléments, (et A0=1 )

le nombre de permutation d'un ensemble à n element ayant p point fixe est alors : binomial(n,p)*A(n-p), il suffit donc de savoir calculer les nombres An :

or on a la relation de récurence :
somme pour p=0 a n des binomial(n,p)*A(n-p) = n!

(on dénombre les permuttion de [1,n] en fonction de leur nombre de point fixe...)

on peut interpréter cette relation comme un produit de Cauchy, ce qui permet de calculer une série génératrice exponentielle :

on pose f(x)=somme pour n>=0 des A(n)/n!*x^n

la relation précédente s'interprète alors comme :
f(x)*(somme des x^n/n!) = somme des x^n

soit f(x)=exp(-x)/(1-x)

apres j'ai pas réussis à expliciter le terme géneral du dévelopement en série de cette fonction. donc je doute que les An aie une forme simple.

ceci un série génératrice aussi simple permet déjà de faire beaucoup de chose... (calculer un développement asymptotique par exemple...)

enfin, on peut quand meme ecrice un peu plus explicitement que :

A(n)=n!*somme de k=0 a n de (-1)^k/k!

les première valeur de A(n) sont (à partir de A(0)) :
1,0,1,2,9,44,265,1854,14833,133496,1334961 etc...

est assymptotiquement, on à A(n)~n!/e
on doit meme avoir A(n)=n!/e+O(1)

En fait si on à une forme close :

si n est pair, An est l'arrondi supérieur de n!/e
si n est impaire, An est l'arrondi inférieur de n!/e

salut

on veut permuter n éléments sans points fixe donc:
pour le 1° j'ai n-1 choix (il n'est pas sa propre image)
pour le 2° j'ai n-2 choix (ni lui ni l'image du 1°)
pour le 3° j'ai n-3 choix (ni lui ni l'image des 2 premiers)
donc au total (n-1)!

si p sont fixes parmi n j'ai C_n^p choix pour choisir mes points fixes et (n-p-1)! permutations pour les autres
soit au final n!/[p!(n-p)]

Carpediem: non il y a un problème dans ton raisonement :

pour le premier, tu as en effet (n-1) choix. pour le deuxieme en revanche tu as (n-2) choix, sauf si tu a choisit 2 comme étant l'image du premier, dans qu'elle cas tu as toujour (n-1) choix...

parceque la avec ton raisonement, pour le dernier, il te reste (n-n)=0 choix... ce qui est un peu embêtant...

enfin, cf les postes précédant

damned

je vais revoir ça

Bonjour et merci à tous les trois de votre aide.

citation :
Seuls les 4-cycles et les doubles transpositions n'ont aucun point invariant, ce qui  donne finalement 9 permutations sans élémént invariant, sauf nouvelle erreur de ma part!

OK c'est ce que j'avais trouvé.

citation :
apres j'ai pas réussis à expliciter le terme géneral du dévelopement en série de cette fonction. donc je doute que les An aie une forme simple.

Je pensais avoir trouvé une distribution de n! qui donne le nombre de permutations qui laissent un certain nombre de points fixes donc les An mais apparemment ça ne marche pas.
Par contre ce que j'ai trouvé donnerait plutôt le nombre de permutations qui sont composées du même nombre de transpositions.
J'ai vérifié pour 3 et 4 ça marche.
n = 1n
n(n -1) = 1n2  - 1n
n(n -1)(n - 2) = 1n3  -  3n2 + 2n
n(n - 1)(n - 2)(n - 3)  =  1n4  -  6n3  + 11n2  -  6n
Les coefficient donnent le nombre de permutations par classe.