points fixes des permutations
Répondre à la discussion
Affichage des résultats 1 à 10 sur 10

points fixes des permutations



  1. #1
    inviteeffa7644

    points fixes des permutations


    ------

    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

    -----

  2. #2
    Médiat

    Re : points fixes des permutations

    Citation Envoyé par loubiana Voir le message
    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...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    invite49858c65

    Re : points fixes des permutations

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

  4. #4
    inviteeffa7644

    Re : points fixes des permutations

    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

  5. A voir en vidéo sur Futura
  6. #5
    invite35452583

    Re : points fixes des permutations

    Citation Envoyé par emt Voir le message
    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 Sm (groupe des permutations de m éléments) sans points fixes=Nm.
    On a alors C(k,n)xNn-k

    Pour le calcul de Nm : à 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.

  7. #6
    invite35452583

    Re : points fixes des permutations

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

    En effet, on privéligie "m".
    Une permutation de Sm sans point fixe (noté désormais Sm*) 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 Sm-1* en "scuntant" m (m' va donc sur m"). A partir d'un élément de Sm-1* on peut fabriquer m-1 antécédents de Sm* (il y a m-1 endroits où intercaller "m"). Il y en a donc (m-1)Nm-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 : Nm-2. Donc il y a (m-1)Nm-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.

  8. #7
    invite35452583

    Re : points fixes des permutations

    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.

  9. #8
    inviteeffa7644

    Re : points fixes des permutations

    merci pour ton aide

  10. #9
    Médiat

    Re : points fixes des permutations

    Citation Envoyé par homotopie Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #10
    invite35452583

    Re : points fixes des permutations

    Citation Envoyé par Médiat Voir le message
    Je te le confirme la limite est 1/e.
    Je me disais bien que cette valeur me disait quelque chose.

Discussions similaires

  1. Méthode des points fixes et systèmes bidimensionnels
    Par tpscience dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 19/10/2007, 23h28
  2. Groupe des permutations
    Par Seirios dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 15/02/2007, 19h29
  3. théorie des groupes en physique: groupe de permutations
    Par invite3e5504c7 dans le forum Physique
    Réponses: 2
    Dernier message: 31/08/2006, 21h25
  4. systèmes de barres articulées avec points fixes(méca)
    Par invitee26bcecf dans le forum Physique
    Réponses: 3
    Dernier message: 17/05/2006, 19h04
  5. Points fixes et théorème des valeurs intermédiaires
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 27
    Dernier message: 27/07/2005, 19h42