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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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)}
$.
1. combien vaut $\def\ind{\mathrm{ind}}\ind(\pi)-\ind(\tilde\pi)$ ?
2. quelles sont les valeurs possibles pour la permutation $\tilde\pi$ ?