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.
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.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 63 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 313 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres