Statistiky náhodné permutace - Random permutation statistics

tento článek případně obsahuje původní výzkum. Prosím vylepši to podle ověřování vznesené nároky a přidání vložené citace. Výroky sestávající pouze z původního výzkumu by měly být odstraněny. (Červenec 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The statistika náhodných permutací, tak jako struktura cyklu a náhodná obměna mají zásadní význam v EU analýza algoritmů, zejména třídicích algoritmů, které fungují na náhodných permutacích. Předpokládejme například, že používáme rychlý výběr (bratranec quicksort ) pro výběr náhodného prvku náhodné permutace. Quickselect provede částečné třídění na poli, protože rozděluje pole podle pivot. Po provedení rychlého výběru bude tedy permutace méně narušená. Množství poruchy, které přetrvává, lze analyzovat pomocí generujících funkcí. Tyto generující funkce závisí zásadním způsobem na generujících funkcích statistik náhodné permutace. Proto je životně důležité vypočítat tyto generující funkce.

Článek o náhodné obměny obsahuje úvod do náhodných permutací.

Základní vztah

Permutace jsou sady označených cyklů. Pomocí označeného pouzdra Flajolet – Sedgewickova základní věta a psaní ${displaystyle scriptstyle {mathcal {P}}}$ pro soubor permutací a ${displaystyle scriptstyle {mathcal {Z}}}$ pro singletonovou sadu máme

${displaystyle operatorname {SET} (operatorname {CYC} ({mathcal {Z}})) = {mathcal {P}}.}$

Překlad do exponenciální generující funkce (EFG), máme

${displaystyle exp log {frac {1} {1-z}} = {frac {1} {1-z}}}$

kde jsme využili skutečnost, že EGF kombinatorické druhy permutací (existují n! obměny n prvků) je

${displaystyle sum _ {ngeq 0} {frac {n!} {n!}} z ^ {n} = {frac {1} {1-z}}.}$

Tato jedna rovnice umožňuje odvodit velké množství statistik permutací. Nejprve zrušením podmínek z ${displaystyle scriptstyle operatorname {SET}}$, tj. exp, můžeme omezit počet cyklů že permutace obsahuje, např. omezením EFG na ${displaystyle scriptstyle operatorname {SET} _ {2}}$ získáme permutace obsahující dva cykly. Zadruhé si povšimněte, že EGF značených cyklů, tj ${displaystyle scriptstyle operatorname {CYC} ({mathcal {Z}})}$, je

${displaystyle log {frac {1} {1-z}} = součet _ {kgeq 1} {frac {z ^ {k}} {k}}}$

protože tam jsou k! / k označené cykly. To znamená, že vypuštěním výrazů z této generující funkce můžeme omezit velikost cyklů které se vyskytují v permutaci a získají EGF permutací obsahujících pouze cykly dané velikosti.

Místo odebírání a výběru cyklů lze také dávat různé váhy různým velikostem cyklů. Li ${displaystyle b: mathbb {N} ightarrow mathbb {R}}$ je váhová funkce, která závisí pouze na velikosti k cyklu a pro stručnost píšeme

${displaystyle b (sigma) = součet _ {cin sigma} b (c),}$

definování hodnoty b pro obměnu ${displaystyle sigma}$ být součtem jeho hodnot na cyklech, pak můžeme označit cykly délky k s u^b(k) a získat funkci generování dvou proměnných

${displaystyle g (z, u) = 1 + součet _ {ngeq 1} vlevo (součet _ {sigma v S_ {n}} u ^ {b (sigma)} ight) {frac {z ^ {n}} {n !}} = exp sum _ {kgeq 1} u ^ {b (k)} {frac {z ^ {k}} {k}}}$

Toto je "smíšená" generující funkce: je to exponenciální generující funkce v z a obyčejná generující funkce v sekundárním parametru u. Diferenciace a hodnocení na u = 1, máme

${displaystyle {frac {částečné} {částečné u}} g (z, u) {Bigg |} _ {u = 1} = {frac {1} {1-z}} součet _ {kgeq 1} b (k) {frac {z ^ {k}} {k}} = součet _ {ngeq 1} vlevo (součet _ {sigma v S_ {n}} b (sigma) ight) {frac {z ^ {n}} {n! }}}$

To je funkce generující pravděpodobnost očekávání b. Jinými slovy, koeficient ${displaystyle z ^ {n}}$ v této výkonové řadě je očekávaná hodnota b o permutacích v ${displaystyle S_ {n}}$, vzhledem k tomu, že každá permutace je zvolena se stejnou pravděpodobností ${displaystyle 1 / n!}$.

Tento článek používá operátor extrakce koeficientů [zⁿ], zdokumentováno na stránce pro formální mocenské řady.

Počet permutací, které jsou involucemi

An involuce je permutace σ, takže σ² = 1 při permutačním složení. Z toho vyplývá, že σ může obsahovat pouze cykly o délce jednoho nebo dvou, tj exponenciální generující funkce G(z) těchto permutací je^[1]

${displaystyle g (z) = exp left (z + {frac {1} {2}} z ^ {2} ight).}$

To dává explicitní vzorec pro celkový počet ${displaystyle I (n)}$ involucí mezi permutacemi σ ∈S_n:^[1]

${displaystyle I (n) = n! [z ^ {n}] g (z) = n! součet _ {a + 2b = n} {frac {1} {a!; 2 ^ {b}; b!} } = n! součet _ {b = 0} ^ {lfloor n / 2floor} {frac {1} {(n-2b) !; 2 ^ {b}; b!}}.}$

Dělení n! poskytuje pravděpodobnost, že náhodná permutace je involuce. Tato čísla jsou známá jako telefonní čísla.

Počet permutací, které jsou mth kořeny jednoty

Tím se zobecňuje pojem involuce. An mth kořen jednoty je permutace σ, takže σ^m = 1 v permutačním složení. Nyní pokaždé, když použijeme σ, se pohybujeme paralelně o jeden krok ve všech jeho cyklech. Cyklus délky d aplikovaný d times vytvoří permutaci identity d elementy (d pevné body) a d je nejmenší hodnota. Proto m musí být násobkem všech velikostí cyklu d, tj. jediné možné cykly jsou ty, jejichž délka d je dělitel m. Z toho vyplývá, že EFG G(X) těchto permutací je

${displaystyle g (z) = exp left (sum _ {dmid m} {frac {z ^ {d}} {d}} v pořádku).}$

Když m = str, kde str je hlavní, tím se zjednodušuje

${displaystyle n! [z ^ {n}] g (z) = n! součet _ {a + pb = n} {frac {1} {a!; p ^ {b}; b!}} = n! součet _ {b = 0} ^ {lfloor n / pfloor} {frac {1} {(n-pb) !; p ^ {b}; b!}}.}$

Počet permutací objednávky přesně k

Toho lze dosáhnout pomocí Möbiova inverze. Při práci se stejným konceptem jako v předchozím vstupu si povšimneme kombinatorických druhů ${displaystyle {mathcal {Q}}}$ permutací, jejichž pořadí se dělí k darováno

${displaystyle {mathcal {Q}} = operatorname {SET} vlevo (součet _ {dmid k} operatorname {CYC} _ {= d} ({mathcal {Z}}) vpravo).}$

Překladem na exponenciální generující funkce získáme EGF permutací, jejichž pořadí se dělí k, který je

${displaystyle Q_ {k} (z) = exp vlevo (součet _ {dmid k} {frac {z ^ {d}} {d}} vpravo).}$

Nyní můžeme použít tuto generující funkci k přesnému výpočtu permutací řádu k. Nechat ${displaystyle p_ {n, d}}$ být počet permutací na n jehož pořadí je přesně d a ${displaystyle q_ {n, k}}$ počet permutací na n počet permutací, jejichž pořadí se dělí k. Pak máme

${displaystyle sum _ {d | k} p_ {n, d} = q_ {n, k}.}$

Z toho vyplývá Möbiova inverze že

${displaystyle sum _ {d | k} q_ {n, d} imes mu (k / d) = p_ {n, k}.}$

Proto máme EGF

${displaystyle Q (z) = součet _ {dmid k} mu (k / d) imes Q_ {d} (z) = součet _ {dmid k} mu (k / d) exp vlevo (součet _ {mmid d} { frac {z ^ {m}} {m}} ight).}$

Požadovaný počet je pak dán vztahem

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

Tento vzorec produkuje např. pro k = 6 EGF

${displaystyle Q (z) = {m {e}} ^ {z} - {m {e}} ^ {z + 1/2, z ^ {2}} - {m {e}} ^ {z + 1 / 3, z ^ {3}} + {m {e}} ^ {z + 1/2, z ^ {2} + 1/3, z ^ {3} + 1/6, z ^ {6}} }$

s posloupností hodnot začínajících na n = 5

${displaystyle 20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280, ldots}$ (sekvence A061121 v OEIS )

Pro k = 8 dostaneme EGF

${displaystyle Q (z) = - {m {e}} ^ {z + 1/2, z ^ {2} + 1/4, z ^ {4}} + {m {e}} ^ {z + 1 / 2, z ^ {2} + 1/4, z ^ {4} + 1/8, z ^ {8}}}$

s posloupností hodnot začínajících na n = 8

${displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800, ldots}$ (sekvence A061122 v OEIS )

Konečně pro k = 12 dostaneme EGF

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

s posloupností hodnot začínajících na n = 7

${displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600, ldots}$ (sekvence A061125 v OEIS )

Počet permutací, které jsou narušeny

Předpokládejme, že existují n lidé na večírku, z nichž každý přinesl deštník. Na konci večírku si každý vybere ze stohu deštníků a listí deštník. Jaká je pravděpodobnost, že nikdo neodjel se svým vlastním deštníkem? Tento problém je ekvivalentní počítání permutací bez pevných bodů (tzv poruchy ), a tedy EGF, kde odečtením pevných bodů odečteme pevné body z, je

${displaystyle exp left (-z + sum _ {kgeq 1} {frac {z ^ {k}} {k}} ight) = {frac {e ^ {- z}} {1-z}}.}$

Násobení nyní ${displaystyle 1 / (1-z)}$ jen součty koeficientů, takže máme následující vzorec pro ${displaystyle D (n)}$, celkový počet poruch:

${displaystyle D (n) = n! součet _ {k = 0} ^ {n} {frac {(-1) ^ {k}} {k!}}; přibližně; {frac {n!} {e}} .}$

Proto existuje asi ${displaystyle n! / e}$ odchylky a pravděpodobnost, že náhodná permutace je odchylka, je ${displaystyle 1 / e.}$

Tento výsledek může být prokázán také začlenění – vyloučení. Pomocí sad ${displaystyle A_ {p}}$ kde ${displaystyle {egin {matrix} 1leq pleq nend {matrix}}}$ k označení množiny permutací, které opravují str, my máme

${displaystyle left | igcup _ {p} A_ {p} ight | = součet _ {p} vlevo | A_ {p} ight |; -; součet _ {p$

Tento vzorec počítá počet permutací, které mají alespoň jeden pevný bod. Kardinality jsou následující:

${displaystyle left | A_ {p} ight | = (n-1)!;, ;; left | A_ {p} cap A_ {q} ight | = (n-2)!;, ;; left | A_ {p } cap A_ {q} cap A_ {r} ight | = (n-3)!;,; ldots}$

Proto je počet permutací bez pevného bodu

${displaystyle n! ;; - ;; {n vyberte 1} (n-1)! ;; + ;; {n vyberte 2} (n-2)! ;; - ;; {n vyberte 3} (n-3 )! ;; + ;; cdots ;; pm ;; {n zvolit n} (nn)!}$

nebo

${displaystyle n! left (1- {frac {1} {1!}} + {frac {1} {2!}} - {frac {1} {3!}} + cdots pm {frac {1} {n !}} ight) = n! součet _ {k = 0} ^ {n} {frac {(-1) ^ {k}} {k!}}}$

a máme nárok.

Existuje zobecnění těchto čísel, které je známé jako obnovuje čísla, tj. číslo ${displaystyle D (n, m)}$ permutací z ${displaystyle [n]}$ obsahující m pevné body. Odpovídající EGF se získá označením cyklů velikosti jedna proměnnou u, tj. výběr b(k) rovno jedné pro ${displaystyle k = 1}$ a jinak nula, která poskytuje generující funkci ${displaystyle g (z, u)}$ množiny permutací počtem pevných bodů:

${displaystyle g (z, u) = exp left (-z + uz + sum _ {kgeq 1} {frac {z ^ {k}} {k}} ight) = {frac {e ^ {- z}} { 1-z}} e ^ {uz}.}$

Z toho vyplývá, že

${displaystyle [u ^ {m}] g (z, u) = {frac {e ^ {- z}} {1-z}} {frac {z ^ {m}} {m!}}}$

a tudíž

${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!}} součet _ {k = 0} ^ {nm} {frac {(-1) ^ {k} } {k!}}.}$

To okamžitě naznačuje

${displaystyle D (n, m) = {n zvolte m} D (nm, 0) ;; {ext {and}} ;; {frac {D (n, m)} {n!}} cca {frac {e ^ {- 1}} {m!}}}$

pro n velký, m pevný.

Pořadí náhodné permutace

Li P je obměna, objednat z P je nejmenší kladné celé číslo n pro který ${displaystyle P ^ {n}}$ je permutace identity. Toto je nejméně běžný násobek délek cyklů P.

Věta o Gohovi a Schmutzovi^[2]uvádí, že pokud ${displaystyle mu _ {n}}$ je očekávané pořadí náhodné permutace velikosti n, pak

${displaystyle log mu _ {n} sim c {sqrt {frac {n} {log n}}}}$

kde konstanta C je

${displaystyle 2 {sqrt {2int _ {0} ^ {infty} log log left ({frac {e} {1-e ^ {- t}}} ight) dt}} přibližně 1,1178641511899}$

Odchylky obsahující sudý a lichý počet cyklů

K výpočtu počtu odchylek můžeme použít stejnou konstrukci jako v předchozí části ${displaystyle D_ {0} (n)}$ obsahující sudý počet cyklů a počet ${displaystyle D_ {1} (n)}$ obsahující lichý počet cyklů. K tomu musíme označit všechny cykly a odečíst pevné body, dávat

${displaystyle g (z, u) = exp left (-uz + ulog {frac {1} {1-z}} ight) = exp (-uz) left ({frac {1} {1-z}} ight) ^ {u}.}$

Nyní některé velmi základní úvahy ukazují, že EGF ${displaystyle q (z)}$ z ${displaystyle D_ {0} (n)}$ darováno

${displaystyle q (z) = {frac {1} {2}} imes g (z, -1) + {frac {1} {2}} imes g (z, 1) = {frac {1} {2} } exp (-z) {frac {1} {1-z}} + {frac {1} {2}} exp (z) (1-z).}$

Máme tedy

${displaystyle D_ {0} (n) = n! [z ^ {n}] q (z) = {frac {1} {2}} n! součet _ {k = 0} ^ {n} {frac {( -1) ^ {k}} {k!}} + {Frac {1} {2}} n! {Frac {1} {n!}} - {frac {1} {2}} n! {Frac { 1} {(n-1)!}}}$

který je

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

Odečítání ${displaystyle D_ {0} (n)}$ z ${displaystyle D (n)}$, shledáváme

${displaystyle D_ {1} (n) = {frac {1} {2}} n! součet _ {k = 0} ^ {n} {frac {(-1) ^ {k}} {k!}} - {frac {1} {2}} (1-n).}$

Rozdíl mezi těmito dvěma (${displaystyle D_ {0} (n)}$ a ${displaystyle D_ {1} (n)}$) je ${displaystyle n-1.}$

Sto vězňů

Vězeňský dozorce chce ve své věznici uvolnit místo a uvažuje o osvobození sto vězňů, čímž uvolní sto cel. Shromáždí proto sto vězňů a požádá je, aby hráli následující hru: seřadí sto uren v řadě, každá obsahuje jméno jednoho vězně, kde se jméno každého vězně vyskytuje přesně jednou. Hra se hraje následovně: každý vězeň může nahlédnout do padesáti uren. Pokud nenajde své jméno v jedné z padesáti uren, budou okamžitě popraveni všichni vězni, jinak hra pokračuje. Vězni mají několik okamžiků, aby se rozhodli pro strategii, protože věděli, že jakmile hra začne, nebudou moci spolu komunikovat, žádným způsobem označovat urny nebo přesouvat urny nebo jména uvnitř. Při náhodném výběru urny je jejich šance na přežití téměř nulová, ale existuje strategie, která jim dává 30% šanci na přežití, za předpokladu, že jména jsou urnám přiřazena náhodně - co to je?

Nejprve je pravděpodobnost přežití pomocí náhodných voleb

${displaystyle left ({frac {99 choose 49} {100 choose 50}} ight) ^ {100} = {frac {1} {2 ^ {100}}},}$

to tedy rozhodně není praktická strategie.

Strategií 30% přežití je považovat obsah uren za permutaci vězňů a cykly procházení. Aby byl zápis jednoduchý, přiřaďte každému vězni číslo, například seřazením jeho jmen podle abecedy. Urny mohou být poté považovány za obsahující spíše čísla než jména. Nyní obsah urn jasně definuje permutaci. První vězeň otevře první urnu. Pokud najde své jméno, skončil a přežil. Jinak otevře urnu s číslem, které našel v první urně. Proces se opakuje: vězeň otevře urnu a přežije, pokud najde své jméno, jinak otevře urnu s právě načteným číslem, a to až do limitu padesáti uren. Druhý vězeň začíná s urnou číslo dva, třetí s urnou číslo tři atd. Tato strategie je přesně ekvivalentní průchodu cyklů permutace představovaných urnami. Každý vězeň začíná s urnou, která nese jeho číslo, a pokračuje ve svém cyklu až do limitu padesáti uren. Číslo urny, která obsahuje jeho číslo, je předobrazem tohoto čísla pod permutací. Vězni tedy přežijí, pokud všechny cykly obměny obsahují maximálně padesát prvků. Musíme ukázat, že tato pravděpodobnost je nejméně 30%.

Všimněte si, že to předpokládá, že dozorce volí permutaci náhodně; pokud dozorce předvídá tuto strategii, může jednoduše zvolit permutaci s cyklem délky 51. Aby to překonali, mohou se vězni předem dohodnout na náhodném obměně jejich jmen.

Zvažujeme obecný případ ${displaystyle 2n}$ vězni a ${displaystyle n}$ otevírání uren. Nejprve spočítáme doplňkovou pravděpodobnost, tj. Že existuje cyklus větší než ${displaystyle n}$ elementy. S ohledem na tuto skutečnost vám představujeme

${displaystyle g (z, u) = exp left (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 ight)}$

nebo

${displaystyle {frac {1} {1-z}} exp left ((u-1) left ({frac {z ^ {n + 1}} {n + 1}} + {frac {z ^ {n + 2 }} {n + 2}} + cdots ight) ight),}$

takže požadovaná pravděpodobnost je

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

protože cyklus více než ${displaystyle n}$ prvky budou nutně jedinečné. S využitím toho, že ${displaystyle 2 (n + 1)> 2n}$, zjistíme, že

${displaystyle [z ^ {2n}] [u] g (z, u) = [z ^ {2n}] [u] {frac {1} {1-z}} vlevo (1+ (u-1) vlevo ({frac {z ^ {n + 1}} {n + 1}} + {frac {z ^ {n + 2}} {n + 2}} + cdots ight) ight),}$

který přináší

${displaystyle [z ^ {2n}] [u] g (z, u) = [z ^ {2n}] {frac {1} {1-z}} vlevo ({frac {z ^ {n + 1}} {n + 1}} + {frac {z ^ {n + 2}} {n + 2}} + cdots ight) = součet _ {k = n + 1} ^ {2n} {frac {1} {k} } = H_ {2n} -H_ {n}.}$

Nakonec pomocí integrálního odhadu, jako je Součet Euler – Maclaurin nebo asymptotická expanze nth harmonické číslo, získáváme

${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) 1-log 2 = 0,30685281,}$

nebo alespoň 30%, jak je uvedeno.

Souvisejícím výsledkem je, že asymptoticky je očekávaná délka nejdelšího cyklu λn, kde λ je Konstanta Golomb – Dickman, přibližně 0,62.

Tento příklad si zaslouží Anna Gál a Peter Bro Miltersen; další informace najdete v příspěvku Petera Winklera a viz diskuse na Les-Mathematiques.net.Poraďte se s odkazy na 100 vězňů odkazy na tyto reference.

Výše uvedený výpočet lze provést jednodušším a přímým způsobem, a to následovně: nejprve si povšimněte, že permutace ${displaystyle 2n}$ prvky obsahuje maximálně jeden cyklus délky striktně větší než ${displaystyle n}$ . Pokud tedy označíme

${displaystyle p_ {k} = Pr [{mbox {existuje cyklus délky}} k],}$

pak

${displaystyle Pr [{mbox {existuje cyklus délky}}> n] = součet _ {k = n + 1} ^ {2n} p_ {k}.}$

Pro ${displaystyle k> n}$, počet permutací, které obsahují přesně cyklus délky ${displaystyle k}$ je

${displaystyle {{2n} vyberte k} cdot {frac {k!} {k}} cdot (2n-k) !.}$

Vysvětlení:${displaystyle {{2n} vyberte k}}$ je počet způsobů výběru ${displaystyle k}$ prvky, které tvoří cyklus;${displaystyle {frac {k!} {k}}}$ je počet způsobů uspořádání ${displaystyle k}$ položky v cyklu; a ${displaystyle (2n-k)!}$ je počet způsobů, jak permutovat zbývající prvky. Neexistuje zde žádné dvojí započítání, protože existuje maximálně jeden cyklus délky ${displaystyle k}$ když ${displaystyle k> n}$. Tím pádem,

${displaystyle p_ {k} = {frac {{{{2n} vyberte k} cdot {frac {k!} {k}} cdot (2n-k)!} {(2n)!}} = {frac {1} { k}}.}$

Došli jsme k závěru, že

${displaystyle Pr [{mbox {existuje cyklus délky}}> n] = součet _ {k = n + 1} ^ {2n} {frac {1} {k}} = H_ {2n} -H_ {n }.}$

Variace na problém 100 vězňů (klíče a krabice)

Existuje zde úzce související problém, který docela dobře odpovídá zde představené metodě. Řekněme, že máte n objednané krabice. Každé pole obsahuje klíč k nějaké jiné schránce nebo případně k samotné, která poskytuje permutaci klíčů. Máte povoleno vybrat k z nich n polí najednou a rozbijte je současně, abyste získali přístup k k klíče. Jaká je pravděpodobnost, že pomocí těchto klíčů můžete otevřít všechny n polí, kde pomocí nalezeného klíče otevřete pole, ke kterému patří, a opakujte.

Matematické vyjádření tohoto problému je následující: vyberte náhodnou permutaci n prvky a k hodnoty z rozsahu 1 na n, také náhodně, zavolejte tyto značky. Jaká je pravděpodobnost, že v každém cyklu permutace je alespoň jedna značka? Tvrzení je tato pravděpodobnost je k / n.

Druh ${displaystyle {mathcal {Q}}}$ permutačních cyklů s nějakou neprázdnou podmnožinou každého označovaného cyklu má specifikaci

${displaystyle {mathcal {Q}} = operatorname {SET} left (sum _ {qgeq 1} operatorname {CYC} _ {= q} ({mathcal {Z}}) imes sum _ {p = 1} ^ {q} {q zvolte p} {mathcal {U}} ^ {p} ight).}$

Index ve vnitřním součtu začíná na jedné, protože v každém cyklu musíme mít alespoň značku.

Přeložením specifikace na generující funkce získáme funkci bivariate generující

${displaystyle G (z, u) = exp vlevo (součet _ {qgeq 1} {frac {z ^ {q}} {q}} součet _ {p = 1} ^ {q} {q vyberte p} u ^ { p} hned).}$

To se zjednodušuje na

${displaystyle exp left (sum _ {qgeq 1} {frac {z ^ {q}} {q}} (u + 1) ^ {q} -sum _ {qgeq 1} {frac {z ^ {q}} { q}} hned)}$

nebo

${displaystyle exp left (log {frac {1} {1- (u + 1) z}} - log {frac {1} {1-z}} ight) = {frac {1-z} {1- (u +1) z}}.}$

Aby bylo možné extrahovat koeficienty z tohoto přepisování, takhle

${displaystyle (1-z) součet _ {qgeq 0} (u + 1) ^ {q} z ^ {q}.}$

Z toho nyní vyplývá

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

a tudíž

${displaystyle [u ^ {k}] [z ^ {n}] G (z, u) = {n zvolte k} - {n-1 vyberte k}.}$

Rozdělte ${displaystyle {n vyberte k}}$ získat

${displaystyle 1- {frac {(n-1)!} {k! (n-1-k)!}} {frac {k! (nk)!} {n!}} = 1- {frac {nk} {n}} = {frac {k} {n}}.}$

Nepotřebujeme dělit n! protože ${displaystyle G (z, u)}$ je exponenciální v z.

Počet permutací obsahujících m cykly

Uplatnění Flajolet – Sedgewickova základní věta, tj. označená věta o výčtu s ${displaystyle G = S_ {m}}$, do sady

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

získáme generující funkci

${displaystyle g_ {m} (z) = {frac {1} {| S_ {m} |}} vlevo (log {frac {1} {1-z}} ight) ^ {m} = {frac {1} {m!}} vlevo (přihlásit {frac {1} {1-z}} vpravo) ^ {m}.}$

Termín

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

dává podepsané Stirlingova čísla prvního druhu, a ${displaystyle g_ {m} (z)}$ je EGF nepodepsaných Stirlingových čísel prvního druhu, tj.

${displaystyle n! [z ^ {n}] g_ {m} (z) = left [{egin {matrix} n mend {matrix}} right].}$

Můžeme vypočítat OGF podepsaných Stirlingových čísel pro n pevné, tj.

${displaystyle s_ {n} (w) = součet _ {m = 0} ^ {n} s (n, m) w ^ {m}.}$

Začít s

${displaystyle g_ {m} (z) = součet _ {ngeq m} {frac {(-1) ^ {n + m}} {n!}} s (n, m) z ^ {n}}$

který přináší

${displaystyle (-1) ^ {m} g_ {m} (z) w ^ {m} = součet _ {ngeq m} {frac {(-1) ^ {n}} {n!}} s (n, m) w ^ {m} z ^ {n}.}$

Když to shrneme, získáme to

${displaystyle sum _ {mgeq 0} (- 1) ^ {m} g_ {m} (z) w ^ {m} = součet _ {mgeq 0} součet _ {ngeq m} {frac {(-1) ^ { n}} {n!}} s (n, m) w ^ {m} z ^ {n} = součet _ {ngeq 0} {frac {(-1) ^ {n}} {n!}} z ^ {n} součet _ {m = 0} ^ {n} s (n, m) w ^ {m}.}$

Použití vzorce zahrnujícího logaritmus pro ${displaystyle g_ {m} (z)}$ vlevo definice ${displaystyle s_ {n} (w)}$ napravo a binomická věta, získáváme

${displaystyle (1-z) ^ {w} = součet _ {ngeq 0} {w zvolit n} (- 1) ^ {n} z ^ {n} = součet _ {ngeq 0} {frac {(-1) ^ {n}} {n!}} s_ {n} (w) z ^ {n}.}$

Porovnání koeficientů ${displaystyle z ^ {n}}$a za použití definice binomický koeficient, konečně máme

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

A klesající faktoriál. Výpočet OGF nepodepsaných Stirlingových čísel prvního druhu funguje podobným způsobem.

Očekávaný počet cyklů dané velikosti m

V tomto problému používáme funkci generování bivariate G(z, u), jak je popsáno v úvodu. Hodnota b pro cyklus, který nemá velikost m je nula a jedna pro cyklus velikosti m. My máme

${displaystyle {frac {částečné} {částečné u}} g (z, u) {Bigg |} _ {u = 1} = {frac {1} {1-z}} součet _ {kgeq 1} b (k) {frac {z ^ {k}} {k}} = {frac {1} {1-z}} {frac {z ^ {m}} {m}}}$

nebo

${displaystyle {frac {1} {m}} z ^ {m}; +; {frac {1} {m}} z ^ {m + 1}; +; {frac {1} {m}} z ^ { m + 2}; +; cdots}$

To znamená, že očekávaný počet cyklů velikosti m v permutaci délky n méně než m je nula (samozřejmě). Minimálně náhodná permutace m obsahuje v průměru 1 /m cykly délky m. Zejména náhodná permutace obsahuje přibližně jeden pevný bod.

OGF očekávaného počtu cyklů o délce menší nebo rovné m je tedy

${displaystyle {frac {1} {1-z}} součet _ {k = 1} ^ {m} {frac {z ^ {k}} {k}} {mbox {and}} [z ^ {n}] {frac {1} {1-z}} součet _ {k = 1} ^ {m} {frac {z ^ {k}} {k}} = H_ {m} {mbox {for}} ngeq m}$

kde H_m je mth harmonické číslo. Proto je očekávaný maximální počet cyklů délky m v náhodné permutaci je asi lnm.

Okamžiky pevných bodů

Smíšený GF ${displaystyle g (z, u)}$ množiny permutací počtem pevných bodů je

${displaystyle g (z, u) = exp left (-z + uz + log {frac {1} {1-z}} ight) = {frac {1} {1-z}} exp (-z + uz) .}$

Nechte náhodnou proměnnou X být počet pevných bodů náhodné permutace. Použití Stirlingova čísla druhého druhu, máme následující vzorec pro mTřetí okamžik X:

${displaystyle E (X ^ {m}) = Eleft (součet _ {k = 0} ^ {m} vlevo {{egin {matrix} m kend {matrix}} ight} (X) _ {k} ight) = součet _ {k = 0} ^ {m} left {{egin {matrix} m kend {matrix}} ight} E ((X) _ {k}),}$

kde ${displaystyle (X) _ {k}}$ je klesající faktoriál.Použitím ${displaystyle g (z, u)}$, my máme

${displaystyle E ((X) _ {k}) = [z ^ {n}] left ({frac {d} {du}} ight) ^ {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}},}$

což je nula, když ${displaystyle k> n}$a jeden jinak. Proto pouze termíny s ${displaystyle k <= n}$ přispějte k této částce

${displaystyle E (X ^ {m}) = součet _ {k = 0} ^ {n} vlevo {{egin {matrix} m kend {matrix}} vpravo}.}$

Očekávaný počet pevných bodů v náhodné permutaci zvýšený na určitou sílu k

Předpokládejme, že vyberete náhodnou permutaci ${displaystyle sigma}$ a pozvednout to na nějakou moc ${displaystyle k}$, s ${displaystyle k}$ kladné celé číslo a zeptat se na očekávaný počet pevných bodů ve výsledku. Označte tuto hodnotu ${displaystyle E [F_ {k}]}$.

Pro každého dělitele ${displaystyle d}$ z ${displaystyle k}$ cyklus délky ${displaystyle d}$ rozděluje na ${displaystyle d}$ pevné body při zvednutí na sílu ${displaystyle k.}$ Proto musíme tyto cykly označit ${displaystyle u ^ {d}.}$ Pro ilustraci to zvažte ${displaystyle E [F_ {6}].}$

Dostaneme

${displaystyle g (z, u) = 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}} + log {frac {1} {1-z}} ight)}$

který je

${displaystyle {frac {1} {1-z}} exp vlevo (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}} hned).}$

Ještě jednou pokračujeme, jak je popsáno v úvodu, zjistíme

${displaystyle left. {frac {partial} {částečné u}} g (z, u) ight | _ {u = 1} = vlevo. {frac {z + z ^ {2} + z ^ {3} + z ^ {6}} {1-z}} exp vlevo (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}} ight) ight | _ {u = 1}}$

který je

${displaystyle {frac {z + z ^ {2} + z ^ {3} + z ^ {6}} {1-z}}.}$

Závěr je takový ${displaystyle E [F_ {6}] = 4}$ pro ${displaystyle ngeq 6}$ a v průměru existují čtyři pevné body.

Obecný postup je

${displaystyle g (z, u) = exp left (součet _ {dmid k} left (u ^ {d} {frac {z ^ {d}} {d}} - {frac {z ^ {d}} {d }} ight) + log {frac {1} {1-z}} ight) = {frac {1} {1-z}} exp vlevo (součet _ {dmid k} vlevo (u ^ {d} {frac { z ^ {d}} {d}} - {frac {z ^ {d}} {d}} hned) hned)$

Zjistili jsme, že ještě jednou pokračujeme jako předtím

${displaystyle left. {frac {částečné} {částečné u}} g (z, u) ight | _ {u = 1} = vlevo. {frac {sum _ {dmid k} z ^ {d}} {1-z }} exp left (sum _ {dmid k} left (u ^ {d} {frac {z ^ {d}} {d}} - {frac {z ^ {d}} {d}} ight) ight) ight | _ {u = 1} = {frac {sum _ {dmid k} z ^ {d}} {1-z}}.}$

Ukázali jsme, že hodnota ${displaystyle E [F_ {k}]}$ je rovný ${displaystyle au (k)}$ (dále jen počet dělitelů z ${displaystyle k}$) Jakmile ${displaystyle ngeq k.}$ Začíná to na ${displaystyle 1}$ pro ${displaystyle n = 1}$ a pokaždé se zvýší o jednu ${displaystyle n}$ zasáhne dělitele ${displaystyle k}$ až do ${displaystyle k}$ sám.

Očekávaný počet cyklů libovolné délky náhodné permutace

Sestavíme funkci generování bivariate ${displaystyle g (z, u)}$ použitím ${displaystyle b (k)}$, kde ${displaystyle b (k)}$ je jeden pro všechny cykly (každý cyklus přispívá jedním k celkovému počtu cyklů).

Všimněte si, že ${displaystyle g (z, u)}$ má uzavřenou formu

${displaystyle g (z, u) = left ({frac {1} {1-z}} ight) ^ {u}}$

a generuje nepodepsané Stirlingova čísla prvního druhu.

My máme

${displaystyle {frac {částečné} {částečné u}} g (z, u) {Bigg |} _ {u = 1} = {frac {1} {1-z}} součet _ {kgeq 1} b (k) {frac {z ^ {k}} {k}} = {frac {1} {1-z}} součet _ {kgeq 1} {frac {z ^ {k}} {k}} = {frac {1} {1-z}} přihlásit {frac {1} {1-z}}.}$

Očekávaný počet cyklů je tedy harmonické číslo ${displaystyle H_ {n}}$, nebo o ${displaystyle log n}$.

Počet permutací s cyklem délky větším než n/2

(Všimněte si této části Sto vězňů obsahuje přesně stejný problém s velmi podobným výpočtem, plus také jednodušší elementární důkaz.)

Ještě jednou začněte s funkcí exponenciálního generování ${displaystyle g (z, u)}$, tentokrát ve třídě ${displaystyle {mathcal {P}}}$ permutací podle velikosti, kde cykly délky větší než ${displaystyle n / 2}$ jsou označeny proměnnou ${displaystyle u}$:

${displaystyle g (z, u) = exp left (usum _ {k> lfloor {frac {n} {2}} floor} ^ {infty} {frac {z ^ {k}} {k}} + součet _ { k = 1} ^ {lfloor {frac {n} {2}} podlaha} {frac {z ^ {k}} {k}} noc).}$

Může existovat pouze jeden cyklus délky větší než ${displaystyle {frac {n} {2}}}$, proto je odpověď na otázku dána

${displaystyle n! [uz ^ {n}] g (z, u) = n! [z ^ {n}] exp vlevo (součet _ {k = 1} ^ {lfloor {frac {n} {2}} podlaha } {frac {z ^ {k}} {k}} ight) součet _ {k> lfloor {frac {n} {2}} patro} ^ {infty} {frac {z ^ {k}} {k}} }$

nebo

${displaystyle n! [z ^ {n}] exp left (log {frac {1} {1-z}} - součet _ {k> lfloor {frac {n} {2}} podlaha} ^ {infty} {frac {z ^ {k}} {k}} ight) součet _ {k> lfloor {frac {n} {2}} podlaha} ^ {infty} {frac {z ^ {k}} {k}}}$

který je

${displaystyle n! [z ^ {n}] {frac {1} {1-z}} exp vlevo (-sum _ {k> lfloor {frac {n} {2}} podlaha} ^ {infty} {frac { z ^ {k}} {k}} ight) suma _ {k> lfloor {frac {n} {2}} podlaha} ^ {infty} {frac {z ^ {k}} {k}} = n! [ z ^ {n}] {frac {1} {1-z}} součet _ {m = 0} ^ {infty} {frac {(-1) ^ {m}} {m!}} vlevo (součet _ { k> lfloor {frac {n} {2}} patro} ^ {infty} {frac {z ^ {k}} {k}} ight) ^ {m + 1}}$

Exponent exponentu ${displaystyle z}$ v termínu pozvednutí k moci ${displaystyle m + 1}$ je větší než ${displaystyle lfloor {frac {n} {2}} podlaha}$ a tedy žádná hodnota pro ${displaystyle m> 0}$ může případně přispět k ${displaystyle [z ^ {n}].}$

Z toho vyplývá, že odpověď je

${displaystyle n! [z ^ {n}] {frac {1} {1-z}} součet _ {k> lfloor {frac {n} {2}} podlaha} ^ {infty} {frac {z ^ {k }} {k}} = n! součet _ {k = lfloor {frac {n} {2}} patro +1} ^ {n} {frac {1} {k}}.}$

Součet má alternativní zastoupení, se kterým se člověk setká např. v OEIS OEIS: A024167.

${displaystyle sum _ {k = 1} ^ {n} {frac {1} {k}} - součet _ {k = 1} ^ {lfloor {frac {n} {2}} podlaha} {frac {1} { k}} = součet _ {k = 1} ^ {n} {frac {1} {k}} - 2sum _ {k = 1} ^ {lfloor {frac {n} {2}} podlaha} {frac {1 } {2k}} = součet _ {k = 1 na vrcholu k; {ext {even}}} ^ {n} (1-2) {frac {1} {k}} + součet _ {k = 1 na vrcholu k; {ext {odd}}} ^ {n} {frac {1} {k}}}$

konečně dávat

${displaystyle n! sum _ {k = 1} ^ {n} {frac {(-1) ^ {k + 1}} {k}} sim n! log 2.}$

Očekávaný počet transpozic náhodné permutace

Můžeme použít rozklad disjunktního cyklu permutace k jeho faktorizaci jako produktu transpozic nahrazením cyklu délky k podle k - 1 provedení. Např. cyklu ${displaystyle (1; 2; 34)}$ faktory jako ${displaystyle (1; 2); (2; 3); (3; 4)}$. Funkce ${displaystyle b (k)}$ pro cykly se rovná ${displaystyle k-1}$ a získáme

${displaystyle g (z, u) = left ({frac {1} {1-uz}} ight) ^ {1 / u}}$

a

${displaystyle {frac {částečné} {částečné u}} g (z, u) {Bigg |} _ {u = 1} = {frac {1} {1-z}} součet _ {kgeq 1} (k-1 ) {frac {z ^ {k}} {k}} = {frac {z} {(1-z) ^ {2}}} - {frac {1} {1-z}} log {frac {1} {1-z}}.}$

Proto očekávaný počet provedení ${displaystyle T (n)}$ je

${displaystyle T (n) = n-H_ {n}}$

kde ${displaystyle H_ {n}}$ je ${displaystyle n ^ {th}}$ Harmonické číslo Tento vzorec jsme mohli získat také tak, že si všimneme, že počet transpozic se získá přidáním délek všech cyklů (což dává n) a odečtením jednoho pro každý cyklus (což dává ${displaystyle log n}$ podle předchozí části).

Všimněte si, že ${displaystyle g (z, u)}$ opět generuje nepodepsané Stirlingova čísla prvního druhu, ale v opačném pořadí. Přesněji, máme

${displaystyle (-1) ^ {m} n!; [z ^ {n}] [u ^ {m}] g (z, u) = left [{egin {matrix} n n-mend {matrix}} večer]}$

Chcete-li to vidět, nezapomeňte, že výše uvedené je ekvivalentní s

${displaystyle (-1) ^ {n + m} n!; [z ^ {n}] [u ^ {m}] g (z, u) | _ {u = 1 / u} | _ {z = uz } = left [{egin {matrix} n mend {matrix}} right]}$

a to

${displaystyle [u ^ {m}] g (z, u) | _ {u = 1 / u} | _ {z = uz} = [u ^ {m}] vlevo ({frac {1} {1-z }} ight) ^ {u} = {frac {1} {m!}} vlevo (log {frac {1} {1-z}} ight) ^ {m},}$

které jsme viděli jako EGF nepodepsaných Stirlingových čísel prvního druhu v sekci o permutacích sestávajících z přesně m cykly.

Očekávaná velikost cyklu náhodného prvku

Vybereme náhodný prvek q náhodné permutace ${displaystyle sigma}$ a zeptejte se na očekávanou velikost cyklu, který obsahuje q. Zde funkce ${displaystyle b (k)}$ je rovný ${displaystyle k ^ {2}}$, protože cyklus délky k přispívá k prvky, které jsou na délkových cyklech k. Všimněte si, že na rozdíl od předchozích výpočtů musíme tento parametr průměrovat poté, co jej extrahujeme z generující funkce (děleno n). My máme

${displaystyle {frac {částečné} {částečné u}} g (z, u) {Bigg |} _ {u = 1} = {frac {1} {1-z}} součet _ {kgeq 1} k ^ {2 } {frac {z ^ {k}} {k}} = {frac {1} {1-z}} {frac {z} {(1-z) ^ {2}}} = {frac {z} { (1-z) ^ {3}}}.}$