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

points fixes des permutations



  1. #1
    loubiana

    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. Publicité
  3. #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

  4. #3
    emt

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

  5. #4
    loubiana

    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

  6. #5
    homotopie

    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. A voir en vidéo sur Futura
  8. #6
    homotopie

    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.

  9. Publicité
  10. #7
    homotopie

    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.

  11. #8
    loubiana

    Re : points fixes des permutations

    merci pour ton aide

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

  13. #10
    homotopie

    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, 22h28
  2. Groupe des permutations
    Par Seirios dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 15/02/2007, 18h29
  3. théorie des groupes en physique: groupe de permutations
    Par Julien S. dans le forum Physique
    Réponses: 2
    Dernier message: 31/08/2006, 20h25
  4. Réponses: 3
    Dernier message: 17/05/2006, 18h04
  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, 18h42