Permutations et points fixes.

malavita
malavita
dans Algèbre
Bonsoir à tous,

je dispose d'un ensemble à $n$ éléments $E$, je note $p_n(k)$ le nombre de permutations de $E$ possédant exactement $k$ points fixes, et j'aimerais démontrer que:
$$
\sum_{k=0}^n k \times p_n(k) = n!
$$
Il s'avère que j'obtiens ce résultat par le bais d'une démonstration par récurrence, qui utilise entre autre la formule donnant le nombre de dérangements d'un ensemble fini.
J'aimerais savoir s'il existe une démonstration de ce résultat "plus élégante".

D'avance merci, bonne soirée.

F.

Réponses

  • nicolas.patrois
    nicolas.patrois
    Tu peux donner une formule close de $p_n(k)$ ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Ramufasa
    Ramufasa
    Ta formule est un peu bizarre.

    On a n! bijections de E dans E. Il y a celles qui ont 0 points fixes, celles qui en ont 1, celles qui en ont 2, etc... d'oú la formule : n!= sum(pnk).

    D'où la question d'Yves peut-être ?
  • Poirot
    Poirot
    La formule est bien vraie, on peut la montrer par la théorie des représentations par exemple. On considère le caractère $\chi$ de la représentation par permutation de $\mathfrak S_E$ sur $E$. Alors la formule demandée n'est rien d'autre que $$\frac{1}{|\mathfrak S_E|} \sum_{\sigma \in \mathfrak S_E} \chi(\sigma) = 1$$ ;-)
  • Maxtimax
    Maxtimax
    Ou le théorème de Burnside, qui s'obtient par double comptage : $\displaystyle\sum_{g\in G}|\mathrm{Fix}(g)| = |G|$ (par double comptage, ou par des représentations, de manière similaire à ce que propose Poirot)
  • Ramufasa
    Ramufasa
    Du coup je ne vois pas trop mon erreur... Le dénombrement que j'ai fait me semble trivial.
  • Poirot
    Poirot
    Ta formule est correcte, ça n'empêche pas celle de malavita de l'être également puisque $p_0(n)$ est en fait grand et n'intervient pas dans sa somme.
  • Maxtimax
    Maxtimax
    Ramufasa : tu n'as pas fait d'erreur, ce sont deux formules différentes. N'oublie pas que dans la formule de Malavita tu as un $0\times p_n(0)$ qui tue tous les dérangements, que $p_n(n-1)=0$ donc le coefficient $n-1$ ne sert à rien, etc. etc.
  • aléa
    aléa
    La formule exprime que le nombre moyen de points fixe d'une permutation aléatoire suivant la loi uniforme sur les premutations vaut $1$.

    Or le nombre de points fixes vaut $F=\sum_{i=1}^n1_{\sigma(i)=i}$, d'où $E(F)=\sum_{i=1}^nP(\sigma(i)=i)=n\times 1/n=1$. Tout est normal !
  • Ramufasa
    Ramufasa
    Effectivement, merci à vous !
  • malavita
    malavita
    Merci pour vos réponses.
    Pour Nicolas, la formule de $p_n(k)$ que j'ai utilisé est $$

    p_n(k)=\binom{n}{k} d_{n-k},

    $$ où $d_{n-k}$ désigne le nombre de dérangements d'un ensemble à $n-k$ éléments, qui vaut $$

    d_{n-k}=(n-k)! \times \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}


    $$ Bonne journée à tous.
    F.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

3 Invités