Matematyka.pl

W jaki sposób obliczyć wartość oczekiwaną liczby cykli w permutacji losowej \(\displaystyle{ n}\) liczb?
Największym (chyba) problemem jest tu zliczenie ile jest permutacji o dokładnie \(\displaystyle{ k}\) cyklach, jak je zliczyć?

Poczytaj o liczbach Stirlinga.

Będziemy tworzyć permutację element po elemencie w zapisie kanonicznym. Weźmy \(\displaystyle{ n}\) niezależnych zmiennych zero-jedynkowych \(\displaystyle{ X_1...X_n}\). Niech \(\displaystyle{ X_i = 1}\) wtw gdy w \(\displaystyle{ i}\)-tym kroku zamykamy cykl (czyli wybierając \(\displaystyle{ i}\)-ty element trafiamy na taki, który przechodzi w pierwszy element aktualnego cyklu). \(\displaystyle{ Pr[X_i=1]=\frac{1}{n-(i-1)}}\), bo mamy do wyboru \(\displaystyle{ n-(i-1)}\) elementów i tylko jeden z nich przechodzi na pierwszy element w rozpatrywanym cyklu (gdy takiego elementu nie ma, czyli w poprzednim kroku zamknęliśmy cykl, to można liczyć ile jest możliwych par postaci \(\displaystyle{ <a,a>}\) wsród par \(\displaystyle{ <x,y>}\), gdzie \(\displaystyle{ x,y\in\{1...n-(i-1)\}}\)).

\(\displaystyle{ E[X]= \sum_{k=1}^{n}E[X_i] = \sum_{k=1}^{n}\frac{1}{n-(i-1)} = \sum_{k=1}^{n}\frac{1}{k} = H_n}\)

Można też rozpatrywać indykatory \(\displaystyle{ X_A}\), gdzie \(\displaystyle{ A}\) jest pewnym zbiorem, takie, że \(\displaystyle{ X_A = 1}\) wtw istnieje w permutacji cykl z elementów zbioru \(\displaystyle{ A}\). Wtedy \(\displaystyle{ E[X_A]=Pr[X_A = 1]=\frac{(|A|-1)! \cdot (n-|A|)!}{n!}}\), bo ustalamy jeden z elementów zbioru \(\displaystyle{ A}\) jako pierwszy element permutacji (nie ma znaczenia który, bo zawsze można uzyskać inny przez przesunięcie cykliczne zapisu permutacji), ustalamy permutację oraz pozostałe elementy oraz wybieramy takie permutacje ze zbioru wszystkich permutacji o mocy \(\displaystyle{ n!}\) .

\(\displaystyle{ E[X] = \sum_{k=1}^{n}\sum_{A \subseteq \{1..n\}, |A| = k}E[X_A] = \sum_{k=1}^{n} {n \choose k} \cdot \frac{(k-1)! \cdot (n-k)}{n!} = \sum_{k=1}^{n}\frac{1}{k} = H_n}\)