points fixes des permutations

[inviteeffa7644]

je suis bloquée sur cette question (probleme de CCP dont je ne connais pas l'année).
Sn ensemble des permutations de [[1,n]]
si 0 <ou= k <ou= n, combien d'éléments de Sn ont exactement k points fixes?
merci de m'aider
-----

[Médiat]

je suis bloquée sur cette question (probleme de CCP dont je ne connais pas l'année).
Sn ensemble des permutations de [[1,n]]
si 0 <ou= k <ou= n, combien d'éléments de Sn ont exactement k points fixes?
merci de m'aider

Il "suffit" de choisir les k points fixes (parmi n), puis de choisir de toutes les façons possibles le n-k autres images...

[invite49858c65]

bonjour
Ca reviens à compter le nombre de bijections de l'ensemble {1,..,n} qui laissent fixe k points.
Tu dénombre le nombre de facons de choisir les k points fixes, puis le nombre de façons de choisir les n-k images des autres points.
Tu en as donc : C(k,n)*(n-k)!
sauf erreur...

[inviteeffa7644]

désolé, mais ça ne marche pas, par exemple, pour (1,2,3), il y a 2 permutations qui ont 0 point fixe mais 3!/0!=6

[A voir en vidéo sur Futura]

[invite35452583]

Tu en as donc : C(k,n)*(n-k)!
sauf erreur...

Oui erreur : dans les (n-k)! il y en a qui ont des points fixes surnéméraires.
Toute formule qui ne donne pas 0 pour n-1 points fixes est nécessairement fausses.

Il faut trover combien d'éléments de S_m (groupe des permutations de m éléments) sans points fixes=N_m.
On a alors C(k,n)xN_n-k

Pour le calcul de N_m : à part une méthode bourrine donnant une formule par récurrence (il va falloir décomposer 3=3 ; 4=4=2+2 ; 5=5=3+2 ; 6=6=4+2=3+3=2+2+2...), je ne vois pas pour l'instant. Je vais y réfléchir.

[invite35452583]

On a N_m=(m-1)(N_m-1+N_m-2)

En effet, on privéligie "m".
Une permutation de Sm sans point fixe (noté désormais S_m*) est soit telle que :
a) m'->m->m" avec m' et m" distincts (ils sont distincts de m par définition)
b) m'->m->m'
On envoie les type a sur S_m-1* en "scuntant" m (m' va donc sur m"). A partir d'un élément de S^m-1* on peut fabriquer m-1 antécédents de S_m* (il y a m-1 endroits où intercaller "m"). Il y en a donc (m-1)N_m-1
On envoie les type b sur S*({1,...,m-1}\{m'}) en retirant le 2-cycle (mm'). Il y a m-1 possibilités pour m' et tous les S*({1,...,m-1}\{m'}) ont même cardinal : N_m-2. Donc il y a (m-1)N_m-2 permutations de type b.

On peut vérifier N1=0, N2=1, N3=2, N4=9, N5=44 (N4 : il y a 3 (2x2)-cycles 6 4-cycles N5 : il y a 24 5-cycles et 20 (3x2) cycles).
N3=(3-1)(1+0)
N4=(4-1)(2+1)
N5=(5-1)(9+2)
Ca roule !

Peut-on arriver à partir de cette relation de récurrence à une formule fermée, je ne sais pas.

[invite35452583]

Je viens de regarder sur Excell le taux de permutations sans points fixes sur le nombre total de permutations. Cela converge assez vite vers 0,3678794412.

[inviteeffa7644]

merci pour ton aide

[Médiat]

Je viens de regarder sur Excell le taux de permutations sans points fixes sur le nombre total de permutations. Cela converge assez vite vers 0,3678794412.

Je te le confirme la limite est 1/e.

[invite35452583]

Je te le confirme la limite est 1/e.

Je me disais bien que cette valeur me disait quelque chose.