Somme utilisant des inversions

Bonjour,
Je peine à prouver la formule suivante, j'ai essayé par récurrence mais ça ne donne pas grand chose.
Sinon j'ai essayé de voir cette somme comme une fonction génératrice en introduisant la variable aléatoire X qui correspond au nombre de permutations ayant k inversions, mais après gros problème sur le calcul de P(X=k).
Une indication s'il vous plait.82156

Réponses

  • Bonjour,

    Pour l'hérédité, on peut associer à toute $\pi\in S_{n+1}$, une permutation $\tilde\pi\in S_{n}$.

    On la définit par : $
    \quad
    \tilde\pi(i) =
    \begin{cases}
    \pi(i) & \text{ pour } i < \pi^{-1}(n+1) \\
    \pi(i+1) & \text{ pour } i \ge \pi^{-1}(n+1) \\
    \end{cases}
    %\left\{
    %\begin{array}
    %
    %\end{array}
    %\right.
    $

    Alors, on a : $
    \quad
    \def\inv{\mathrm{inv}}
    \sum\limits_{\pi\in S_{n+1}}
    x^{\inv(\pi)}
    = \sum\limits_{i=1}^{n+1}
    \sum\limits_{\pi^{-1}(n+1)=i}
    x^{\inv(\pi)-\inv(\tilde\pi)}
    \cdot
    x^{\inv(\tilde\pi)}
    $.
  • Je ne vois pas comment tu pourras utiliser l'hypothèse de récurrence .
  • Si $\pi^{-1}(n+1) = i$, alors :

    1. combien vaut $\def\ind{\mathrm{ind}}\ind(\pi)-\ind(\tilde\pi)$ ?
    2. quelles sont les valeurs possibles pour la permutation $\tilde\pi$ ?
Connectez-vous ou Inscrivez-vous pour répondre.