Intuition derrière une identité combinatoire

Pour \(\sigma \in \mathfrak{S}_n\), on note \(|\sigma|\) le nombre de cycles à supports disjoints de \(\sigma\). Pourquoi l'identité suivante est-elle évidente ?
\[
\frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_n} \left(\frac{1}{2}\right)^{|\sigma|} = \frac{1}{4^n}\binom{2n}{n}
\]

Réponses

  • Ça ne me saute pas aux yeux. J'ai bien sûr envie d'y voir une interprétation probabiliste (on a l'espérance d'une fonction d'une permutation aléatoire à gauche ; on a la probabilité qu'une marche simple issu de 0 soit en 0 à l'instant 2n à droite) mais je ne vois pas de lien entre les deux. À quoi ressemble la preuve dont tu disposes ?
  • Je ne vois pas non plus le lien avec la marche aléatoire. Ma preuve consiste à calculer le terme de gauche comme un produit d'espérances (1/2*1/k + 1*(1 - 1/k)) pour k de 1 à k, et on reconnaît alors le terme de droite mais ce n'est pas très satisfaisant.
  • Bonjour,

    Je sais montrer (par récurrence) une formule plus générale qui donne la formule de Siméon quand $x=\dfrac12$:
    $\displaystyle\sum_{\sigma \in \mathfrak{S}_n} x^{|\sigma|} = \prod_{k=0}^{n-1} (x+k)$.

    Mais je ne vois pas pourquoi ce serait "évident" si $x=\dfrac12$.
  • Merci jandri, j'avais déjà cette formule en procédant comme indiqué dans mon précédent message. Ce qui m'intéresserait vraiment le lien avec la marche aléatoire / loi binomiale.
  • Le côté gauche fait penser au théorème de dénombrement de Polya. Mais des coloriages avec 1/2 couleur, bizarre !
  • Je ne vais pas révolutionner le monde, c'est un truc que Siméon a sans doute remarqué, mais le membre de gauche représente la probabilité que tout le monde mange des chips au restaurant chinois.

    On sert deux trucs au restaurant chinois: du riz, et des chips.

    Quand quelqu'un entre au restaurant chinois alors qu'il y a déjà $n$ personnes, il rejoint une table donnée de $m$ personnes avec probabilité $m/(n+1)$. Avec probabilité $1/(n+1)$, il crée une nouvelle table.
    Le premier arrivé sur une table choisit et commande pour tout le monde. Avec proba $1/2$, il commande des chips, avec proba $1/2$ du riz.

    Et c'est un problème important, cette histoire de manger des chips (Hugues, salut !)

    Bref, je n'ai pas fait beaucoup avancer le schmilblic, mais il y a des gens qui connaissent bien le restaurant chinois (voir Ewens formula), peut être qu'ils ont des idées sur le lien avec la marche.
  • La formule de Siméon joue un rôle important dans l'article

    'The Hyperoctahedral Group, Symmetric Group representations and the Moments of the Real Wishart Distribution

    de Graczyk, Letac,Massam (Journal of Theoretical Probability , Vol 18 , 2005, 1-42).

    Elle est démontrée page 11 par fonctions génératrices. Elle est aussi un cas particulier un peu caché de la Proposition 1. En gros, on considère $Z=(Z_1,\ldots,Z_r)$ standard normal dans $ \mathbb{R}^r$ et la matrice de Wishart $S=Z^tZ/2$ et on calcule de deux manières $\mathbb{E}((\mathrm{trace} S)^r)$, l'une en dérivant $r$ fois la TF de Laplace de $S$ (premier membre de l'égalité de Siméon) et l'autre bêtement parce que $\mathrm{trace} S$ suit une loi gamma.
  • Je précise mon histoire de restaurant chinois.

    Si $(X_n)$ est une suite de variables indépendantes avec $X_n$ qui suit la loi uniforme sur $\{1,\dots,n\}$, on suppose que l'individu $n$ va s'assoir à la même table que l'individu $X_n$.

    C'est bien le problème du restaurant chinois.
    Le nombre de tables ouvertes est $\sum_{k=1}^n 1_{\{X_k=k\}}$.
    Mais c'est aussi le nombre de cycles de la permutation $\sigma_n=(1 X_1)(2 X_2)\dots (n X_n)$.

    Si $x$ est la probabilité que le chef de table commande des chips, en notant $E$ la proba que tout le monde commande des chips, on a $P(E|\sigma_n)=x^{|\sigma_n|}$.

    Mais on peut démontrer (voir par exemple Garet-Kurtzmann, exercice corrigé 105), que $\sigma_n$ suit la loi uniforme sur le groupe symétrique, d'où

    $P(E)=\frac1{n!}\sum_{\sigma \in\mathfrak{S}_n} x^{|\sigma|}$.

    Par ailleurs, $P(E)=E[ x^{|\sigma_n|}]=E \prod_{i=1}^n x^{1_{X_i=i}}=\prod_{i=1}^nE x^{1_{X_i=i}}=\prod_{i=1}^n (1+(x-1)/i)$

    (C'est la formule de Jandri et Siméon).

    Ceci dit, si on veut juste $P(E)$, la récurrence $P(E_i)= (1+(x-1)/i)P(E_{i-1})$ est du niveau L2.
  • @aléa : merci d'avoir développé la preuve de façon imagée, c'est bien comme ça que j'obtiens la formule. Est-ce que tu pourrais préciser ce qui te fait dire que "c'est un problème important, cette histoire de manger des chips" ? (et qui est ce Hugues ?)

    @P : merci pour la référence, j'irai voir ton article dès que j'y aurai accès.
  • Mais bien sûr !
Connectez-vous ou Inscrivez-vous pour répondre.