Suite et....fin ?

[nodgim]

Soit la bijection B de E vers E, E ensemble des entiers de 1 à 100. B(k) est une valeur prise complètement au hasard.
Soit S, la suite telle que S0=B(1) et S(n+1)=B(B(n)).
Quelle est la probabilité pour que la suite S comporte exactement toutes les valeurs de E ?

Très court, en principe. :id:

[ThSQ]

<< nimp >>

[Doraki]

Si B² n'a qu'une seule orbite, ça veut dire que B en a qu'une seule aussi, donc c'est un 100-cycle, et donc comme 100 est pair, B² c'est deux 50-cycles disjoints et pas un 100-cycle.
Donc c'est pas possible.

La proba est donc de 0.

[ThSQ]

Ah oui, m*rde, j'ai lu trop vite l'énoncé. :marteau:

[nodgim]

Si B² n'a qu'une seule orbite, ça veut dire que B en a qu'une seule aussi, donc c'est un 100-cycle, et donc comme 100 est pair, B² c'est deux 50-cycles disjoints et pas un 100-cycle.
Donc c'est pas possible.

La proba est donc de 0.

Ma présentation est ambiguë, j'aurais dû écrire:
S0=B(1) et
S(k+1)=B(Sk)

Pour obtenir une suite de 50 termes, la proba doit avoisiner les
C(100,50)*49!/100! si je ne m'abuse.
Très simplifiable!

[Doraki]

Ah ben oui j'avais pas vu que c'était mal typé.
S(n+1) = B(S(n))

Ben dans ce cas, en choisissant au hasard les valeurs de la permutation au fur et à mesure qu'on avance dans le cycle, c'est
99/100 * 98/99 * 97/98 * ... * 2/3 * 1/2 * 1/1 = 1/100

Ou sinon, on peut écrire un 100-cycle de 100 manières différentes (selon le point de départ qu'on prend) en écrivant la liste des 100 valeurs prises dans l'ordre par les itérés du cycle à partir d'un point de départ.
Le nombre de telles listes est aussi le nombre de permutations de {1...100}
(c'est juste l'interprétation de la liste de nombres qui est différent)
Donc p = 1/100


En reprenant le 1er raisonnement pour avoir la proba que l'orbite ait n éléments,
ça fait 99/100 * 98/99 * ... * (100-n+1)/(100-n+2) * 1/(100-n+1)
= 1/100 aussi.

Tiens c'est marrant.

[ThSQ]

Tiens, ben j'avais bon en fait :ptdr: