Losowe statystyki permutacji

Statystyki permutacji losowych , takie jak struktura cykli permutacji losowych, mają fundamentalne znaczenie w analizie algorytmów , zwłaszcza algorytmów sortowania, które operują na permutacjach losowych. Załóżmy na przykład, że używamy quickselect (kuzyn quicksort ), aby wybrać losowy element losowej permutacji. Quickselect wykona częściowe sortowanie tablicy, ponieważ dzieli tablicę zgodnie z osią obrotu. Stąd permutacja będzie mniej nieuporządkowana po przeprowadzeniu szybkiego wyboru. Ilość pozostałego nieporządku można analizować za pomocą funkcji generujących. Te funkcje generujące zależą w fundamentalny sposób od funkcji generujących statystyki permutacji losowych. Dlatego tak ważne jest obliczenie tych funkcji generujących.

Artykuł o permutacjach losowych zawiera wprowadzenie do permutacji losowych.

Podstawowa relacja

Permutacje to zestawy oznakowanych cykli. Używając oznaczonego przypadku podstawowego twierdzenia Flajoleta – Sedgewicka i pisząc dla zbioru permutacji i dla singletonu, $displaystyle \ scriptstyle {\ mathcal {P}}}$$\$ zestaw, mamy

${\ Displaystyle \ nazwa operatora {ZESTAW} (\ nazwa operatora {CYC} ({\ mathcal {Z}})) = {\ mathcal {P}}.}$

Przekładając na wykładnicze funkcje generujące (EGF), mamy

${\ Displaystyle \ exp \ lewo (\ log {\ Frac {1} {1-z}} \ prawej) = {\ Frac {1} {1- z}}}$

gdzie wykorzystaliśmy fakt, że EGF kombinatorycznych gatunków permutacji (istnieje n ! permutacji n elementów) wynosi

${\ Displaystyle \ suma _ {n \ geq 0} {\ Frac {n!} {n!}} Z ^ {n} = {\ Frac {1} {1-z}}.}$

To jedno równanie pozwala wyprowadzić dużą liczbę statystyk permutacji. Po pierwsze, usuwając terminy z $,$ tj. exp , możemy ograniczyć liczbę cykli zawartych w permutacji, np. ograniczając EGF do ${\ displaystyle \ scriptstyle \ operatorname { SET} _{2}}$ otrzymujemy permutacje zawierające dwa cykle. Po drugie, zauważ, że EGF oznaczonych cykli, tj. ${\ Displaystyle \ scriptstyle \ operatorname {CYC} ({\ mathcal {Z}})}$ , Jest

$${\ Displaystyle \ suma _ {k \ geq 1} {\ Frac {(k-1)! Z ^ {k}} {k!}} = \ suma _{k\geq 1}{\frac {z^{k}}{k}}=\log {\frac {1}{1-z}}}$$

bo jest k ! / k oznaczonych cykli. Oznacza to, że usuwając wyrazy z tej funkcji generującej, możemy ograniczyć rozmiar cykli występujących w permutacji i otrzymać EGF permutacji zawierających tylko cykle o danym rozmiarze.

Zamiast usuwać i wybierać cykle, można również przypisywać różne wagi cyklom o różnych rozmiarach. Jeśli ${\ Displaystyle b: \ mathbb {N} \ rightarrow \ mathbb {R}}$ jest funkcją wagi, która zależy tylko od rozmiaru k cyklu i dla zwięzłości piszemy

${\ Displaystyle b (\ sigma) = \ suma _ {c \ in \ sigma} b (c)}$

definiując wartość b dla permutacji jako sumy jej wartości w cyklach, możemy oznaczyć cykle o długości k za pomocą u ^{b ( k )} i otrzymać funkcję generującą dwie zmienne σ {\ displaystyle $sigma}$

${\ Displaystyle g (z, u) = 1 + \ suma _ {n \ geq 1} \ lewo (\ suma _ {\ sigma \ w S_ {n}} u ^ {b (\ sigma)} \ prawej) { \frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{\frac {z^{k}}{k}}}$

Jest to „mieszana” funkcja generująca: jest to wykładnicza funkcja generująca w z i zwykła funkcja generująca w parametrze drugorzędnym u . Różniczkując i oceniając przy u = 1, mamy

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq 1}b(k){\frac {z^{k}}{k}}=\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}b (\sigma )\right){\frac {z^{n}}{n!}}}$

To jest funkcja generująca prawdopodobieństwo oczekiwania b . Innymi słowy, współczynnik $potęgowym$ jest oczekiwaną wartością b na permutacjach w , biorąc pod uwagę, że permutacja jest wybierana za pomocą $\ displaystyle S_ {n}}$ to samo prawdopodobieństwo ${\ Displaystyle 1/n!$ }

W tym artykule zastosowano operator ekstrakcji współczynników [ z ⁿ ], udokumentowany na stronie dotyczącej formalnych szeregów potęgowych .

Liczba permutacji będących inwolucjami

Główny artykuł: Numer telefonu (matematyka)

Inwolucja jest permutacją σ tak, że σ 2 ⁼ 1 przy złożeniu permutacji. Wynika z tego, że σ może zawierać tylko cykle o długości jeden lub dwa, tj. wykładnicza funkcja generująca g ( z ) tych permutacji to

${\ Displaystyle g (z) = \ exp \ lewo (z + {\ Frac {1} {2}} z ^ {2} \ prawo).}$

Daje to wyraźny wzór na całkowitą liczbę inwolucji wśród permutacji σ ∈ S _n : ${\ displaystyle I (n)}$

${\ Displaystyle I (n) = n! [z ^ {n}] g (z) = n! \ suma _ {a + 2b = n} {\ Frac {1} {a! \; 2 ^ {b} \;b!}}=n!\sum _{b=0}^{\lfloor n/2\rfloor }{\frac {1}{(n-2b)!\;2^{b}\;b !}}.}$

Dzielenie przez n ! daje prawdopodobieństwo, że losowa permutacja jest inwolucją. Numery te są znane jako numery telefonów .

Liczba permutacji, które są m- tym pierwiastkiem jedności

To uogólnia pojęcie inwolucji. Pierwiastek m - ty z jedności jest permutacją σ taką, że σ ^m = 1 przy złożeniu permutacji. Teraz za każdym razem, gdy stosujemy σ, przesuwamy się równolegle o jeden krok wzdłuż wszystkich jego cykli. Cykl o długości d zastosowany d razy daje permutację identyczności na d elementach ( d stałych punktach), a d jest najmniejszą wartością, która to robi. Stąd m musi być wielokrotnością wszystkich rozmiarów cykli d , tj. jedynymi możliwymi cyklami są te, których długość d jest dzielnikiem m . Wynika z tego, że EGF g ( x ) tych permutacji wynosi

${\ Displaystyle g (z) = \ exp \ lewo (\ suma _ {d \ mid m} {\ Frac {z ^ {d}} {d}} \ prawej).}$

Kiedy m = p , gdzie p jest liczbą pierwszą, upraszcza się to do

${\ Displaystyle n! [z ^ {n}] g (z) = n! \ suma _ {a + pb = n} {\ frac {1} {a! \; p ^ {b} \; b!} }=n!\sum _{b=0}^{\lfloor n/p\rfloor}{\frac {1}{(n-pb)!\;p^{b}\;b!}}.}$

Liczba permutacji rzędu dokładnie k

Można to zrobić za pomocą inwersji Möbiusa . Pracując z tą samą koncepcją, co w poprzednim wpisie, zauważamy, że gatunek kombinatoryczny permutacji, których kolejność dzieli k , jest określony przez ${\ displaystyle {\ mathcal {Q}}}$

${\ Displaystyle {\ mathcal {Q}} = \ nazwa operatora {ZESTAW} \ lewo (\ suma _ {d \ mid k} \ nazwa operatora {CYC} _ {= d} ({\ mathcal {Z}}) \ po prawej) .}$

Przekładając na wykładnicze funkcje generujące otrzymujemy EGF permutacji, których rząd dzieli k , czyli

${\ Displaystyle Q_ {k} (z) = \ exp \ lewo (\ suma _ {d \ mid k} {\ Frac {z ^ {d}} {d}} \ prawej).}$

Teraz możemy użyć tej funkcji generującej, aby dokładnie policzyć permutacje rzędu k . Niech ${\ Displaystyle p_ {n, d}}$ będzie liczbą permutacji na n , którego kolejność jest dokładnie re i ${\ Displaystyle q_ {n, k}}$ liczbą permutacji na n permutacji liczyć, którego rząd dzieli k . Następnie mamy

${\ Displaystyle \ suma _ {d | k} p_ {n, d} = q_ {n, k}.}$

Wynika to z inwersji Möbiusa

${\ Displaystyle \ suma _ {d | k} q_ {n, d} \ razy \ mu (k / d) = p_ {n, k}.}$

Dlatego mamy EFG

${\ Displaystyle Q (z) = \ suma _ {d \ mid k} \ mu (k / d) \ razy Q_ {d} (z) = \ suma _ {d \ mid k} \ mu (k / d) \exp \left(\sum _{m\mid d}{\frac {z^{m}}{m}}\right).}$

Pożądana liczba jest następnie podana przez

${\ displaystyle n! [z ^ {n}] Q (z).}$

Ta formuła daje np. dla k = 6 EGF

${\ Displaystyle Q (z) = {\ rm {e}} ^ {z} - {\ rm {e}} ^ {z + 1/2 \, z ^ {2}} - {\ rm {e}} ^{z+1/3\,z^{3}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1 /6\,z^{6}}}$

z ciągiem wartości zaczynającym się od n = 5

${\ Displaystyle 202401470106408316058 4640,4496030,42658440,371762820,3594871280,\ldkropki }$ (sekwencja A061121 w OEIS )

Dla k = 8 otrzymujemy EFG

${\ Displaystyle Q (z) = - {\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}+{\rm {e}}^{z+1/2\, z^{2}+1/4\,z^{4}+1/8\,z^{8}}}$

z ciągiem wartości zaczynającym się od n = 8

${\ Displaystyle 5040,45360,453600,3326400,39916 800,363242880,3874590720,34767532800,\ldots}$ (sekwencja A061122 w OEIS )

Ostatecznie dla k = 12 otrzymujemy EFG

${\ Displaystyle Q (z) = {\ rm {e}} ^ {z + 1 / 2\,z^{2}}-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}-{\rm {e} }^{z+1/2\,z^{2}+1/3\,{z}^{3}+1/6\,z^{6}}+{\rm {e}}^{ z+1/2\,z^{2}+1/3\,z^{3}+1/4\,z^{4}+1/6\,z^{6}+1/12\ ,z^{12}}}$

z ciągiem wartości zaczynającym się od n = 7

$,\ldots}$ (sekwencja A061125 w OEIS )

Liczba permutacji, które są zaburzeniami

Główny artykuł: Obłąkanie

, że na przyjęciu jest n osób, z których każda przyniosła parasol. Na koniec imprezy wszyscy wybierają parasol ze stosu parasoli i liści. Jakie jest prawdopodobieństwo, że nikt nie wyszedł z własnym parasolem? Ten problem jest równoważny z liczeniem permutacji bez punktów stałych (zwanych derangementami ), a zatem EGF, w którym odejmujemy punkty stałe (cykle o długości 1) poprzez usunięcie składnika z z podstawowej relacji to

${\ Displaystyle \ exp \ lewo (- z + \ suma _ {k \ geq 1} {\ Frac {z ^ {k}} {k}} \ prawo) = {\ frac {e ^ {- z}} {1 -z}}.}$

Mnożenie przez ${\ Displaystyle 1/(1-z)}$ sumuje współczynniki mi $\ Displaystyle e ^ {- z}}$ , więc ${\ Displaystyle D (n) }$ , łączna liczba zaburzeń, jest dana wzorem:

${\ Displaystyle D (n) = n! \ suma _ {k = 0} ^ {n} {\ Frac {(-1) ^ {k}} {k!}} \; \ około \; {\ Frac { n!}{e}}.}$

Stąd istnieje około ${\ displaystyle n!/e}$ zaburzenia i prawdopodobieństwo, że losowa permutacja jest zaburzeniem, wynosi ${\ Displaystyle 1 / e.}$

Wynik ten można również udowodnić przez włączenie-wykluczenie . Za ${\ Displaystyle A_ {p}}$ gdzie $równoważnik p \ równoważnik n \ koniec {macierz}}}$ do oznaczenia zestawu permutacji, które naprawiają p , mamy

${\ Displaystyle \ lewo | \ bigcup _ {p} A_ {p} \ prawo | = \ suma _ {p} \ lewo | A_ {p} \ prawo | \; - \; \ suma _ {p <q} \ left|A_{p}\cap A_{q}\right|\;+\;\suma _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\ prawo|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.}$

Ta formuła zlicza liczbę permutacji, które mają co najmniej jeden punkt stały. Liczebności są następujące:

${\ Displaystyle \ lewo | A_ {p} \ prawo | = (n-1)! \;, \; \; \ lewo | A_ {p} \ czapka A_ {q} \ prawo | = (n-2)! \;,\;\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=(n-3)!\;,\;\ldots }$

Stąd liczba permutacji bez punktu stałego wynosi

${\ Displaystyle n! \; \; - \; \; {n \ wybierz 1} (n-1)! \; \; + \; \; {n \ wybierz 2} (n-2)! \; \ ;-\;\;{n \wybierz 3}(n-3)!\;\;+\;\;\cdots \;\;\pm \;\;{n \wybierz n}(nn)!}$

Lub

${\ Displaystyle n! \ lewo (1- {\ Frac {1} {1!}} + {\ Frac {1} {2!}} - {\ Frac {1} {3!}} + \ cdots \ pm {\frac {1}{n!}}\right)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

i mamy roszczenie.

Istnieje uogólnienie tych liczb, które jest znane jako $}$ rencontres tj. liczba permutacji zawierających m stała $\ Displaystyle D (n, m$ zwrotnica. Odpowiedni EFG uzyskuje się poprzez oznaczenie cykli o rozmiarze jeden zmienną u , tj. wybranie b ( k ) równego jeden dla ${\ displaystyle k = 1}$ i zero w przeciwnym razie, co daje funkcję generującą zbioru permutacji według liczby stałych punktów: ${\ Displaystyle g (z, u)}$

${\ Displaystyle g (z, u) = \ exp \ lewo (- z + uz + \ suma _ {k \ geq 1} {\ Frac {z ^ {k}}} {k}} \ prawej) = {\ frac { e^{-z}}{1-z}}e^{uz}.}$

Wynika, że

${\ Displaystyle [u ^ {m}] g (z, u) = {\ Frac {e ^ {-z}} {1-z}} {\ Frac {z ^ {m}} {m!}}}$

i stąd

${\ Displaystyle D (n, m) = n! [z ^ {n}] [u ^ {m}] g (z, u) = {\ Frac {n!} {m!}} [z ^ {nm }] {\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{nm}{\frac {(- 1)^{k}}{k!}}.}$

To od razu implikuje

${\ Displaystyle D (n, m) = {n \ wybierz m} D (nm, 0) \; \; {\ tekst {i}} \; \; {\ Frac {D (n, m)}} {n !}}\około {\frac {e^{-1}}{m!}}}$

dla n dużych, m stałych.

Kolejność losowej permutacji

Jeśli P jest permutacją, rząd P jest najmniejszą dodatnią liczbą całkowitą n , dla której permutacją tożsamości jest P $\ displaystyle P ^ {n}} .$ Jest to najmniejsza wspólna wielokrotność długości cykli P .

Twierdzenie Goha i Schmutza stwierdza, że ​​jeśli jest oczekiwanym rzędem losowej permutacji o rozmiarze n , to ${\ displaystyle \ mu _ {n}}$

${\ Displaystyle \ log \ mu _ {n} \ sim c {\ sqrt {\ Frac {n} {\ log n}}}}$

jest stała c

${\ Displaystyle 2 {\ sqrt {2 \ int _ {0} ^ {\ infty} \ log \ log \ lewo ({\ Frac {e}{1-e^{-t}}}\right)dt}}\około 1,1178641511899}$

Zaburzenia zawierające parzystą i nieparzystą liczbę cykli

$n$${1}(n)}$ aby obliczyć liczbę zaburzeń zawierających parzystą liczbę cykli i liczbę $displaystyle$ zawierający nieparzystą liczbę cykli. Aby to zrobić musimy zaznaczyć wszystkie cykle i odjąć punkty stałe, dając

${\ Displaystyle g (z, u) = \ exp \ lewo (-uz + u \ log {\ Frac {1} {1-z}} \ prawej) = \ exp (-uz) \ lewo ({\ frac { 1}{1-z}}\prawo)^{u}.}$

$}$ pokazuje, że EGF jest podane przez $n )$

${\ Displaystyle q (z) = {\ Frac {1} {2}} \ razy g (z, -1) + {\ Frac {1} {2}} \ razy g (z, 1) = {\ frac {1}{2}}\exp(-z){\frac {1}{1-z}}+{\frac {1}{2}}\exp(z)(1-z).}$

Mamy zatem

${\ Displaystyle D_ {0} (n) = n! [z ^ {n}] q (z) = {\ Frac {1} {2}} n! \ suma _ {k = 0} ^ {n} \frac {(-1)^{k}}{k!}}+{\frac {1}{2}}n!{\frac {1}{n!}}-{\frac {1}{2 }}n!{\frac {1}{(n-1)!}}}$

który jest

${\ Displaystyle {\ Frac {1} {2}} n! \ suma _ {k = 0} ^ {n} {\ Frac {(-1) ^ {k}} {k!}} + {\ Frac { 1}{2}}(1-n)\sim {\frac {1}{2e}}n!+{\frac {1}{2}}(1-n).}$

Odejmując ${\ Displaystyle D_ {0} (n)}$ od ${\ Displaystyle D (n)}$ , znajdujemy

${\ Displaystyle D_ {1} (n) = {\ Frac {1} {2}} n! \ suma _ {k = 0} ^ {n} {\ Frac {(-1) ^ {k}} {k !}}-{\frac {1}{2}}(1-n).}$

Różnica tych dwóch ( i $\ Displaystyle$$)}$ ) jest $displaystyle n-1 .}$

Sto więźniów

Główny artykuł: problem 100 więźniów

Naczelnik więzienia chce zrobić miejsce w swoim więzieniu i rozważa uwolnienie stu więźniów, a tym samym uwolnienie stu cel. Dlatego gromadzi stu więźniów i prosi ich o rozegranie następującej gry: ustawia w rzędzie sto urn, z których każda zawiera imię jednego więźnia, przy czym imię każdego więźnia występuje dokładnie raz. Gra przebiega następująco: każdy więzień może zajrzeć do wnętrza pięćdziesięciu urn. Jeśli nie znajdzie swojego imienia w jednej z pięćdziesięciu urn, wszyscy więźniowie zostaną natychmiast straceni, w przeciwnym razie gra toczy się dalej. Więźniowie mają kilka chwil na podjęcie decyzji o strategii, wiedząc, że po rozpoczęciu gry nie będą mogli się ze sobą komunikować, w żaden sposób oznaczać urn ani przenosić znajdujących się w nich urn lub imion. Wybierając losowo urny, ich szanse przeżycia są bliskie zeru, ale istnieje strategia dająca im 30% szans na przeżycie, przy założeniu, że imiona są przypisywane urnom losowo – co to jest?

Przede wszystkim prawdopodobieństwo przeżycia przy losowych wyborach wynosi

${\ Displaystyle \ lewo ({\ Frac {99 \ wybierz 49} {100 \ wybierz 50}} \ prawej) ^ {100} = {\ Frac { 1}{2^{100}}},}$

więc zdecydowanie nie jest to praktyczna strategia.

Strategia 30% przetrwania polega na uznaniu zawartości urn za permutację więźniów i cykle przechodzenia. Aby notacja była prosta, przypisz każdemu więźniowi numer, na przykład sortując ich nazwiska alfabetycznie. Następnie można uznać, że urny zawierają raczej liczby niż nazwiska. Teraz wyraźnie zawartość urn definiuje permutację. Pierwszy więzień otwiera pierwszą urnę. Jeśli znajdzie swoje imię, skończył i przeżyje. W przeciwnym razie otwiera urnę z numerem, który znalazł w pierwszej urnie. Proces się powtarza: więzień otwiera urnę i przeżywa, jeśli znajdzie swoje nazwisko, w przeciwnym razie otwiera urnę z numerem właśnie odzyskanym, do limitu pięćdziesięciu urn. Drugi więzień zaczyna z urną numer dwa, trzeci z urną numer trzy i tak dalej. Ta strategia jest dokładnie równoważna przechodzeniu przez cykle permutacji reprezentowanej przez urny. Każdy więzień zaczyna od urny z jego numerem i kontynuuje swój cykl aż do granicy pięćdziesięciu urn. Numer urny, który zawiera jego numer, jest przedobrazem tego numeru pod permutacją. Dlatego więźniowie przeżywają, jeśli wszystkie cykle permutacji zawierają co najwyżej pięćdziesiąt elementów. Musimy pokazać, że prawdopodobieństwo to wynosi co najmniej 30%.

Zauważ, że zakłada to, że naczelnik losowo wybiera permutację; jeśli naczelnik przewidzi tę strategię, może po prostu wybrać permutację z cyklem o długości 51. Aby temu zaradzić, więźniowie mogą z góry uzgodnić losową permutację swoich nazwisk.

Rozważamy ogólny $otwierania$ i $.$ Najpierw obliczamy prawdopodobieństwo komplementarności, tj. że istnieje cykl składający się z więcej $niż$ . Mając to na uwadze, przedstawiamy

${\ Displaystyle g (z, u) = \ exp \ lewo (z + {\ frac {z ^ {2}}} {2}} + {\ frac {z ^ {3}} {3}} + \ cdots + u {\frac {z^{n+1}}{n+1}}+u{\frac {z^{n+2}}{n+2}}+\cdots \right)}$

Lub

${\ Displaystyle {\ Frac {1} {1-z}} \ exp \left((u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\ cdots \prawo)\prawo),}$

tak, że pożądane prawdopodobieństwo jest

${\ Displaystyle [z ^ {2n}] [u] g (z, u)}$

ponieważ cykl więcej niż $będzie$ z konieczności unikalny. Korzystając z faktu, że ${\ Displaystyle 2 (n + 1)> 2n}$ , stwierdzamy, że

$\ Displaystyle [z ^ {2n}] [u] g (z, u) = [z ^ {2n} [u] {\ Frac {1} {1-z}} \ lewo (1+ (u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right )\Prawidłowy),}$

co daje

${\ Displaystyle [z ^ {2n}] [u] g (z, u) = [z ^ {2n}] {\ Frac {1} {1-z}} \ lewo ({\ Frac {z ^ {n +1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)=\sum _{k=n+1}^{2n} {\frac {1}{k}}=H_{2n}-H_{n}.}$

Wreszcie, używając estymatora całkowego, takiego jak sumowanie Eulera-Maclaurina lub asymptotyczne rozwinięcie n- tej liczby harmonicznej , otrzymujemy

${\ Displaystyle H_ {2n} -H_ {n} \ sim \log 2-{\frac {1}{4n}}+{\frac {1}{16n^{2}}}-{\frac {1}{128n^{4}}}+{\frac { 1}{256n^{6}}}-{\frac {17}{4096n^{8}}}+\cdots ,}$

aby

${\ Displaystyle [z ^ {2n}] [u] g (z, u) <\ log 2 \ quad {\ mbox {i}} \ quad 1- [z ^ {2n}] [u] g (z, u)>1-\log 2=0,30685281,}$

lub co najmniej 30%, jak twierdzono.

Powiązanym wynikiem jest to, że asymptotycznie oczekiwana długość najdłuższego cyklu wynosi λn, gdzie λ jest stałą Golomba-Dickmana , około 0,62.

Ten przykład pochodzi od Anny Gál i Petera Bro Miltersena; więcej informacji można znaleźć w artykule Petera Winklera oraz w dyskusji na stronie Les-Mathematiques.net . Zapoznaj się z odniesieniami do 100 więźniów , aby uzyskać linki do tych odniesień.

$większej$$zauważ$ , że permutacja elementów zawiera co najwyżej jeden cykl o długości ściśle . Zatem, jeśli oznaczymy

${\ Displaystyle p_ {k} = \ Pr [{\ mbox {jest cykl o długości}} k],}$

Następnie

${\ Displaystyle \ Pr [{\ mbox {istnieje cykl długości}}> n] = \ suma _ {k = n + 1} ^ {2n} p_ {k}.}$

Dla ${\ displaystyle k> n}$ liczba permutacji, które zawierają dokładnie cykl o długości k > n ${\ displaystyle k}$ wynosi

${\ Displaystyle {{2n} \ wybierz k} \ cdot {\ Frac {k!} {k}} \ cdot (2n-k)!.}$

Wyjaśnienie: ${\ Displaystyle {{2n} \ wybierz k}}$ to liczba sposobów wyboru elementów składających się na cykl; ${\ displaystyle k}$${\ displaystyle {\ frac {k!} {k}}}$ to liczba sposobów ułożenia elementów w cyklu ${\ displaystyle k} ;$ i ${\ Displaystyle (2n-k)!}$ to liczba sposobów permutacji pozostałych elementów. Nie ma tu podwójnego liczenia ${\ displaystyle k> n$ ponieważ istnieje co najwyżej jeden cykl o długości, gdy $}$ . Zatem,

${\ Displaystyle p_ {k} = {\ Frac {{{2n} \ wybierz k} \ cdot {\ Frac {k!} {k}} \ cdot (2n-k)!} {(2n)!}} = {\frac {1}{k}}.}$

Wnioskujemy, że

${\ Displaystyle \ Pr [{\ mbox {istnieje cykl długości}}> n] = \ suma _ {k = n + 1} ^ {2n} {\ Frac {1} {k}} = H_ {2n }-H_{n}.}$

Wariacja na temat problemu 100 więźniów (klucze i pudełka)

Istnieje ściśle powiązany problem, który całkiem dobrze pasuje do przedstawionej tutaj metody. Załóżmy, że masz n zamówionych pudełek. Każde pudełko zawiera klucz do innego pudełka lub ewentualnie siebie, dając permutację kluczy. Możesz wybrać k z tych n skrzynek jednocześnie i otworzyć je jednocześnie, uzyskując dostęp do k kluczy. Jakie jest prawdopodobieństwo, że za pomocą tych kluczy możesz otworzyć wszystkie n skrzynek, gdzie użyjesz znalezionego klucza, aby otworzyć skrzynkę, do której należy, i powtórzyć.

Matematyczne sformułowanie tego problemu jest następujące: wybierz losową permutację na n elementach i k wartościach z zakresu od 1 do n , również losowo, nazwij te znaki. Jakie jest prawdopodobieństwo, że w każdym cyklu permutacji jest co najmniej jeden znak? Twierdzenie jest takie, że prawdopodobieństwo to wynosi k/n .

Gatunek permutacji według cykli z pewnym niepustym podzbiorem każdego zaznaczonego cyklu ma specyfikację ${\ displaystyle {\ mathcal {Q}}}$

${\ Displaystyle {\ mathcal {Q}} = \ nazwa operatora {ZESTAW} \ lewo (\ suma _ {q \ geq 1} \ nazwa operatora {CYC} _ {= q} ({\ mathcal {Z}}) \ razy \ suma _{p=1}^{q}{q \wybierz p}{\mathcal {U}}^{p}\prawo).}$

Indeks w sumie wewnętrznej zaczyna się od jedynki, ponieważ w każdym cyklu musimy mieć co najmniej jeden znak.

Przekładając specyfikację na funkcje generujące, otrzymujemy dwuwymiarową funkcję generującą

${\ Displaystyle G (z, u) = \ exp \ lewo (\ suma _ {q \ geq 1} {\ Frac {z ^ {q}}} {q}} \ suma _ {p = 1} ^ {q} {q \wybierz p}u^{p}\right).}$

To upraszcza do

${\ Displaystyle \ exp \ lewo (\ suma _ {q \ geq 1} {\ Frac {z ^ {q }}{q}}(u+1)^{q}-\sum _{q\geq 1}{\frac {z^{q}}{q}}\right)}$

Lub

${\ Displaystyle \ exp \ lewo (\ log {\ Frac {1} {1- (u + 1) z}} - \ log {\ Frac {1} {1-z}} \ prawej) = {\ frac { 1-z}{1-(u+1)z}}.}$

Aby wyodrębnić współczynniki z tego przepisz tak

${\ Displaystyle (1-z) \ suma _ {q \ geq 0} (u + 1) ^ {q} z ^ {q}.}$

Teraz z tego wynika

${\ Displaystyle [z ^ {n}] G (z, u) = (u + 1) ^ { n}-(u+1)^{n-1}}$

i stąd

${\ Displaystyle [u ^ {k} [z ^ {n}] G (z, u) = {n \ wybierz k} - {n-1 \ wybierz k}.}$

Podziel przez ${\ Displaystyle {n \ wybierz k}}$ , aby uzyskać

${\ Displaystyle 1- {\ Frac {(n-1)!} {k! (n-1-k)!}}} {\ Frac {k! (nk)!} {n!}} = 1- {\ frac {nk}{n}}={\frac {k}{n}}.}$

Nie musimy dzielić przez n! ponieważ jest wykładniczy w z . sol $\ Displaystyle G (z, u)}$

Liczba permutacji zawierających m cykli

Zastosowanie podstawowego twierdzenia Flajoleta – Sedgewicka , tj. twierdzenia o wyliczeniu z etykietą z , do zbioru ${\ Displaystyle G = S_ {m}}$

${\ Displaystyle \ nazwa operatora {ZESTAW} _ {= m} (\ nazwa operatora {CYC} ({\ mathcal {Z}}))}$

otrzymujemy funkcję generującą

${\ Displaystyle g_ {m} (z) = {\ Frac {1} {1} {| S_ {m} |}} \ lewo (\ log {\ Frac {1} {1-z}} \ prawej) ^ {m} ={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m}.}$

Termin

${\ Displaystyle (-1) ^ {n + m} n! \; [z ^ {n}] g_ {m} (z) = s ( n,m)}$

daje podpisane liczby Stirlinga pierwszego rodzaju i jest EGF niepodpisanych liczb Stirlinga pierwszego rodzaju, tj ${\ displaystyle g_ {m} (z)}$

${\ Displaystyle n! [z ^ {n}] g_ {m} (z) = \ lewo [{\ rozpocząć {macierz} n \\ m \ koniec {macierz}} \ prawo].}$

Możemy obliczyć OGF podpisanych liczb Stirlinga dla n ustalonego, tj

${\ Displaystyle s_ {n} (w) = \ suma _ {m = 0} ^ {n} s (n, m) w ^ {m}.}$

Zacząć od

${\ Displaystyle g_ {m} (z) = \ suma _ {n \ geq m} {\ Frac {(-1) ^ {n + m}} {n!}} s ( n,m)z^{n}}$

co daje

${\ Displaystyle (-1) ^ {m} g_ {m} (z) w ^ {m} = \ suma _ {n \ geq m} {\ Frac {(-1) ^ {n}} {n!} }s(n,m)w^{m}z^{n}.}$

Sumując to, otrzymujemy

${\ Displaystyle \ suma _ {m \ geq 0} (-1) ^ {m} g_ {m} (z) w ^ {m} = \ suma _ {m \ geq 0} \ suma _ {n \ geq m }{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}=\sum _{n\geq 0}{\frac {( -1)^{n}}{n!}}z^{n}\suma _{m=0}^{n}s(n,m)w^{m}.}$

Korzystając ze wzoru zawierającego logarytm dla $Displaystyle g_ {m} (z$$\$ , definicję po prawej stronie, m i twierdzenie dwumianowe , otrzymujemy

${\ Displaystyle (1-z) ^ {w} = \ suma _ {n \ geq 0} {w \ wybierz n} (-1) ^ {n} z ^ {n} = \ suma _ {n \ geq 0 }{\frac {(-1)^{n}}{n!}}s_{n}(w)z^{n}.}$

$Porównując$ współczynniki i definicji współczynnika dwumianowego , końcu mamy

${\ Displaystyle s_ {n} (w) = w \; (w- 1)\;(w-2)\;\cdots \;(w-(n-1))=(w)_{n},}$

silnia opadająca . Obliczanie OGF liczb Stirlinga bez znaku pierwszego rodzaju działa w podobny sposób.

Oczekiwana liczba cykli danego rozmiaru m

W tym zadaniu używamy dwuwymiarowej funkcji generującej g ( z , u ), jak opisano we wstępie. Wartość b dla cyklu o rozmiarze innym niż m wynosi zero, a jeden dla cyklu o rozmiarze m . Mamy

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) { \Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}} ={\frac {1}{1-z}}{\frac {z^{m}}{m}}}$

Lub

${\ Displaystyle {\ Frac {1} {m}} z ^ {m} \; + \; {\ Frac {1} m}}z^{m+1}\;+\;{\frac {1}{m}}z^{m+2}\;+\;\cdots }$

Oznacza to, że oczekiwana liczba cykli o rozmiarze m w permutacji o długości n mniejszej niż m wynosi zero (oczywiście). Losowa permutacja o długości co najmniej m zawiera średnio 1/ m cykli o długości m . W szczególności losowa permutacja zawiera około jednego punktu stałego.

OGF oczekiwanej liczby cykli o długości mniejszej lub równej m wynosi zatem

${\ Displaystyle {\ Frac {1} {1-z} }\sum _{k=1}^{m}{\frac {z^{k}}{k}}{\mbox{ i }}[z^{n}]{\frac {1}{1- z}}\suma _{k=1}^{m}{\frac {z^{k}}{k}}=H_{m}{\mbox{ dla }}n\geq m}$

gdzie Hm jest _m - tą liczbą harmoniczną . Stąd oczekiwana liczba cykli o długości co najwyżej m w losowej permutacji wynosi około ln m .

Momenty punktów stałych

Mieszany GF ${\ Displaystyle g (z, u)}$ permutacji według liczby stałych punktów wynosi sol

${\ Displaystyle g (z, u) = \ exp \ lewo (- z + uz + \ log {\ Frac {1} {1-z}} \ prawej) = {\ Frac {1} {1-z}} \ exp(-z+uz).}$

Niech zmienną losową X będzie liczba stałych punktów losowej permutacji. Używając liczb Stirlinga drugiego rodzaju , mamy następujący wzór na m- ty moment X :

${\ Displaystyle E (X ^ {m}) = E\left(\suma _{k=0}^{m}\left\{{\begin{macierz}m\\k\end{macierz}}\right\}(X)_{k}\right) =\suma _{k=0}^{m}\left\{{\begin{macierz}m\\k\end{macierz}}\right\}E((X)_{k}),}$

gdzie ${\ Displaystyle (X) _ {k}}$ jest silnią opadającą . Używając mamy ${\ Displaystyle g (z, u)}$

${\ Displaystyle E ((X) _ {k}) = [z ^ {n}] \ lewo ({\ Frac {d} {du}} \ prawej) ^ {k} g(z,u){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}}\exp(-z+uz){ \Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}},}$

czyli zero, gdy ${\ displaystyle k> n}$ i jeden w przeciwnym razie. Stąd tylko terminy, których suma składa się na ${\ displaystyle k <= n} .$ To daje

${\ Displaystyle E (X ^ {m}) = \ suma _ {k = 0} ^ {n} \ lewo \ {{\ początek {macierz} m \\ k \ koniec {macierz}} \ prawo \}.}$

Oczekiwana liczba stałych punktów w losowej permutacji podniesiona do pewnej potęgi k

$,$$.$ wybierasz losową permutację $podnosisz$ ją do pewnej potęgi dodatnią liczbą całkowitą i pytasz o oczekiwaną liczbę stałych punktów w wyniku Oznacz tę wartość przez ${\ Displaystyle E [F_ {k}]}$ .

Dla każdego dzielnika k $\ displaystyle k$${\ displaystyle k.}$$cykl$ długości dzieli się na $podniesieniu$$do$ potęgi Dlatego musimy oznaczyć te cykle ${\ Displaystyle u ^ {d}.}$ Aby to zilustrować, rozważ ${\ Displaystyle E [F_ {6}].}$

dostajemy

${\ Displaystyle g (z, u) = \ exp \ lewo (uz-z + u ^ {2} {\ frac {z ^ {2}} {2}} - {\ frac {z ^ {2}} 2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^ {6}}{6}}-{\frac {z^{6}}{6}}+\log {\frac {1}{1-z}}\right)}$

który jest

${\ Displaystyle {\ Frac {1} {1-z}} \ exp \ lewo (uz-z + u ^ {2} {\ Frac {Z ^ {2}} {2}} - {\ Frac {z ^ {2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{ \frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right).}$

Po raz kolejny kontynuując, jak opisano we wstępie, znajdujemy

${\ Displaystyle \ lewo. {\ Frac {\ częściowe} {\ częściowe u}} g (z, u) \ prawo | _ {u = 1} = \ lewo. {\ Frac {z + z ^ { 2}+z^{3}+z^{6}}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}- {\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+ u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right)\right|_{u=1}}$

który jest

${\ Displaystyle {\ Frac {z + z ^ {2} + z ^ {3} + z ^ {6}} {1-z}}.}$

Wniosek jest taki, że $n$$\ geq 6} i$ 6 cztery stałe

Ogólna procedura jest

${\ Displaystyle g (z, u) = \ exp \ lewo (\ suma _ {d \ mid k} \ lewo (u ^ {d} {\ Frac {z ^ {d}}} {d}} - {\ frac {z^{d}}{d}}\right)+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp \left( \sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\ Prawidłowy).}$

Po raz kolejny kontynuując jak poprzednio, stwierdzamy

${\ Displaystyle \ lewo. {\ Frac {\ częściowe} {\ częściowe u}} g (z, u) \ prawo | _ {u = 1} = \ lewo. {\ Frac {\ suma _ {d \ mid k }z^{d}}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}- {\frac {z^{d}}{d}}\right)\right)\right|_{u=1}={\frac {\sum _{d\mid k}z^{d}}{ 1-z}}.}$

Pokazaliśmy, że wartość ${\ displaystyle k) mi [$ równa ( liczba dzielników k $Displaystyle$$E [$ ) jak tylko ${\ Displaystyle n \ geq k.}$ Zaczyna się od ${\ Displaystyle 1}$ dla ${\ Displaystyle n = 1}$ i zwiększa się o jeden za każdym razem ${\ displaystyle n}$ uderza w dzielnik $\ displaystyle k}$${$ włącznie .

Oczekiwana liczba cykli dowolnej długości losowej permutacji

Konstruujemy dwuwymiarową funkcję generującą ${\ Displaystyle g (z, u)}$ za pomocą $\ Displaystyle b (k)}$ { , gdzie ${\ Displaystyle b (k)}$ jeden dla wszystkich cykli (każdy cykl dodaje jeden do całkowitej liczby cykli).

Zauważ, że ma formę zamkniętą. ${\ Displaystyle g (z, u)}$

${\ Displaystyle g (z, u) = \ lewo ({\ Frac {1} {1-z}} \ prawej) ^ {u}}$

i generuje niepodpisane liczby Stirlinga pierwszego rodzaju .

Mamy

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\sum _{k\geq 1}{\frac {z ^{k}}{k}}={\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

Stąd oczekiwana liczba cykli to $displaystyle$ harmoniczna lub o $log n}$ .

Liczba permutacji z cyklem o długości większej niż n /2

(Zauważ, że sekcja stu więźniów zawiera dokładnie ten sam problem z bardzo podobnymi obliczeniami, a także prostszy elementarny dowód).

${$ od wykładniczej funkcji generującej tym razem z klasy permutacji według rozmiaru, w którym cykle $}}}$ o długości większej niż ${\ displaystyle n/2}$ są oznaczone zmienną: ${\ displaystyle u}$ :

${\ Displaystyle g (z, u) = \ exp \ lewo (u \ suma _ {k> \ lfloor {\ Frac {n} {2}} \ rfloor} ^ {\ infty} {\ frac {z ^ {k }}{k}}+\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor}{\frac {z^{k}}{k}}\right). }$

Może istnieć tylko jeden cykl o długości większej niż n $\ displaystyle {\ frac {n} {2}}}$

${\ Displaystyle n! [uz ^ {n}] g (z, u) = n! [z ^ {n}] \ exp \ lewo (\ suma _ {k = 1} ^ {\ lfloor {\ frac {n }{2}}\rfloor }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

Lub

${\ Displaystyle n! [z ^ {n}] \ exp \ lewo (\ log {\ Frac {1} {1-z}} - \ suma _ {k> \ lfloor {\ frac {n} {2}} \rfloor }^{\infty}{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor}^{\infty }{\frac {z^{k}}{k}}}$

który jest

${\ Displaystyle n! [z ^ {n}] {\ Frac {1} {1-z}} \ exp \ lewo (- \ suma _ { k>\lfloor {\frac {n}{2}}\rfloor}^{\infty}{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor}^{\infty}{\frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z} }\sum _{m=0}^{\infty}{\frac {(-1)^{m}}{m!}}\left(\sum _{k>\lfloor {\frac {n}{ 2}}\rfloor }^{\infty}{\frac {z^{k}}{k}}\right)^{m+1}}$

Wykładnik $⌊$${$ podniesionym do potęgi $rfloor}$ większy niż $\ Displaystyle \ lfloor {\ Frac {n} {2}$${\ Displaystyle [z ^ {n}].}$ a zatem żadna wartość dla nie $z$ się do

Wynika z tego, że odpowiedź brzmi

${\ Displaystyle n! [z ^ {n}] {\ Frac {1} {1-z}} \ suma _ {k> \ lfloor {\ Frac {n} {2}} \ rfloor} ^ {\ infty} {\frac {z^{k}}{k}}=n!\sum _{k=\lfloor {\frac {n}{2}}\rfloor +1}^{n}{\frac {1} {k}}.}$

Suma ma alternatywną reprezentację, którą można spotkać np. w OEIS OEIS : A024167 .

${\ Displaystyle \ suma _ {k = 1} ^ {n} {\ Frac {1} {k}} - \ suma _ {k = 1} ^ {\ lfloor { \frac {n}{2}}\rfloor}{\frac {1}{k}}=\sum _{k=1}^{n}{\frac {1}{k}}-2\sum _ {k=1}^{\lfloor {\frac {n}{2}}\rfloor}{\frac {1}{2k}}=\sum _{k=1 \na szczycie k\;{\text{parzysty }}}^{n}(1-2){\frac {1}{k}}+\sum _{k=1 \na szczycie k\;{\text{nieparzyste}}}^{n}{\frac {1}{k}}}$

wreszcie dać

${\ Displaystyle n! \ suma _ {k = 1} ^ {n} {\ Frac {(-1) ^ {k + 1}} {k}} \ sim n! \ log 2.}$

Oczekiwana liczba transpozycji losowej permutacji

Możemy użyć rozkładu permutacji na cykl rozłączny, aby rozłożyć ją na czynniki jako iloczyn transpozycji, zastępując cykl o długości k przez k - 1 transpozycji. Np. cykl ${\ Displaystyle (1 \; 2 \; 34)}$ czynniki jako ${\ Displaystyle (1 \; 2) \; (2 \; 3)\;(3\;4)}$ . funkcja ${\ Displaystyle b (k)}$ dla cykli jest równa ${\ displaystyle k-1}$ i otrzymujemy

${\ Displaystyle g (z, u) = \ lewo ({\ Frac {1} {1-uz}} \ prawej) ^ {1/u }}$

I

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq 1}(k-1){\frac {z^{k}}{k}}={\frac {z}{(1-z)^{2}}}-{\frac {1} {1-z}}\log {\frac {1}{1-z}}.}$

Stąd oczekiwana liczba transpozycji wynosi ${\ displaystyle T (n)}$

${\ Displaystyle T (n) = nH_ {n}}$

gdzie jest liczbą harmoniczną $displaystyle n ^ {th}$$}$ \ Moglibyśmy również otrzymać ten wzór, zauważając, że liczbę transpozycji uzyskuje się przez dodanie długości wszystkich cykli (co daje n ) i odjęcie jednego dla każdego cyklu (co daje ${\ displaystyle \ log n}$ przez poprzedni Sekcja).

Zauważ, że ponownie generuje liczby Stirlinga bez znaku $pierwszego$ rodzaju Dokładniej, mamy

${\ Displaystyle (-1) ^ {m} n! \; [z ^ {n}][u ^ {m}] g(z,u)=\left[{\begin{macierz}n\\nm\end{macierz}}\right]}$

Aby to zobaczyć, zauważ, że powyższe jest równoważne z

${\ Displaystyle (-1) ^ {n + m} n! \; [z ^ {n} [u ^ {m}] g (z, u) | _ {u =1/u}|_{z=uz}=\left[{\begin{macierz}n\\m\end{macierz}}\right]}$

i to

${\ Displaystyle [u ^ {m}] g (z, u) | _ {u = 1/u} | _ {z = uz} = [u ^ {m}] \ lewo ({\ Frac {1} 1-z}}\right)^{u}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m},}$

który widzieliśmy jako EGF niepodpisanych liczb Stirlinga pierwszego rodzaju w części dotyczącej permutacji składających się z dokładnie m cykli.

Oczekiwany rozmiar cyklu elementu losowego

Wybieramy losowy element q losowej permutacji $rozmiar$ cyklu zawierającego q . Tutaj funkcja jest równa $k ^ {2}}$ Displaystyle $,$ o długości wnosi k elementów , które są w cyklach o długości . Zauważ, że w przeciwieństwie do poprzednich obliczeń, musimy uśrednić ten parametr po wyodrębnieniu go z funkcji generującej (podzielenie przez n ). Mamy

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq 1}k^{2}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z}{(1-z)^ {2}}}={\frac {z}{(1-z)^{3}}}.}$

Stąd oczekiwana długość cyklu zawierającego q wynosi

${\ Displaystyle {\ Frac {1} {n}} [z ^ {n}] {\ Frac {z} {(1-z) ^ {3}}} = {\ Frac {1} {n}} \frac {1}{2}}n(n+1)={\frac {1}{2}}(n+1).}$

Prawdopodobieństwo, że losowy element leży w cyklu o rozmiarze m

$permutacji , element ten$ , że jeśli ponownie wybierzemy losowy element losowej w cyklu o m . Funkcja $k)}$$m = k}$ jest równa dla m $Displaystyle$ i zero w przeciwnym razie, ponieważ przyczyniają się tylko cykle o długości m , a mianowicie m elementy leżące na cyklu o długości m . Mamy

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\;m\;{\frac {z^{m} }{m}}={\frac {z^{m}}{1-z}}.}$

Wynika z tego, że prawdopodobieństwo, że losowy element leży w cyklu o długości m , wynosi

${\ Displaystyle {\ Frac {1} {n}} [z ^ {n}] {\ Frac {z ^ {m}} {1-z}} = {\ rozpocząć {przypadki} {\ Frac {1} n}},&{\mbox{if }}n\geq m\\0,&{\mbox{inaczej.}}\end{przypadki}}}$

Prawdopodobieństwo, że losowy podzbiór [ n ] leży w tym samym cyklu

Wybierz losowy podzbiór Q z [ n ] zawierający m elementów i losową permutację i zapytaj o prawdopodobieństwo, że wszystkie elementy Q leżą w tym samym cyklu. To kolejny średni parametr. Funkcja b ( k ) jest równa ${\ Displaystyle {\ rozpocząć {macierz} {k \ wybrać m} \ koniec {macierzy}}}$ , ponieważ cykl o długości k przyczynia się ${\ Displaystyle {\begin{matrix}{k \choose m}\end{macierz}}}$ podzbiory o rozmiarze m , gdzie ${\ Displaystyle {\ rozpocząć {macierz} {k \ wybrać m} = 0 \ koniec {macierzy}}}$ dla k < m . To daje

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq m}{k \choose m}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {1}{m}}{\ frac {z^{m}}{(1-z)^{m}}}={\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m +1}}}.}$

Uśredniając, uzyskujemy prawdopodobieństwo, że elementy Q będą w tym samym cyklu

${\ Displaystyle {n \ wybierz m} ^ {- 1} [z ^ {n}] {\ Frac {1} {m}}} {\ Frac {z ^ {m}} {(1-z) ^ {m +1}}}={n \choose m}^{-1}{\frac {1}{m}}[z^{nm}]{\frac {1}{(1-z)^{m+ 1}}}}$

Lub

${\ Displaystyle {\ Frac {1} {m}} {n \ wybierz m} ^ {-1} {(nm) \; + \; m \ wybierz m} = {\ frac {1} {m}}. }$

W szczególności prawdopodobieństwo, że dwa elementy p < q znajdują się w tym samym cyklu, wynosi 1/2.

Liczba permutacji zawierających parzystą liczbę parzystych cykli

Możemy bezpośrednio użyć fundamentalnego twierdzenia Flajoleta-Sedgewicka i obliczyć bardziej zaawansowane statystyki permutacji. (Zajrzyj na tę stronę, aby dowiedzieć się, w jaki sposób obliczane są operatory, których będziemy używać). Na przykład zbiór permutacji zawierających parzystą liczbę parzystych cykli jest określony wzorem

${\ Displaystyle \ nazwa operatora {ZESTAW} (\ nazwa operatora {CYC} _ {\ nazwa operatora {nieparzyste}} ({\ mathcal {Z}}}) \ nazwa operatora {ZESTAW} _ {\ nazwa operatora {parzyste}} (\ nazwa operatora {CYC } _{\operatorname {parzysty}}({\mathcal {Z}})).}$

Przekładając na wykładnicze funkcje generujące (EGF), otrzymujemy

${\ Displaystyle \ exp \ lewo ({\ Frac {1} {2}} \ log {\ Frac {1+z}{1-z}}\right)\cosh \left({\frac {1}{2}}\log {\frac {1}{1-z^{2}}}\right) }$

Lub

${\ Displaystyle {\ Frac {1} {2}} \ exp \ lewo ({\ Frac {1} {2}} \ lewo (\ log {\ Frac {1 + z} {1-z}} + \ log {\frac {1}{1-z^{2}}}\right)\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\left (\log {\frac {1+z}{1-z}}-\log {\frac {1}{1-z^{2}}}\right)\right).}$

To upraszcza do

${\ Displaystyle {\ Frac {1} {2}} \ exp \ left({\frac {1}{2}}\log {\frac {1}{(1-z)^{2}}}\right)+{\frac {1}{2}}\exp \left ({\frac {1}{2}}\log(1+z)^{2}\right)}$

Lub

${\ Displaystyle {\ Frac {1} {2}}} {\ Frac {1} {1-z}} + {\ Frac {1} {2}} (1 + z) = 1 + z + {\ Frac {1 }{2}}{\frac {z^{2}}{1-z}}.}$

Oznacza to, że istnieje jedna permutacja o rozmiarze zero zawierająca parzystą liczbę parzystych cykli (permutacja pusta, która zawiera zerowe cykle o parzystej długości), jedna taka permutacja o rozmiarze jeden (punkt stały, który zawiera również zerowe cykle o parzystej długości ) i że dla ${\ displaystyle n \ geq 2}$ jest ${\ displaystyle n!/2}$ takie permutacje.

Permutacje, które są kwadratami

Zastanówmy się, co się stanie, gdy podniesiemy permutację do kwadratu. Punkty stałe są odwzorowywane na punkty stałe. Cykle nieparzyste są odwzorowywane na cykle nieparzyste w korespondencji jeden do jednego, np. ${\ Displaystyle (1 \; 8 \; 9 \; 11 \; 13)}$ zamienia się w ${\ Displaystyle (1 \; 9 \; 13 \; 8 \; 11)}$ . Parzyste cykle dzielą się na dwie części i tworzą parę cykli o połowę mniejszą od pierwotnego cyklu, np. ${\ Displaystyle (5 \; 13 \; 6 \; 9)}$ zamienia się w ${\ Displaystyle (5 \; 6) \; (9 \; 13)}$ . Stąd permutacje, które są kwadratami, mogą zawierać dowolną liczbę nieparzystych cykli i parzystą liczbę cykli o rozmiarze dwa, parzystą liczbę cykli o rozmiarze cztery itd., i są dane przez

${\ Displaystyle \ nazwa operatora {ZESTAW} (\ nazwa operatora {CYC} _ {\ nazwa operatora {nieparzyste}} ({\ mathcal {Z}}}) \ nazwa operatora {ZESTAW} _ {\ nazwa operatora {parzyste}} (\ nazwa operatora {CYC } _{=2}({\mathcal {Z}}))\nazwa_operatora {SET} _{\nazwa_operatora {parzyste} }(\nazwa_operatora {CYC} _{=4}({\mathcal {Z}})) \operatorname {SET} _{\operatorname {parzyste}}(\operatorname {CYC} _{=6}({\mathcal {Z}}))\cdots}$

co daje EFG

${\ Displaystyle \ exp \ lewo ({\ Frac {1} {2}} \ log {\ Frac {1 + z} {1-z}} \ prawo) \ prod _ {m \ geq 1} \ cosh {\ frac {z^{2m}}{2m}}={\sqrt {\frac {1+z}{1-z}}}\prod _{m\geq 1}\cosh {\frac {z^{2m }}{2m}}.}$

Nieparzyste niezmienniki cyklu

Przedstawione w dwóch poprzednich podrozdziałach typy permutacji, tj. permutacje zawierające parzystą liczbę cykli i permutacje będące kwadratami, są przykładami tzw . Termin niezmiennik cyklu nieparzystego oznacza po prostu, że przynależność do odpowiedniej klasy kombinatorycznej jest niezależna od wielkości i liczby nieparzystych cykli występujących w permutacji. W rzeczywistości możemy udowodnić, że wszystkie nieparzyste niezmienniki cyklu podlegają prostej rekurencji, którą wyprowadzimy. Po pierwsze, oto kilka przykładów niezmienników cyklu nieparzystego.

Permutacje, w których suma długości parzystych cykli wynosi sześć

Ta klasa ma specyfikację

${\ Displaystyle \ nazwa operatora {ZESTAW} (\ nazwa operatora {CYC} _ {\ nazwa operatora {nieparzyste}} ({\ mathcal {Z}})} \ lewo (\ nazwa operatora {ZESTAW} _ {= 3} (\ nazwa operatora {CYC } _{=2}({\mathcal {Z}}))+\nazwa_operatora {CYC} _{=2}({\mathcal {Z}})\nazwa_operatora {CYC} _{=4}({\mathcal {Z}})+\operatorname {CYC} _{=6}({\mathcal {Z}})\right)}$

i funkcja generująca

${\ Displaystyle {\ sqrt {\ Frac {1 + z} {1-z}}} \ lewo ({\ Frac {1} {6}} \ lewo ({\ Frac {z ^ {2}}} {2} }\right)^{3}+{\frac {z^{2}}{2}}{\frac {z^{4}}{4}}+{\frac {z^{6}}{6 }}\right)={\frac {5}{16}}z^{6}{\sqrt {\frac {1+z}{1-z}}}.}$

Kilka pierwszych wartości to

${\ Displaystyle 0,0,0,0,0,225,1575,6300,56700,42525 0,4677750,46777500,608107500,\ kropki }$

Permutacje, w których wszystkie parzyste cykle mają tę samą długość

Ta klasa ma specyfikację

$_ \operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=4}({\mathcal {Z} }))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=6}({\mathcal {Z}}))+\cdots \right)}$

i funkcja generująca

${\ Displaystyle {\ sqrt {\ Frac {1 + z} {1-z}}} \ lewo (\ exp \ lewo ({\ Frac {z ^ {2}} {2}} \ prawej) -1 \, +\,\exp \left({\frac {z^{4}}{4}}\right)-1\,+\,\exp \left({\frac {z^{6}}{6} }\right)-1\,+\,\cdots \right).}$

Jest tu pewien semantyczny niuans. Możemy uznać permutacje nie zawierające parzystych cykli za należące do tej klasy, ponieważ zero jest parzyste . Kilka pierwszych wartości to

${\ Displaystyle 0,1,3,15,75,405,2835,22155,199395,1828575\ldots}$

Permutacje, w których maksymalna długość parzystego cyklu wynosi cztery

Ta klasa ma specyfikację

${\ Displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {nieparzysty} }({\mathcal {Z}}))\nazwa_operatora {SET} (\nazwa_operatora {CYC} _{=2}({\mathcal {Z}})+\nazwa_operatora {CYC} _{=4}({\ matematyka {Z}}))}$

i funkcja generująca

${\ Displaystyle {\ sqrt {\ Frac {1 + z} {1-z}}} \ exp \ lewo ({\ Frac {z ^ {2}} {2}} + {\ frac {z ^ {4} }{4}}\prawo).}$

Kilka pierwszych wartości to

${\ Displaystyle 1,2,6,24,120,600,4200,28560,2 57040,2207520,24282720,258128640,\ldkropki }$

Nawrót

Obserwuj uważnie, jak skonstruowane są specyfikacje składowej cyklu parzystego. Najlepiej myśleć o nich w kategoriach drzew analizy. Te drzewa mają trzy poziomy. Węzły na najniższym poziomie reprezentują sumy iloczynów cykli o parzystej długości singletonu. ${\ displaystyle {\ mathcal {Z}}}$ . Węzły na poziomie środkowym reprezentują ograniczenia operatora mnogościowego. Wreszcie węzeł na najwyższym poziomie sumuje iloczyny wkładów z poziomu środkowego. Należy zauważyć, że ograniczenia operatora mnogościowego zastosowane do parzystej funkcji generującej zachowają tę cechę, tj. utworzą inną parzystą funkcję generującą. Ale wszystkie dane wejściowe operatorów zbiorów są parzyste, ponieważ wynikają z cykli o parzystej długości. W rezultacie wszystkie zaangażowane funkcje generujące mają postać

${\ Displaystyle g (z) = h (z) {\ sqrt {\ Frac {1 + z} {1-z}}}}$

gdzie ${\ displaystyle h (z)}$ jest funkcją parzystą. To znaczy że

${\ Displaystyle {\ Frac {1} {1 + z}} \; g (z) = h (z) \; {\ Frac { 1}{\sqrt {1-z^{2}}}}}$

jest parzyste, a zatem

${\ Displaystyle {\ Frac {1} {1 + z}} \; g (z) = {\ Frac {1} {1-z}} \; g (- z) \ quad {\ mbox {lub}} \quad (1-z)\;g(z)=(1+z)\;g(-z).}$

Pozwalając ${\ Displaystyle g_ {n} = [z ^ {n}] g (z)}$ i wyodrębniając współczynniki, stwierdzamy, że

${\ Displaystyle {\ Frac {g_ {2m + 1}} {(2m + 1)!}} - {\ Frac {g_ {2m}} {(2m)!}} = - {\ Frac {g_ {2m + 1}}{(2m+1)!}}+{\frac {g_{2m}}{(2m)!}}\quad {\mbox{ lub }}\quad 2{\frac {g_{2m+1 }}{(2m+1)!}}=2{\frac {g_{2m}}{(2m)!}}}$

co daje rekurencję

${\ displaystyle g_ {2m + 1} = (2m + 1) g_ {2m} \,.}$

Problem z konkursu Putnama z 2005 roku

Link do strony konkursu Putnam pojawia się w sekcji Linki zewnętrzne . Problem prosi o dowód na to

${\ Displaystyle \ suma _ {\ pi \ w S_ {n}} {\ Frac {\ sigma (\pi)}{\nu (\pi)+1}}=(-1)^{n+1}{\frac {n}{n+1}},}$

gdzie suma jest po wszystkich ${\ Displaystyle n!}$ Permutacje ${\ Displaystyle [n]}$ , ${\ Displaystyle \ sigma (\ pi)}$ to znak ${\ Displaystyle \ pi}$ , tj. $\ sigma (\ pi) = 1}$ jeśli jest $)$ i ${ \$$π$$-1}$ jeśli jest i jest liczbą stałych punktów $\ displaystyle \pi }$ .

Teraz znak jest podany przez ${\ displaystyle \ pi}$

${\ Displaystyle \ sigma (\ pi) = \ prod _ {c \ in \ pi} (-1) ^ {| c | -1},}$

gdzie iloczyn znajduje się we wszystkich cyklach c , jak wyjaśniono np $nieparzystych$ Na stronie permutacji parzystych i .

Dlatego rozważamy klasę kombinatoryczną

${\ Displaystyle \ operatorname {SET} (- {\ mathcal {Z}} + {\ mathcal {V}} {\ mathcal {Z}} + \ operatorname {CYC} _ {= 1} ({\ mathcal {Z} })+{\mathcal {U}}\nazwa_operatora {CYC} _{=2}({\mathcal {Z}})+{\mathcal {U}}^{2}\nazwa_operatora {CYC} _{=3 }({\mathcal {Z}})+{\mathcal {U}}^{3}\operatorname {CYC} _{=4}({\mathcal {Z}})+\cdots )}$

gdzie $oznacza$$punkty$ minus długość cyklu składowego, a stałe. Przekładając na funkcje generujące, otrzymujemy

${\ Displaystyle g (z, u, v) = \ exp \ lewo (-z + vz+\sum _{k\geq 1}u^{k-1}{\frac {z^{k}}{k}}\right)}$

Lub

${\ Displaystyle \ exp \ lewo (-z + vz + {\ frac {1} {u}} \ log {\ frac {1} {1-uz}} \ prawej) = \ exp (-z + vz) \ lewo ({\frac {1}{1-uz}}\right)^{1/u}.}$

Teraz mamy

${\ Displaystyle n! [z ^ {n}] g (z, -1, v) = n! [z ^ {n}] \ exp (-z + vz) (1 + z) = \ suma _ {\ pi \in S_{n}}\sigma (\pi)v^{\nu (\pi)}}$

a zatem pożądana ilość jest dana przez

${\ Displaystyle n! [z ^ {n}] \ int _ {0} ^ {1} g (z, -1, v) dv = \ suma _ {\ pi \ w S_ {n}} {\ frac { \sigma (\pi )}{\nu (\pi )+1}}.}$

Wykonując obliczenia, otrzymujemy

${\ Displaystyle \ int _ {0} ^ {1} g(z,-1,v)dv=\exp(-z)(1+z)\left({\frac {1}{z}}\exp(z)-{\frac {1}{z} }\Prawidłowy)}$

Lub

${\ Displaystyle \ lewo ({\ Frac {1} {z}} + 1 \ prawo) \ lewo (1- \ exp (- z) \ prawo) = {\ Frac {1} {z}} + 1- \ exp(-z)-{\frac {1}{z}}\exp(-z).}$

$wynosi$ że współczynnik zero Stałą jest jedynka, która nie zgadza się ze wzorem (powinna wynosić zero). Jednak dla $uzyskujemy$

${\ Displaystyle n! [z ^ {n}] \ lewo (- \ exp (- z) - {\ Frac {1} {z}} \ exp (- z) \ prawej) = n! \ lewo (- ( -1)^{n}{\frac {1}{n!}}-(-1)^{n+1}{\frac {1}{(n+1)!}}\right)}$

Lub

${\ Displaystyle (-1) ^ {n + 1} \ lewo (1- {\ Frac { 1}{n+1}}\right)=(-1)^{n+1}{\frac {n}{n+1}},}$

co jest pożądanym rezultatem.

Na marginesie, zauważamy, że można użyć do oszacowania następującego wyznacznika macierzy ${\ displaystyle n \ razy n}$$}$ ) :

${\ Displaystyle d (n) = \ det (A_ {n}) = {\ rozpocząć {vmatrix} a&&b&&b&&\ cdots &&b \\b&&a&&b&&&\cdots &&b\\b&&b&&a&&&\cdots &&b\\\vdots &&\vdots &&\vdots && \ddots &&\vdots \\b&&b&&b&&\cdots &&a\end{vmatrix}}.}$

gdzie ${\ Displaystyle a, b \ neq 0}$ . Przypomnij sobie wzór na wyznacznik:

${\ Displaystyle \ det (A) = \ suma _ {\ pi \ w S_ {n}} \ sigma (\ pi) \ prod _ {i = 1} ^ {n} A_ {i, \ pi (i)} .}$

Teraz wartość iloczynu po prawej stronie dla permutacji $\$ za $Displaystyle a ^ {f} b ^ {nf}}$ , gdzie f jest liczbą stałych punktów ${\ Displaystyle \ pi}$ . Stąd

${\ Displaystyle d (n) = b ^ {n} n! [z ^ {n}] g \ lewo (z, -1, {\ Frac {a} {b}} \ prawo) = b ^ {n} n![z^{n}]\exp \left({\frac {ab}{b}}z\right)(1+z)}$

co daje

${\ Displaystyle b ^ {n} \ lewo ({\frac {ab}{b}}\right)^{n}+b^{n}n\left({\frac {ab}{b}}\right)^{n-1}=(ab )^{n}+nb(ab)^{n-1}}$

i w końcu

${\ Displaystyle d (n) = (a + (n-1) b) (ab) ^ {n-1} \,.}$

Różnica między liczbą cykli w parzystych i nieparzystych permutacjach

Tutaj staramy się pokazać, że ta różnica jest dana przez

${\ Displaystyle (-1) ^ {n} (n-2)!}$

$\ Displaystyle$ , że znak permutacji jest dany przez $\ sigma (\ pi) }$

${\ Displaystyle \ sigma (\ pi) = \ prod _ {c \ in \ pi} (-1) ^ {| c | -1}}$

gdzie produkt waha się w cyklach c od rozłącznego składu cykli ${\ displaystyle \ pi}$ .

Wynika z tego, że gatunek kombinatoryczny , który odzwierciedla znaki i liczbę cykli zbioru permutacji, jest określony przez ${\ displaystyle {\ mathcal {Q}}}$

${\ Displaystyle {\ mathcal {Q}} = \ nazwa operatora {ZESTAW} ({\ mathcal {V}} \ nazwa operatora {CYC} _ {1} ({\ mathcal {Z}}) + {\mathcal {U}}{\mathcal {V}}\operatorname {CYC} _{=2}({\mathcal {Z}}))+{\mathcal {U}}^{2}{\mathcal { V}}\nazwa_operatora {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}{\mathcal {V}}\nazwa_operatora {CYC} _{=4 }({\mathcal {Z}})+{\mathcal {U}}^{4}{\mathcal {V}}\operatorname {CYC} _{=5}({\mathcal {Z}})+\ kropki )}$

$cykli$ użyliśmy $do$ oznaczania znaków i do liczenia

Przekładając na funkcje generujące mamy

${\ Displaystyle Q (z, u, v) = \ exp \ lewo (v {\ Frac {z} {1}} + vu {\ frac {z ^ {2}} {2}} + vu ^ {2} {\frac {z^{3}}{3}}+vu^{3}{\frac {z^{4}}{4}}+vu^{4}{\frac {z^{5}} {5}}+\cdots \po prawej).}$

To upraszcza do

${\ Displaystyle Q (z, u, v) = \ exp \ lewo ({\ Frac {v} {u}} \ lewo ({\ Frac {zu} {1}} + {\ Frac {z ^ {2} u^{2}}{2}}+{\frac {z^{3}u^{3}}{3}}+{\frac {z^{4}u^{4}}{4}} +{\frac {z^{5}u^{5}}{5}}+\cdots \right)\right)}$

który jest

${\ Displaystyle \ exp \ lewo ({\ Frac {v} {u}} \ log {\ Frac {1} {1-uz}} \ prawej) = \ lewo ({\ frac {1} {1-uz} }\right)^{\frac {v}{u}}.}$

Teraz dwie funkcje generujące i parzyste $}$ nieparzyste Q $Displaystyle$ permutacje według liczby cykli są podane przez

${\ Displaystyle Q_ {1} (z, v) = {\ Frac {1} {2}} Q (z, + 1, v) + {\ Frac {1} {2}} Q (z, -1, v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}+{\frac {1}{2}}\left({ \frac {1}{1+z}}\right)^{-v}}$

I

${\ Displaystyle Q_ {2} (z, v) = {\ Frac {1} {2}} Q (z, + 1, v) - {\ Frac {1} {2}} Q (z, -1, v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}-{\frac {1}{2}}\left({ \frac {1}{1+z}}\right)^{-v}.}$

Wymagamy ilości

${\ Displaystyle G (z, v) = \ lewo. {\ Frac {d} {dv}} (Q_ {1} (z, v) -Q_ {2} (z, v)} \ prawo | _{v=1}}$

który jest

${\ Displaystyle \ lewo. {\ Frac {d} {dv}} \ lewo ({\ Frac {1} {1 + z}} \ prawo) ^ {- v} \ prawo | _ {v = 1} = - \left.\log {\frac {1}{1+z}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}= -(1+z)\log {\frac {1}{1+z}}.}$

Ostatecznie, wyodrębniając współczynniki z tej funkcji generującej, otrzymujemy

${\ Displaystyle -n! [z ^ {n}] (1 + z) \ log {\ Frac {1} {1 + z} }=-n!\left({\frac {(-1)^{n}}{n}}+{\frac {(-1)^{n-1}}{n-1}}\right) }$

który jest

${\ Displaystyle -n! (-1) ^ {n-1} \ lewo (- {\ Frac {1} {n}} + { \frac {1}{n-1}}\right)=n!(-1)^{n}{\frac {n-(n-1)}{n(n-1)}}}$

co z kolei

${\ Displaystyle n! (-1) ^ {n} {\ Frac {1} {n (n-1)}} = (-1) ^ {n} (n-2)!}$

To kończy dowód.

Zobacz też

• Stała Golomba-Dickmana

Linki zewnętrzne

•   Śpiewane, Filip; Zhang Yan (2003). „Powtarzające się nawroty w liczeniu permutacji”. CiteSeerX 10.1.1.91.1088 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
• Marko Riedel i in., Różnica liczby cykli parzystych i nieparzystych permutacji
• Marko Riedel i in., Klucze w zamkniętych pudełkach, pytanie o prawdopodobieństwo

100 więźniów

• Różni autorzy, Permutacje z cyklem > n/2
• Różni autorzy, Właściwość zaburzeń
• Różni autorzy, Przewidywana liczba punktów stałych
• Peter Winkler, Siedem zagadek, o których myślisz, że nie słyszałeś poprawnie
• Różni autorzy, Les-Mathematiques.net . Cent więźniowie (po francusku)