Statystyki permutacji losowych — Random permutation statistics

Te dane statystyczne losowych permutacje , takie jak struktury cyklu o losowej permutacji mają zasadnicze znaczenie dla analizy algorytmów , w szczególności algorytmy sortowania, które działają na losowych permutacji. Załóżmy na przykład, że używamy quickselect (kuzyna quicksort ) do wybrania losowego elementu losowej permutacji. Quickselect wykona częściowe sortowanie na tablicy, dzieląc tablicę według osi. Stąd permutacja będzie mniej nieuporządkowana po wykonaniu szybkiego wyboru. Ilość nieporządku, który pozostaje, można analizować za pomocą funkcji generujących. Te funkcje generujące zależą w zasadniczy sposób od funkcji generujących statystyki permutacji losowych. Dlatego tak ważne jest obliczenie tych funkcji generujących.

Artykuł o losowych permutacjach zawiera wprowadzenie do losowych permutacji.

Podstawowa relacja

Permutacje to zestawy oznaczonych cykli. Używając oznaczonego przypadku podstawowego twierdzenia Flajoleta-Sedgewicka i pisząc dla zbioru permutacji i dla zbioru singletonów, mamy ${\displaystyle \scriptstyle {\mathcal {P}}}$${\displaystyle \scriptstyle {\mathcal {Z}}}$

${\ Displaystyle \ operatorname {SET} (\ operatorname {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) jest

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

To jedno równanie pozwala na wyprowadzenie dużej liczby statystyk permutacji. Po pierwsze, usuwając terminy z , tj. exp, możemy ograniczyć liczbę cykli, które zawiera permutacja, np. ograniczając EGF do uzyskania permutacji zawierających dwa cykle. Po drugie, należy zauważyć, że EGF cykli oznaczonych, tj. , wynosi ${\displaystyle \scriptstyle \operator {SET}}$${\ Displaystyle \ scriptstyle \ operatorname {SET} _{2}}$${\ Displaystyle \ scriptstyle \ operatorname {CYC} ({\ mathcal {Z}})}$

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

ponieważ istnieje k!/k oznaczonych cykli. Oznacza to, że odrzucając terminy z tej funkcji generującej, możemy ograniczyć rozmiar cykli występujących w permutacji i uzyskać EGF permutacji zawierających tylko cykle o danej wielkości.

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

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

zdefiniowanie wartości b dla permutacji jako sumy jej wartości na cyklach, to 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)} \ po prawej) { \frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{\frac {z^{k}}{k}}}$

Jest to funkcja „mieszane” generujący: jest to funkcja wykładnicza generujący w Z. i zwykła funkcja generowania w parametrze wtórnej u. Rozróżniają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!}}}$

Jest to funkcja generująca prawdopodobieństwo oczekiwania b . Innymi słowy, współczynnik w tym szeregu potęgowym jest oczekiwaną wartością b dla permutacji w , biorąc pod uwagę, że każda permutacja jest wybierana z takim samym prawdopodobieństwem . ${\ Displaystyle z ^ {n}}$${\displaystyle S_{n}}$${\displaystyle 1/n!}$

W artykule zastosowano operator ekstrakcji współczynników [ z ⁿ ] udokumentowany na stronie dla formalnych szeregów potęgowych .

Liczba permutacji będących inwolucjami

Zanik jest σ permutacji, aby σ ² = 1 pod permutacji kompozycji. Wynika z tego, że σ może zawierać tylko cykle o długości jeden lub dwa, czyli wykładnicza funkcja generująca g ( z ) tych permutacji jest

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

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}^{\lpodłoga n/2\rpodłoga }{\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 będących m- tymi pierwiastkami jedności

To uogólnia pojęcie inwolucji. M p korzenia jedności jest σ permutacji, aby σ ^m = 1 na podstawie składu permutacji. Teraz za każdym razem, gdy stosujemy σ, poruszamy się o jeden krok równolegle we wszystkich jego cyklach. Cykl o długości d zastosowany d razy tworzy permutację identyczności na d elementach ( d stałych punktów), a d jest najmniejszą wartością do wykonania. Stąd m musi być wielokrotnością wszystkich rozmiarów cykli d , tzn. 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 \ średni m} {\ Frac {z ^ {d}} {d}} \ po prawej).}$

Gdy 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}^{\lpodłoga n/p\rpodłoga }{\frac {1}{(n-pb)!\;p^{b}\;b!}}.}$

Liczba permutacji rzędu dokładnie k

Można to zrobić przez inwersję Möbiusa . Pracując z tym samym pojęciem, co w poprzednim wpisie, zauważamy, że kombinatoryczne gatunki permutacji, których porządek dzieli k, jest określony przez ${\displaystyle {\mathcal {Q}}}$

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

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

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

Teraz możemy użyć tej funkcji generującej, aby zliczyć permutacje rzędu dokładnie k . Niech będzie liczba permutacji na n, których kolejność jest dokładnie d i liczba permutacji na n liczba permutacji, których kolejność dzieli k . Potem będzie ${\displaystyle p_{n,d}}$${\displaystyle q_{n,k}}$

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

Wynika z inwersji Möbiusa, że

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

Dlatego mamy EFG

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

Żądana liczba jest następnie podana przez

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

Ten wzór 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 20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280,\ldots}$(sekwencja A061121 w OEIS )

Dla k  = 8 otrzymujemy EGF

${\ 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,39916800,363242880,3874590720,34767532800,\ldots}$(sekwencja A061122 w OEIS )

Ostatecznie dla k  = 12 otrzymujemy EGF

${\ 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

${\ Displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600,\ldots}$(sekwencja A061125 w OEIS )

Liczba permutacji będących derangementami

Załóżmy, że na imprezie jest n osób, z których każda przyniosła parasol. Pod koniec imprezy wszyscy wybierają parasol ze stosu parasoli i liści. Jakie jest prawdopodobieństwo, że nikt nie wyjdzie z własnym parasolem? Ten problem jest równoważny liczeniu permutacji bez punktów stałych (zwanych derangements ), a więc EGF, gdzie odejmujemy punkty stałe (cykle o długości 1), usuwając wyraz z z podstawowej relacji to

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

Mnożenie przez sumy współczynników , więc , całkowitej liczby odchyleń, otrzymuje wzór: ${\ Displaystyle 1/(1-z)}$${\ Displaystyle e ^ {-z}}$${\ Displaystyle D (n)}$

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

W związku z tym istnieją zaburzenia, a prawdopodobieństwo, że losowa permutacja jest zaburzeniem, wynosi${\displaystyle n!/e}$${\displaystyle 1/e.}$

Ten wynik może być również udowodniony przez włączenie-wykluczenie . Używając zbiorów, gdzie oznaczamy zbiór permutacji, które ustalają p , mamy ${\ Displaystyle A_ {p}}$${\ Displaystyle {\ zacząć {macierz} 1 \ równoważnik p \ równoważnik n \ koniec {macierz}}}$

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

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

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

Stąd liczba permutacji bez stałego punktu 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 liczby rencontres , czyli liczba permutacji zawierających m punktów stałych. Odpowiedni EGF otrzymujemy zaznaczając cykle o rozmiarze jeden zmienną u , tj. wybierając b ( k ) równe jeden dla i zero w przeciwnym razie, co daje funkcję generowania zbioru permutacji przez liczbę punktów stałych: ${\ Displaystyle D (n, m)}$${\displaystyle [n]}$${\displaystyle k=1}$${\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 sugeruje, że

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

dla n duże, m stałe.

Kolejność losowej permutacji

Jeśli p jest permutacją The zamówienie z P jest najmniejsza dodatnia n , dla których jest permutacją tożsamości. Jest to najmniejsza wspólna wielokrotność długości cykli P . ${\ Displaystyle P ^ {n}}$

Twierdzenie Goha i Schmutza mówi, że jeśli jest oczekiwaną kolejnością losowej permutacji wielkości n , to ${\ Displaystyle \ mu _ {n}}$

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

gdzie stała c to

${\ Displaystyle 2 {\ sqrt {2 \ int _ {0} ^ {\ infty} \ log \ log \ lewo ({\ Frac {e} {1-e ^ {-t}}} \ prawej) dt}} \ok 1.1178641511899}$

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

Możemy użyć tej samej konstrukcji, co w poprzedniej sekcji, aby obliczyć liczbę odchyleń zawierających parzystą liczbę cykli i liczbę zawierającą nieparzystą liczbę cykli. Aby to zrobić musimy zaznaczyć wszystkie cykle i odjąć punkty stałe, podając ${\displaystyle D_{0}(n)}$${\displaystyle D_{1}(n)}$

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

Teraz niektórzy bardzo podstawowe rozumowanie pokazuje, że EFG od oblicza się według ${\displaystyle q(z)}$${\displaystyle D_{0}(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).}$

W ten sposób mamy

${\ 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 od , znajdujemy ${\displaystyle D_{0}(n)}$${\ Displaystyle D (n)}$

${\ 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 ) to${\displaystyle D_{0}(n)}$${\displaystyle D_{1}(n)}$${\displaystyle n-1.}$

Sto 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. Gromadzi więc stu więźniów i prosi ich o rozegranie następującej gry: ustawia w szeregu sto urn, każda z imieniem jednego więźnia, przy czym nazwisko każdego więźnia występuje dokładnie raz. Gra przebiega w następujący sposób: każdy więzień może zajrzeć do pięćdziesięciu urn. Jeśli nie znajdzie swojego nazwiska w jednej z pięćdziesięciu urn, wszyscy więźniowie zostaną natychmiast straceni, w przeciwnym razie gra będzie kontynuowana. 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 jakikolwiek sposób oznaczać urn ani przesuwać urn lub nazw w nich zawartych. Wybierając urny losowo, ich szanse na przeżycie są prawie zerowe, ale istnieje strategia dająca im 30% szans na przeżycie, zakładając, że nazwy są przypisywane do urn losowo – co to jest?

Przede wszystkim prawdopodobieństwo przeżycia przy użyciu losowych wyborów wynosi

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

więc zdecydowanie nie jest to praktyczna strategia.

Strategia przetrwania 30% polega na traktowaniu zawartości urn jako permutacji więźniów i przemierzaniu cykli. Aby zachować prostą notację, każdemu więźniowi przypisz numer, na przykład sortując ich nazwiska alfabetycznie. Od tego momentu urny mogą być uważane za zawierające liczby, a nie imiona. Teraz wyraźnie zawartość urn określa 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żyje, jeśli znajdzie swoje nazwisko, w przeciwnym razie otwiera urnę z właśnie odzyskanym numerem, maksymalnie do 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 reprezentowanych przez urny. Każdy więzień zaczyna od urny opatrzonej jego numerem i kontynuuje przechodzenie przez swój cykl do limitu pięćdziesięciu urn. Numer urny, który zawiera jego numer, jest wstępnym obrazem tej liczby pod permutacją. Stąd więźniowie przeżywają, jeśli wszystkie cykle permutacji zawierają co najwyżej pięćdziesiąt elementów. Musimy wykazać, że to prawdopodobieństwo wynosi co najmniej 30%.

Zauważ, że zakłada to, że naczelnik losowo wybiera permutację; jeśli naczelnik przewiduje taką strategię, może po prostu wybrać permutację z cyklem długości 51. Aby to przezwyciężyć, więźniowie mogą z góry uzgodnić losową permutację swoich imion.

Rozważamy ogólny przypadek więźniów i otwierania urn. Najpierw obliczamy prawdopodobieństwo komplementarne, to znaczy, że istnieje cykl składający się z więcej niż elementów. Mając to na uwadze, przedstawiamy ${\displaystyle 2n}$${\ Displaystyle n}$${\ Displaystyle n}$

${\ 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 \ lewo ((u-1) \ lewo ({\ Frac {z ^ {n + 1}} {n + 1}} + {\ Frac {z^{n+2}}{n+2}}+\cdots \w prawo)\w prawo),}$

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

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

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

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

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 oszacowania całkowego, takiego jak sumowanie Eulera-Maclaurina lub asymptotyczne rozwinięcie liczby n- tej 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.

Pokrewnym 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 zawdzięczamy Annie Gál i Peterowi Bro Miltersenowi; skonsultuj się z artykułem Petera Winklera, aby uzyskać więcej informacji, i zobacz dyskusję na Les-Mathematiques.net . Zapoznaj się z odnośnikami do 100 więźniów, aby znaleźć linki do tych odnośników.

Powyższe obliczenie można przeprowadzić w prostszy i bardziej bezpośredni sposób: najpierw zauważ, że permutacja elementów zawiera co najwyżej jeden cykl o długości ściśle większej niż . Tak więc, jeśli oznaczamy ${\displaystyle 2n}$${\ Displaystyle n}$

${\displaystyle p_{k}=\Pr[{\mbox{istnieje cykl długości}}k]}$

następnie

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

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

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

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

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

Dochodzimy do wniosku, ż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 skrzynki)

Istnieje ściśle powiązany problem, który całkiem ładnie pasuje do przedstawionej tutaj metody. Powiedzmy, że masz n zamówionych pudełek. Każde pudełko zawiera klucz do jakiegoś innego pudełka lub ewentualnie samo dające permutację kluczy. Możesz wybrać k z tych n pól na raz i jednocześnie je otworzyć, uzyskując dostęp do k kluczy. Jakie jest prawdopodobieństwo, że za pomocą tych kluczy otworzysz wszystkie n skrzynek, w których 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ści 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? Twierdzi się, że to prawdopodobieństwo wynosi k/n .

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

${\ Displaystyle {\ mathcal {Q}} = \ operatorname {SET} \ lewo (\ suma _ {q \ geq 1} \ operatorname {CYC} _ {= q} ({\ mathcal {Z}}) \ razy \ suma _{p=1}^{q}{q \wybierz p}{\mathcal {U}}^{p}\right).}$

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

Tłumaczą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).}$

Upraszcza to

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

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 przepisać tak

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

Wynika z tego, że

${\ 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}.}$

Dziel przez, aby otrzymać ${\displaystyle {n \wybierz k}}$

${\ 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 . ${\displaystyle G(z,u)}$

Liczba permutacji zawierających m cykli

Zastosowanie fundamentalnego twierdzenia Flajoleta-Sedgewicka , czyli twierdzenia o wyliczeniu etykietowanym z , do zbioru ${\ Displaystyle G = S_ {m}}$

${\ Displaystyle \ operatorname {SET} _ {= m} (\ operatorname {CYC} ({\ mathcal {Z}}))}$

otrzymujemy funkcję generującą

${\ Displaystyle g_ {m} (z) = {\ Frac {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 liczby Stirlinga ze znakiem pierwszego rodzaju i jest EGF liczb Stirlinga bez znaku pierwszego rodzaju, tj. ${\ Displaystyle g_ {m} (z)}$

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

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}.}$

Podsumowują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}\sum _{m=0}^{n}s(n,m)w^{m}.}$

Korzystając ze wzoru zawierającego logarytm z lewej strony, definicję z prawej strony i twierdzenie dwumianowe otrzymujemy ${\ Displaystyle g_ {m} (z)}$${\ Displaystyle s_ {n} (w)}$

${\ 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 korzystając z definicji współczynnika dwumianowego , w końcu mamy ${\ Displaystyle z ^ {n}}$

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

spada silnia . Obliczanie OGF niepodpisanych liczb Stirlinga pierwszego rodzaju działa w podobny sposób.

Oczekiwana liczba cykli o danej wielkości m

W tym zadaniu wykorzystujemy dwuwymiarową funkcję generującą g ( z ,  u ) opisaną we wstępie. Wartość b dla cyklu nie o rozmiarze 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}} \ suma _ { 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 mw permutacji 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 ustalonego punktu.

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

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

gdzie H _m to m p harmonicznej . W związku z tym oczekuje się liczby cykli o długości co najwyżej m w przypadkowym permutacji około ln  m .

Momenty punktów stałych

Mieszany GF zbioru permutacji przez liczbę punktów stałych wynosi ${\displaystyle g(z,u)}$

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

Niech zmienna losowa X będzie liczbą 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 \ lewo (\ suma _ {k = 0} ^ {m} \ lewo \ {{\ zacząć {macierz} m \ \ k \ koniec {macierz}} \ prawo \}(X)_{k}\right)=\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}E ((X)_{k}),}$

gdzie jest spadająca silnia . Używając , mamy ${\ Displaystyle (X) _ {k}}$${\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 , a jeden w przeciwnym razie. Stąd tylko warunki z wkładem do sumy. To daje ${\displaystyle k>n}$${\displaystyle k<=n}$

${\ Displaystyle E (X ^ {m}) = \ suma _ {k = 0} ^ {n} \ lewo \ {{\ zacząć {macierz} m \ \ k \ koniec {macierz}} \ prawej \}.}$

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

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

Dla każdego dzielnik z cyklu długości dzieli stałych punktów, gdy podniesiona do potęgi Stąd musimy zaznaczyć te cykle z Aby zilustrować to rozważyć${\displaystyle d}$${\displaystyle k}$${\displaystyle d}$${\displaystyle d}$${\displaystyle k.}$${\ Displaystyle u ^ {d}.}$${\ 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}}\prawo).}$

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

${\ Displaystyle \ lewo. {\ Frac {\ częściowy} {\ częściowy 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 średnio dla i są cztery stałe punkty. ${\ Displaystyle E [F_ {6}] = 4}$${\displaystyle n\geq 6}$

Ogólna procedura to

${\ Displaystyle g (z, u) = \ exp \ lewo (\ suma _ {d \ średni 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)\ dobrze).}$

Po raz kolejny kontynuując jak poprzednio, stwierdzamy:

${\ Displaystyle \ lewo. {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) \ prawo | _ {u = 1} = \ lewo. {\ Frac {\ suma _ {d \ średni 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}}.}$

Wykazaliśmy, że wartość jest równa (the liczba dzielników o ) tak szybko, jak to zaczyna się w za i wzrasta o jeden za każdym razem uderza dzielnik włącznie siebie. ${\ Displaystyle E [F_ {k}]}$${\ Displaystyle \ tau (k)}$${\displaystyle k}$${\displaystyle n\geq k.}$${\ Displaystyle 1}$${\displaystyle n=1}$${\ Displaystyle n}$${\displaystyle k}$${\displaystyle k}$

Oczekiwana liczba cykli o dowolnej długości losowej permutacji

Funkcję generującą dwuwymiarową konstruujemy za pomocą , gdzie jest jedynką dla wszystkich cykli (każdy cykl wnosi jeden do całkowitej liczby cykli). ${\displaystyle g(z,u)}$${\displaystyle b(k)}$${\displaystyle b(k)}$

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

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

i generuje liczby Stirlinga bez znaku 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 liczba harmoniczna , czyli około . ${\ Displaystyle H_ {n}}$${\ Displaystyle \ log n}$

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

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

Jeszcze raz zacznij od funkcji generowania wykładniczego , tym razem klasy permutacji według rozmiaru, gdzie cykle o długości większej niż są oznaczone zmienną : ${\displaystyle g(z,u)}$${\displaystyle {\mathcal {P}}}$${\displaystyle n/2}$${\ Displaystyle u}$

${\ Displaystyle g (z, u) = \ exp \ lewo (u \ suma _ {k> \ l podłoga {\ Frac {n} {2}} \ r podłoga} ^ {\ infty} {\ Frac {z ^ {k }}{k}}+\sum _{k=1}^{\lpodłoga {\frac {n}{2}}\rpodłoga }{\frac {z^{k}}{k}}\right). }$

Może być tylko jeden cykl o długości większej niż , stąd odpowiedź na pytanie daje ${\displaystyle {\frac {n}{2}}}$

${\ Displaystyle n! [uz ^ {n}] g (z, u) = n! [z ^ {n}] \ exp \ lewo (\ suma _ {k = 1} ^ {\ l piętro {\ Frac {n }{2}}\rpodłoga }{\frac {z^{k}}{k}}\right)\sum _{k>\lpodłoga {\frac {n}{2}}\rpodłoga }^{\infty }{\frac {z^{k}}{k}}}$

lub

${\ Displaystyle n! [z ^ {n}] \ exp \ lewo (\ log {\ Frac {1} {1-z}} - \ suma _ {k> \ l podłoga {\ 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> \ l piętro {\ Frac {n} {2}} \ r piętro }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lpodłoga {\frac {n}{2}}\rpodłoga }^{\infty }{ \frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z}}\sum _{m=0}^{\infty }{\ frac {(-1)^{m}}{m!}}\left(\sum _{k>\lpodłoga {\frac {n}{2}}\rpodłoga }^{\infty }{\frac {z ^{k}}{k}}\prawo)^{m+1}}$

Wykładnik terminu podniesienie do potęgi jest większy niż i dlatego żadna wartość nie może przyczynić się do${\displaystyle z}$${\displaystyle m+1}$${\displaystyle \lpodłoga {\frac {n}{2}}\rpodłoga}$${\ Displaystyle m> 0}$${\ Displaystyle [z ^ {n}].}$

Wynika z tego, że odpowiedź brzmi

${\ Displaystyle n! [z ^ {n}] {\ Frac {1} {1-z}} \ suma _ {k> \ l piętro {\ Frac {n} {2}} \ r piętro} ^ {\ infty} {\frac {z^{k}}{k}}=n!\sum _{k=\lpodłoga {\frac {n}{2}}\rpodłoga +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}} \ r piętro }{\frac {1}{k}}=\suma _{k=1}^{n}{\frac {1}{k}}-2\sum _{k=1}^{\lpodłoga {\ frac {n}{2}}\rfloor }{\frac {1}{2k}}=\sum _{k=1 \atop k\;{\text{parzyste}}}^{n}(1-2 ){\frac {1}{k}}+\sum _{k=1 \atop k\;{\text{nieparzysty}}}^{n}{\frac {1}{k}}}$

wreszcie dawanie

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

Oczekiwana liczba transpozycji losowej permutacji

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

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

oraz

${\ 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) = n-H_ {n}}$

gdzie jest liczba harmoniczna . 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 w poprzedniej sekcji). ${\ Displaystyle H_ {n}}$${\ Displaystyle n ^ {th}}$ ${\ Displaystyle \ log n}$

Zauważ, że ponownie generuje liczby Stirlinga pierwszego rodzaju bez znaku , ale w odwrotnej kolejności. Dokładniej, mamy ${\displaystyle g(z,u)}$

${\ Displaystyle (-1) ^ {m} n! \; [z ^ {n}} [u ^ {m}] g (z, u) = \ lewo [{\ zacznij {macierz} n \ \ nm \ koniec{macierz}}\prawo]}$

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

${\ 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 sekcji o permutacjach składających się dokładnie z m cykli.

Oczekiwany rozmiar cyklu elementu losowego

Wybieramy losowy element q losowej permutacji i pytamy o oczekiwaną wielkość cyklu zawierającego q . Tutaj funkcja jest równa , ponieważ cykl o długości k wnosi k elementów znajdujących się w cyklach o długości k . Zauważ, że w przeciwieństwie do poprzednich obliczeń, musimy uśrednić ten parametr po wyodrębnieniu go z funkcji generującej (podziel przez n ). Mamy ${\displaystyle \sigma}$${\displaystyle b(k)}$${\ Displaystyle k ^ {2}}$

${\ 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 element losowy leży w cyklu o rozmiarze m

Ten średni parametr reprezentuje prawdopodobieństwo, że jeśli ponownie wybierzemy losowy element losowej permutacji, element ten leży w cyklu o rozmiarze m . Funkcja jest równa for, aw przeciwnym razie zero, ponieważ wnoszą wkład tylko cykle o długości m , czyli m elementów, które leżą w cyklu o długości m . Mamy ${\displaystyle [n]}$${\displaystyle b(k)}$${\ Displaystyle m}$${\displaystyle m=k}$

${\ 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 element losowy leży w cyklu o długości m wynosi

${\ Displaystyle {\ Frac {1} {n}} [z ^ {n}] {\ Frac {z ^ {m}} {1-z}} = {\ zacząć {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 , ponieważ cykl o długości k wnosi podzbiory o rozmiarze m , gdzie dla k < m . To daje ${\ Displaystyle {\ zacząć {macierz} {k \ wybierz m} \ koniec {macierz}}}$${\ Displaystyle {\ zacząć {macierz} {k \ wybierz m} \ koniec {macierz}}}$${\ Displaystyle {\ zacząć {macierz} {k \ wybierz m} = 0 \ koniec {macierz}}}$

${\ Displaystyle {\ Frac {\ częściowy} {\ częściowy u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ Frac {1} {1-z}} \ suma _ { k\geq m}{k \wybierz 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 otrzymujemy, że prawdopodobieństwo, że elementy Q znajdują się w tym samym cyklu wynosi

${\ Displaystyle {n \ wybierz m} ^ {-1} [z ^ {n}] {\ Frac {1} {m}} {\ Frac {z ^ {m}} {(1-z) ^ {m +1}}}={n \wybierz 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 są 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 permutacyjne. (Sprawdź tę stronę, aby uzyskać wyjaśnienie, w jaki sposób obliczane są operatory, których będziemy używać.) Na przykład zbiór permutacji zawierających parzystą liczbę cykli parzystych jest podany przez

${\displaystyle \operator {SET} (\operator {CYC} _{\operator {nieparzysty}}}({\mathcal {Z}}))\operator {SET} _{\operator {parzyste}}(\operator {CYC } _{\nazwa operatora {parzyste} }({\mathcal {Z}})).}$

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

${\ Displaystyle \ exp \ lewo ({\ Frac {1} {2}} \ log {\ Frac {1 + Z} {1-z}} \ prawo) \ cosh \ lewo ({\ 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).}$

Upraszcza to

${\ Displaystyle {\ Frac {1} {2}} \ exp \ lewo ({\ Frac {1} {2}} \ log {\ Frac {1} {(1-z) ^ {2}}} \ prawej) )+{\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}}.}$

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

Permutacje, które są kwadratami

Zastanów się, co się dzieje, gdy poddajemy permutację do kwadratu. Punkty stałe są mapowane na punkty stałe. Nieparzyste cykle są mapowane na nieparzyste cykle w korespondencji jeden do jednego, np. zamienia się w . Parzyste cykle dzielą się na dwie części i tworzą parę cykli o połowę mniejszych od oryginalnego cyklu, np. zamienia się w . 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. ${\displaystyle (1\;8\;9\;11\;13)}$${\displaystyle (1\;9\;13\;8\;11)}$${\displaystyle (5\;13\;6\;9)}$${\displaystyle (5\;6)\;(9\;13)}$

${\displaystyle \operator {SET} (\operator {CYC} _{\operator {nieparzysty}}}({\mathcal {Z}}))\operator {SET} _{\operator {parzyste}}(\operator {CYC } _{=2}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {parzyste} }(\operatorname {CYC} _{=4}({\mathcal {Z}})) \operatorname {SET} _{\operatorname {parzyste} }(\operatorname {CYC} _{=6}({\mathcal {Z}}))\cdots }$

która daje EFG

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

Niezmienniki cyklu nieparzystego

Rodzaje permutacji przedstawione w poprzednich dwóch rozdziałach, tj. permutacje zawierające parzystą liczbę cykli parzystych oraz permutacje będące kwadratami, są przykładami tzw. nieparzystych niezmienników cykli , badanych przez Sung i Zhang (patrz linki zewnętrzne ). Termin niezmiennik cyklu nieparzystego oznacza po prostu, że członkostwo w odpowiedniej klasie kombinatorycznej jest niezależne 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 \operator {SET} (\operator {CYC} _{\operator {nieparzysty}}}({\mathcal {Z}}))\left (\operator {SET} _ {=3}(\operator {CYC) } _{=2}({\mathcal {Z}}))+\operatorname {CYC} _{=2}({\mathcal {Z}})\operatorname {CYC} _{=4}({\mathcal {Z}})+\nazwa operatora {CYC} _{=6}({\mathcal {Z}})\right)}$

i funkcja generowania

${\ 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,425250,4677750,46777500,608107500,\ldots}$

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

Ta klasa ma specyfikację

${\displaystyle \operator {SET} (\operator {CYC} _{\operator {nieparzysty}}}({\mathcal {Z}}))\left (\operator {SET} _{\geq 1}(\operator { 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 generowania

${\ 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 niuans semantyczny. Moglibyśmy uznać permutacje nie zawierające parzystych cykli jako 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 \ nazwa operatora {ZESTAW} (\ nazwa operatora {CYC} _ {\ nazwa operatora {nieparzysty} } ({\ mathcal {Z}})) \ nazwa operatora {ZESTAW} (\ nazwa operatora {CYC} _ {= 2} ({ \mathcal {Z}})+\operatorname {CYC} _{=4}({\mathcal {Z}}))}$

i funkcja generowania

${\ 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,257040,2207520,24282720,258128640,\ldots}$

Nawrót

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

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

gdzie jest funkcja parzysta. To znaczy że ${\ Displaystyle h (z)}$

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

też jest parzysty, a co za tym idzie

${\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 i wydobywając współczynniki, stwierdzamy, że ${\ Displaystyle g_ {n} = [z ^ {n}] g (z)}$

${\ Displaystyle {\ Frac {g_ {2 m + 1}} {(2 m + 1)!}} - {\ Frac {g_ {2 m}} {(2 m)!}} = - {\ Frac {g_ {2 m + 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 nawrót

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

Problem z konkursu Putnam 2005

Link do strony internetowej konkursu Putnam pojawia się w sekcji Linki zewnętrzne . Problem prosi o dowód, że

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

gdzie suma jest nad wszystkimi permutacjami , jest znakiem , tj. jeśli jest parzysta i jeśli jest nieparzysta, i jest liczbą stałych punktów . ${\displaystyle n!}$${\displaystyle [n]}$${\displaystyle \sigma (\pi)}$${\displaystyle \pi}$${\ Displaystyle \ sigma (\ pi) = 1}$${\displaystyle \pi}$${\ Displaystyle \ sigma (\ pi) = -1}$${\displaystyle \pi}$${\displaystyle \nu (\pi)}$${\displaystyle \pi}$

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

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

gdy produkt jest produktem w stosunku do wszystkich cykli c z , jak to opisano na przykład na stronach od parzystych i nieparzystych permutacji . ${\displaystyle \pi}$

Stąd bierzemy pod uwagę 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}\nazwa operatora {CYC} _{=4}({\mathcal {Z}})+\cdots )}$

gdzie oznacza jeden minus długość cyklu składowego i oznacza punkty stałe. Przekładając na generowanie funkcji, otrzymujemy ${\ Displaystyle {\ Mathcal {U}}}$${\displaystyle {\mathcal {V}}}$

${\ Displaystyle g (z, u, v) = \ exp \ lewo (-z + vz + \ suma _ {k \ geq 1} u ^ {k-1} {\ Frac {z ^ {k}} {k} }\dobrze)}$

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 )}}$

i stąd pożądana ilość jest podana 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) \ lewo ({\ Frac {1} {z}} \ exp (z)-{\frac {1}{z}}\prawo)}$

lub

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

Wyodrębniając współczynniki, okazuje się, że współczynnik wynosi zero. Stała to jeden, co nie zgadza się ze wzorem (powinno wynosić zero). Za pozytywne jednak otrzymujemy ${\displaystyle 1/z}$${\ Displaystyle n}$

${\ Displaystyle n! [z ^ {n}] \ lewo (- \ exp (-z) - {\ Frac {1} {z}} \ exp (- Z) \ prawo) = 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}} \ prawej) = (-1) ^ {n + 1} {\ Frac {n} {n+1}},}$

co jest pożądanym rezultatem.

Jako ciekawostkę bok, widzimy, że mogą być wykorzystane do oceny następujące wyznacznik danego matrycy: ${\displaystyle g(z,u,v)}$${\displaystyle n\razy n}$

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

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

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

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

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

co daje

${\ Displaystyle b ^ {n} \ po lewej ({\ Frac {ab} {b}} \ po prawej) ^ {n} + b ^ {n} n \ po lewej ({\ Frac {ab} {b}} \ po prawej )^{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 permutacjach parzystych i nieparzystych

Tutaj staramy się pokazać, że tę różnicę podaje

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

Przypomnijmy, że znak permutacji jest podany przez ${\displaystyle \sigma (\pi)}$${\displaystyle \pi}$

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

gdzie produkt mieści się w zakresie cykli c od składu rozłącznego cyklu . ${\displaystyle \pi}$

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

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

gdzie używaliśmy do oznaczania znaków i liczenia cykli. ${\ Displaystyle {\ Mathcal {U}}}$${\displaystyle {\mathcal {V}}}$

Przekładając na funkcje generowania, które 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 \prawo).}$

Upraszcza to

${\ 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 oraz parzyste i nieparzyste permutacje według liczby cykli są podane przez ${\displaystyle Q_{1}(z,v)}$${\displaystyle Q_{2}(z,v)}$

${\ 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}}$

oraz

${\ 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}} \ po prawej) ^ {-v} \ po prawej | _ {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}}.}$

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

${\ Displaystyle -n! [z ^ {n}] (1 + z) \ log {\ Frac {1} {1 + z}} = - n! \ lewo ({\ 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}} \ prawej) = 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)!}$

Na tym kończy się dowód.

Zobacz też

• Stała Golomba-Dickmana

Bibliografia

Linki zewnętrzne

• Panholzer, Alois; Prodinger, Helmut; Riedla, Marko. „Pomiar zaburzeń post-quickselect” (PDF) . Cytowanie dziennika wymaga |journal=( pomoc )
• Archiwum konkursu Williama Lowella Putnama
• Śpiewał Filip; Zhang, Yan. „Powtarzające się nawroty w liczeniach permutacji”. CiteSeerX  10.1.1.91.1088 . Cytowanie dziennika wymaga |journal=( pomoc )
• Marko Riedel i in., Różnica liczby cykli permutacji parzystych i nieparzystych
• Marko Riedel i in., Klucze w zamkniętych pudełkach, pytanie o prawdopodobieństwo

100 więźniów

• Anna Gál, Peter Bro Miltersen, Złożoność sondy komórkowej w zwięzłych strukturach danych
• Różni autorzy, Permutacje z cyklem > n/2
• Różni autorzy, Własność derangements
• Różni autorzy, Oczekiwana liczba punktów stałych
• Peter Winkler, Siedem łamigłówek, o których myślisz, że nie słyszałeś poprawnie
• Różni autorzy, Les-Mathematiques.net . Cent więźniowie (po francusku)