[Prawdopodobieństwo][Kombinatoryka] Pokrycie cyklowe

[Swistak]

Mamy sobie dany graf pełny skierowany o n wierzchołkach i wybieramy z niego losowe pokrycie cyklowe (oczywiście każde z równym prawdopodobieństwem). Jakie jest prawdopodobieństwo, że 1 i 2 będą w tym samym cyklu?

[xiikzodz]

Ukryta treść:    

O ile dobrze rozumiem pojęcia losujemy jedną z \(\displaystyle{ n!}\) permutacji zbioru \(\displaystyle{ n}\)-elementowego badamy, czy po jej rozkładzie na cykle rozłączne elementy \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) są w tym samym cyklu. Rozważając kolejno wszystkie możliwe długości cyklów zawierających \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) sumując możliwości i dzieląc przez \(\displaystyle{ n!}\) otrzymujemy więc wynik:

\(\displaystyle{ \sum_{i=2}^n\binom{n}{i}^{-1}}\)

Ta suma daje się inaczej wyrazić bo np.

\(\displaystyle{ \binom{n}{i}^{-1}=\frac{\Gamma(i+1)\Gamma(n-i+1)}{\Gamma(n+1)}=(n+1)\int_0^1x^i(1-x)^{n-i} \mbox{ d}x}\)

ale tu moja wiedza się kończy.

[Swistak]

Żeby nie zniechęcić innych do rozkminy powiem, że wynik da się przedstawić w istotnie ładniejszej postaci .

[xiikzodz]

Ukryta treść:    

Mój błąd, trzeba uważniej zliczać. Ale najpierw krótsze rozwiązanie bez liczenia, za to z pisaniem:

Istnieje wzajemnie jednoznaczne odwzorowanie pomiędzy zbiorem pokryć w których \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) są współcyklowe i zbiorem pokryć, w których nie są. Odwzorowanie to posyła cykl \(\displaystyle{ (1,v_1,\ldots,v_i, 2,w_1\ldots,w_j)}\) na dwa cykle \(\displaystyle{ (1,v_1,\ldots,v_i),(2,w_1\ldots,w_j)}\) i nie rusza pozostałych cykli w pokryciu. Stąd szukane prawdopodobieństwo wynosi \(\displaystyle{ \frac 12}\).

Znając wynik łatwiej poprawnie wszystko pozliczać poprzez powiązanie permutacji z pokryciami:

\(\displaystyle{ \sum_{i=2}^n\frac 1i\cdot \binom{n}{i}^{-1}\cdot\binom{n-2}{i-2}=\sum_{i=2}^n\frac{i-1}{n(n-1)}=\frac 12}\)

Wyrażenie po lewej stronie powstało tak: Wyrzucamy na moment \(\displaystyle{ 1,2}\) i z pozostałych \(\displaystyle{ n-2}\) wierzchołków wybieramy na \(\displaystyle{ \binom{n-2}{i-2}}\) sposobów \(\displaystyle{ i-2}\) wierzchołki. Wybranym \(\displaystyle{ i-2}\) wierzchołkom dodajemy \(\displaystyle{ 1,2}\) i zliczamy wszystkie możliwe cykle długości \(\displaystyle{ i}\), czyli \(\displaystyle{ \frac{i!}{i}}\). Pozostałe \(\displaystyle{ n-i}\) wierzchołków można cyklowo pokryć na \(\displaystyle{ (n-i)!}\) sposobów. Pozostaje zsumować po \(\displaystyle{ i=2,3,\ldots,n}\) i całość podzielić przez \(\displaystyle{ n!}\), liczbę wszystkich pokryć cyklowych grafu o \(\displaystyle{ n}\) wierzchołkach.

Przy okazji ciekawe zadanie: 246929.htm.

[Mruczek]

Tutaj chyba chodziło o klikę nieskierowaną. W treści zadania jest co prawda mowa o skierowanych, ale rozwiązanie jest dla nieskierowanego. W przypadku skierowanym wydaje się, że wynik będzie zależał od rodzaju grafu i chyba nie można go utożsamić bezpośrednio z permutacjami.

[Swistak]

No jakoś głupio to napisałem rzeczywiście. W każdym razie chodziło mi o taką interpretację jakiej użyła xiikzodz, innymi słowy losowa permutację.