cycle de longueur max dans une permutation

Parmi les n! permutations possibles d'un ensemble de n éléments, on en prend une au hasard.
On désigne par L la variable aléatoire : longueur du cycle de longueur max pour cette permutation
Il est facile de voir que si k >n/2, P (L = k) = 1 / k  (et c'est utile pour le très amusant problème des 100 prisonniers, voir sa page wikipédia). Et si k < n/2, que vaut P (L=k) ? (je trouve ça très dur) 

Réponses

  • (même calculer P (L < k) me semble dur car je crois qu'il faut compter les cycles de longueur r pour tout r <=k)
  • Titi le curieux
    Modifié (12 Jun)
    Bonsoir,

    J'ai trouvé ce sujet de la semaine dernière auquel personne n'a répondu. Je me suis un peu creusé la tête et j'ai pondu cette horreur (attention il y a peut-être des erreurs en plus)
    Il y a moyen de faire des formules valides pour tout les $k$ tels que $\frac{n}{l+1} < k \leq \frac{n}{l}$, plus $l$ est grand plus ça va être compliqué. Avec $l = 1$ tu l'as déjà.

      On va noter $G^n_{k,m}$ le nombre d'élément de $\mathfrak{S}_n$ qui ne possède aucun cycle de longueur supérieure à k et exactement $m$ cycle de longeur $k$ (donc si $m=0$, c'est l'ensemble des éléments qui n'ont que des cycles de longeurs inférieure à $k$). Enfin, on notera $f(n,k) = \displaystyle \frac{1}{n!} \sum_{l\geq 1} G^n_{k,l}$ qui est la quantité recherchée.
     
     
      Cas $n/3< k \leq n/2$
      Il ne peut y avoir que 1 ou deux cycles de longueur $k$

      -1 cycle: $G^n_{k,1} = \left( \binom{n}{k} (k-1)!\right) G^{n-k}_{k,0}$ et comme $\frac{n-k}{2} \leq k$:  le facteur entre parenthèses est le nombre de cycles de longueur $k$ distinct qu'on peut produire dans un ensemble de cardinal $n$, reste à estimer $G^{n-k}_{k,0}$, mais bon si c'est les permutations dont tout les cycles sont de longueur inférieur à $k$, bah elles sont aussi plus petite que tout les $j$ supérieurs à $k$ donc:    $G^{n-k}_{k,0} = (n-k)!\left( 1 -\displaystyle \sum_{j=k}^{n-k} f(n-k,j) \right) $. Et dans le cas présent, on a $f(n-k,j) = \frac{1}{j}$ puisque $k \geq \frac{n-1}{2} $. Donc $G^n_{k,1} = \left( \binom{n}{k} (k-1)!\right) (n-k)!\left( 1 -\displaystyle \sum_{j=k}^{n-k} f(n-k,j) \right) = \frac{n!}{k}\left( 1 -\displaystyle \sum_{j=k}^{n-k} \frac{1}{j} \right) $
     
     
      -2 cycles: Le nombre de paire de cycles de longueur $k$ disjointes est $  \frac{1}{2} \binom{n}{k,k} (k-1!)^2$ le $\frac{1}{2}$ est là parce qu'on compte des paires et pas des couples, (je ne suis pas sûr de la notation que j'utilise pour les coefficients multinomiaux soit la bonne, mais quand j'écris $\binom{n}{k,j}$ c'est le coefficient trinomial égal à $\frac{n!}{k!j!(n-(k+j))!}$ lorsqu'on est dans le bon domaine, notons que c'est égal à $\binom{n}{k}\binom{n-k}{j}$). Il reste $n-2k$ élément qui se permutent entre eux comme sans contrainte parce qu'ils ne sont pas assez nombreux, et ça fait:
      $G^n_{k,2} =  \frac{1}{2}\binom{n}{k,k} (k-1!)^2 (n-2k)! = \frac{n!}{2k^2}$
     
     
      Donc au final $f(n,k) = \frac{$G^{n-k}_{k,1}+G^{n-k}_{k,2}}{n!} =  \frac{1}{2k^2} + \frac{1}{k} \left( 1 -\displaystyle \sum_{j=k}^{n-k} \frac{1}{j} \right) = \frac{1}{k} \left( 1 -\displaystyle \sum_{j=k+1}^{n-k} \frac{1}{j} \right) - \frac{1}{2k^2} $
     
     
      Cas $n/4< k \leq n/3$

      Jusqu'à trois cycles
     
       -1 cycles :  $\frac{G^n_{k,1}}{n!} = \frac{1}{k} \left( 1 - \displaystyle \sum_{j=k}^{n-k} f(n-k,j) \right)$ attention, ce coup-ci selon les valeur on a $f(n-k,j) = \frac{1}{j}$ ou la formule précédente.
       - 2 cycles : $ \frac{G^n_{k,2}}{n!} =\frac{\binom{n}{k,k} ((k-1)!)^2 }{2! n!} (n-2k)!\left( 1 - \displaystyle \sum_{j = k}^{n-2k} f(n-2k,j) \right)=\frac{1 }{2 k^2} \left( 1 - \displaystyle \sum_{j = k}^{n-2k} f(n-2k,j) \right)$
       - 3 cycles, ce coup-ci il n'y a pas assez de $n-3k$ éléments pour faire un quatrième cycle donc : $ \frac{G^n_{k,3}}{n!} =\frac{\binom{n}{k,k,k} ((k-1)!)^3 }{3! n!} (n-3k)!=\frac{1 }{6 k^3} $
       $f(n,k)$ est la somme de ces trois trucs.
       À partir de là on voit comment construire pour les $k$ encore plus petit. C'est un peu long à faire à la main, mais informatiquement une fonction récursive fera ton bonheur (ce ne sera pas optimisé, il y a sûrement moyen de factoriser des trucs, mais bon ...) .

    Remarque: j'ai aussi trouvé ça dur.

    Edit le lendemain:

      Je donne textuellement la formule: pour $\frac{n}{l+1} < k \leq \frac{n}{l}$
    la formule est $f(n,k) = \displaystyle \sum_{i = 1}^l \frac{1}{i! k^i} \left( 1 -\sum_{j\in \mathbb{N}, k\leq j \leq n -ik} f(n-ik,j)\right) $
    En fait, pour les petits $k$ (en tout cas pour 1 et 2) ça vaut peut-être le coup de prendre une autre formule:
    En notant $l$ la partie entière de $n/k$ : 
    $f(n,1) = \frac{1}{n!}$ puis:
    $f(n,k) = \displaystyle \sum_{i=1}^l \left( \frac{\binom{n}{ k ... k \text{ (i fois)}}((k-1)!)^i}{i! n!} \sum_{j=0}^{\min (k-1, n-ik)}(n-ik)! f(j,n-ik) \right) = \sum_{i=0}^l\left(\frac{1}{i!k^i  }\sum_{j=0}^{\min (k-1, n-ik)}f(j,n-ik)   \right) $
    Note: dans les sommes de la dernière formule, il y a des $f(m,0)$, il faut les prendre nuls sauf si $m=0$, auquel cas, c'est 1.

Connectez-vous ou Inscrivez-vous pour répondre.