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

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.

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.