Slumpmässig permutationsstatistik - Random permutation statistics

De statistik av slumpmässiga permutationer , såsom cykelstruktur av en slumpmässig permutation är av grundläggande betydelse i analys av algoritmer , i synnerhet av sorteringsalgoritmer, som arbetar på slumpmässiga permutationer. Antag till exempel att vi använder quickselect (en kusin till quicksort ) för att välja ett slumpmässigt element i en slumpmässig permutation. Quickselect kommer att utföra en partiell sortering på arrayen, eftersom den partitionerar arrayen enligt pivoten. Därför blir en permutation mindre störd efter att quickselect har utförts. Mängden störning som återstår kan analyseras med genererande funktioner. Dessa genereringsfunktioner beror på ett grundläggande sätt på genereringsfunktionerna för statistik över slumpmässig permutation. Därför är det av avgörande betydelse att beräkna dessa genereringsfunktioner.

Artikeln om slumpmässiga permutationer innehåller en introduktion till slumpmässiga permutationer.

Det grundläggande förhållandet

Permutationer är uppsättningar av märkta cykler. Med hjälp av det märkta fallet för Flajolet – Sedgewicks grundläggande sats och skrift för uppsättningen permutationer och för singletonsatsen har vi ${\ displaystyle \ scriptstyle {\ mathcal {P}}}$${\ displaystyle \ scriptstyle {\ mathcal {Z}}}$

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

Vi har översatt till exponentiella genererande funktioner (EGF)

${\ displaystyle \ exp \ left (\ log {\ frac {1} {1-z}} \ right) = {\ frac {1} {1-z}}}$

där vi har använt det faktum att EGF för de kombinatoriska arterna av permutationer (det finns n ! permutationer av n element) är

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

Denna ekvation gör att man kan härleda ett stort antal permutationsstatistik. För det första, genom att släppa termer från , dvs exp, kan vi begränsa antalet cykler som en permutation innehåller, t.ex. genom att begränsa EGF till att vi får permutationer som innehåller två cykler. Notera för det andra att EGF för märkta cykler, dvs av , är ${\ displaystyle \ scriptstyle \ operatorname {SET}}$${\ displaystyle \ scriptstyle \ operatorname {SET} _ {2}}$${\ displaystyle \ scriptstyle \ operatorname {CYC} ({\ mathcal {Z}})}$

${\ displaystyle \ sum _ {k \ geq 1} {\ frac {(k-1)! z^{k}} {k!}} = \ sum _ {k \ geq 1} {\ frac {z^{ k}} {k}} = \ log {\ frac {1} {1-z}}}$

eftersom det finns k!/k -märkta cykler. Detta innebär att genom att släppa termer från denna genereringsfunktion kan vi begränsa storleken på de cykler som uppstår i en permutation och erhålla en EGF för permutationerna som endast innehåller cykler av en given storlek.

Istället för att ta bort och välja cykler kan man också lägga olika vikter på cykler med olika storlekar. If är en viktfunktion som bara beror på cykelns storlek k och för korthet skriver vi ${\ displaystyle b: \ mathbb {N} \ rightarrow \ mathbb {R}}$

${\ displaystyle b (\ sigma) = \ sum _ {c \ in \ sigma} b (c),}$

definiera värdet av b för att en permutation ska vara summan av dess värden på cyklerna, då kan vi markera cykler med längden k med u ^{b ( k )} och få en tvåvariabel genereringsfunktion ${\ displaystyle \ sigma}$

${\ displaystyle g (z, u) = 1+\ sum _ {n \ geq 1} \ vänster (\ sum _ {\ sigma \ i S_ {n}} u^{b (\ sigma)} \ höger) { \ frac {z^{n}} {n!}} = \ exp \ sum _ {k \ geq 1} u^{b (k)} {\ frac {z^{k}} {k}}}$

Detta är en "blandad" genereringsfunktion: det är en exponentiell genereringsfunktion i z och en vanlig genereringsfunktion i den sekundära parametern u. Differentiera och utvärdera vid u  = 1, vi har

${\ displaystyle {\ frac {\ partiell} {\ partiell u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} b (k) {\ frac {z^{k}} {k}} = \ sum _ {n \ geq 1} \ vänster (\ sum _ {\ sigma \ i S_ {n}} b (\ sigma) \ höger) {\ frac {z^{n}} {n!}}}$

Detta är sannolikhetsgenererande funktion för förväntningen på b . Med andra ord är koefficienten för i denna effektserie det förväntade värdet av b på permutationer i , med tanke på att varje permutation väljs med samma sannolikhet . ${\ displaystyle z^{n}}$${\ displaystyle S_ {n}}$${\ displaystyle 1/n!}$

Denna artikel använder koefficientuttagsoperatorn [ z ⁿ ], som dokumenterats på sidan för formella kraftserier .

Antal permutationer som är involutions

En involution är en permutation σ så att σ ² = 1 under permutationskomposition. Av detta följer att σ endast kan innehålla cykler med en eller två längder, dvs den exponentiella genereringsfunktionen g ( z ) för dessa permutationer är

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

Detta ger den uttryckliga formeln för det totala antalet involutions bland permutationerna σ ∈  S _n : ${\ displaystyle I (n)}$

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

Dela med n ! ger sannolikheten att en slumpmässig permutation är en involution. Dessa nummer är kända som telefonnummer .

Antal permutationer som är m roten till enhet

Detta generaliserar begreppet en involution. En m rot av enhet är en permutation σ så att σ ^m = 1 under permutationskomposition. Nu varje gång vi tillämpar σ rör vi oss ett steg parallellt längs alla dess cykler. En cykel med längd d applicerad d gånger ger identitetspermutation på d element ( d fasta punkter) och d är det minsta värdet för att göra det. Därför måste m vara en multipel av alla cykelstorlekar d , dvs de enda möjliga cyklerna är de vars längd d är en divisor av m . Det följer att EGF g ( x ) för dessa permutationer är

${\ displaystyle g (z) = \ exp \ left (\ sum _ {d \ mid m} {\ frac {z^{d}} {d}} \ right).}$

När m = p , där p är primtal, förenklas detta till

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

Antal permutationer av order exakt k

Detta kan göras genom Möbius inversion . Genom att arbeta med samma koncept som i föregående post noterar vi att de kombinatoriska arterna av permutationer vars ordning delar k ges av ${\ displaystyle {\ mathcal {Q}}}$

${\ displaystyle {\ mathcal {Q}} = \ operatorname {SET} \ left (\ sum _ {d \ mid k} \ operatorname {CYC} _ {= d} ({\ mathcal {Z}}) \ right) .}$

Översättning till exponentiella genereringsfunktioner vi erhåller EGF för permutationer vars ordning delar k , vilket är

${\ displaystyle Q_ {k} (z) = \ exp \ left (\ sum _ {d \ mid k} {\ frac {z^{d}} {d}} \ right).}$

Nu kan vi använda denna genereringsfunktion för att räkna permutationer av ordning exakt k . Låt vara antalet permutationer på n vars ordning är exakt d och antalet permutationer på n permutationsräkningen vars ordning delar k . Då har vi ${\ displaystyle p_ {n, d}}$${\ displaystyle q_ {n, k}}$

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

Det följer av Möbius inversion att

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

Därför har vi EGF

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

Den önskade räkningen ges sedan av

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

Denna formel producerar t.ex. för 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}}}$

med sekvensen av värden som börjar med n  = 5

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

För k  = 8 får vi 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}}}$

med sekvensen av värden som börjar med n  = 8

${\ displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800, \ ldots}$(sekvens A061122 i OEIS )

Slutligen för k  = 12 får vi 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}}}$

med sekvensen av värden som börjar med n  = 7

${\ displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600, \ ldots}$(sekvens A061125 i OEIS )

Antal permutationer som är störningar

Antag att det finns n personer på en fest, som var och en tog med ett paraply. I slutet av festen väljer alla ett paraply ur stacken av paraplyer och löv. Vad är sannolikheten för att ingen lämnade sitt eget paraply? Detta problem motsvarar att räkna permutationer utan fasta punkter (kallade avvikelser ), och därmed EGF, där vi subtraherar fasta punkter (cykler med längd 1) genom att ta bort termen z från den grundläggande relationen är

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

Multiplicering med summerar koefficienterna för det totala antalet störningar, ges med: ${\ displaystyle 1/(1-z)}$${\ displaystyle e^{-z}}$${\ displaystyle D (n)}$

${\ displaystyle D (n) = n! \ sum _ {k = 0}^{n} {\ frac {(-1)^{k}} {k!}} \; \ approx \; {\ frac { n!} {e}}.}$

Därför finns det ungefär störningar och sannolikheten för att en slumpmässig permutation är en störning är${\ displaystyle n!/e}$${\ displaystyle 1/e.}$

Detta resultat kan också bevisas genom inkludering – uteslutning . Med hjälp av uppsättningarna där vi ska beteckna uppsättningen permutationer som fixar p , har vi ${\ displaystyle A_ {p}}$${\ displaystyle {\ begin {matris} 1 \ leq p \ leq n \ end {matris}}}$

${\ displaystyle \ left | \ bigcup _ {p} A_ {p} \ right | = \ sum _ {p} \ left | A_ {p} \ right | \;-\; \ sum _ {p <q} \ vänster | A_ {p} \ cap A_ {q} \ höger | \;+\; \ sum _ {p <q <r} \ vänster | A_ {p} \ cap A_ {q} \ cap A_ {r} \ höger | \;-\; \ cdots \; \ pm \; \ vänster | A_ {p} \ cap \; \ cdots \; \ cap A_ {s} \ höger |.}$

Denna formel räknar antalet permutationer som har minst en fixpunkt. Kardinaliteterna är följande:

${\ displaystyle \ left | A_ {p} \ right | = (n-1)! \;, \; \; \ left | A_ {p} \ cap A_ {q} \ right | = (n-2)! \;, \; \; \ vänster | A_ {p} \ cap A_ {q} \ cap A_ {r} \ höger | = (n-3)! \;, \; \ ldots}$

Därför är antalet permutationer utan fast punkt

${\ displaystyle n! \; \;-\; \; {n \ välj 1} (n-1)! \; \;+\; \; {n \ välj 2} (n-2)! \; \ ;-\; \; {n \ välj 3} (n-3)! \; \;+\; \; \ cdots \; \; \ pm \; \; {n \ välj n} (nn)!}$

eller

${\ displaystyle n! \ left (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!}}}$

och vi har påståendet.

Det finns en generalisering av dessa nummer, som är kända som rencontres -nummer , dvs antalet permutationer för att innehålla m fasta punkter. Motsvarande EGF erhålls genom att markera cykler av storlek ett med variabeln u , dvs att välja b ( k ) lika med en för och noll annars, vilket ger uppsättningen permutations genereringsfunktion med antalet fasta punkter: ${\ displaystyle D (n, m)}$${\ displaystyle [n]}$${\ displaystyle k = 1}$${\ displaystyle g (z, u)}$

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

Det följer att

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

och följaktligen

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

Detta innebär omedelbart det

${\ displaystyle D (n, m) = {n \ välj m} D (nm, 0) \; \; {\ text {och}} \; \; {\ frac {D (n, m)} {n !}} \ approx {\ frac {e^{-1}} {m!}}}$

för n stor, m fast.

Ordning för slumpmässig permutation

Om P är en permutation är ordningen för P det minsta positiva heltalet n för vilket identitetspermutationen är. Detta är den minsta gemensamma multipeln av längderna av de cykler av P . ${\ displaystyle P^{n}}$

En sats av Goh och Schmutz säger att om är den förväntade ordningen för en slumpmässig permutation av storlek n , då ${\ displaystyle \ mu _ {n}}$

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

där konstanten c är

${\ displaystyle 2 {\ sqrt {2 \ int _ {0}^{\ infty} \ log \ log \ left ({\ frac {e} {1-e^{-t}}} \ right) dt}} \ ungefär 1.1178641511899}$

Förvrängningar som innehåller ett jämnt och ett udda antal cykler

Vi kan använda samma konstruktion som i föregående avsnitt för att beräkna antalet störningar som innehåller ett jämnt antal cykler och antalet som innehåller ett udda antal cykler. För att göra detta måste vi markera alla cykler och subtrahera fasta punkter, ge ${\ displaystyle D_ {0} (n)}$${\ displaystyle D_ {1} (n)}$

${\ displaystyle g (z, u) = \ exp \ left (-uz+u \ log {\ frac {1} {1-z}} \ right) = \ exp (-uz) \ left ({\ frac { 1} {1-z}} \ höger)^{u}.}$

Nu visar några mycket grundläggande resonemang att EGF för ges av ${\ displaystyle q (z)}$${\ displaystyle D_ {0} (n)}$

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

Vi har alltså

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

vilket är

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

Att dra från , hittar vi ${\ displaystyle D_ {0} (n)}$${\ displaystyle D (n)}$

${\ displaystyle D_ {1} (n) = {\ frac {1} {2}} n! \ sum _ {k = 0}^{n} {\ frac {(-1)^{k}} {k !}}-{\ frac {1} {2}} (1-n).}$

Skillnaden mellan dessa två ( och ) är${\ displaystyle D_ {0} (n)}$${\ displaystyle D_ {1} (n)}$${\ displaystyle n-1.}$

Hundra fångar

En fängelsevakt vill göra plats i sitt fängelse och funderar på att frigöra hundra fångar och därigenom frigöra hundra celler. Han samlar därför hundra fångar och ber dem att spela följande spel: han ställer upp hundra urnor i rad, var och en innehåller namnet på en fånge, där varje fångas namn förekommer exakt en gång. Spelet spelas enligt följande: varje fånge får titta in i femtio urnor. Om han eller hon inte hittar sitt namn i någon av de femtio urnorna kommer alla fångar att avrättas omedelbart, annars fortsätter spelet. Fångarna har några ögonblick att bestämma sig för en strategi, med vetskap om att när spelet väl har börjat kommer de inte att kunna kommunicera med varandra, markera urnorna på något sätt eller flytta urnorna eller namnen inuti dem. Genom att välja urnor slumpmässigt är deras chanser att överleva nästan noll, men det finns en strategi som ger dem 30% chans att överleva, förutsatt att namnen tilldelas urnor slumpmässigt - vad är det?

Först och främst är sannolikheten för överlevnad med slumpmässiga val

${\ displaystyle \ vänster ({\ frac {99 \ välj 49} {100 \ välj 50}} \ höger)^{100} = {\ frac {1} {2^{100}}},}$

så detta är definitivt inte en praktisk strategi.

30% överlevnadsstrategi är att betrakta innehållet i urnorna som en permutation av fångarna och genomgå cykler. För att hålla notationen enkel, tilldela varje fånge ett nummer, till exempel genom att sortera deras namn alfabetiskt. Urnen kan därefter anses innehålla siffror snarare än namn. Nu definierar innehållet i urnorna en permutation. Den första fången öppnar den första urna. Om han hittar sitt namn har han slutat och överlever. Annars öppnar han urnan med numret han hittade i den första urnan. Processen upprepas: fången öppnar en urna och överlever om han hittar sitt namn, annars öppnar han urnet med numret som just hämtats, upp till en gräns på femtio urnor. Den andra fången börjar med urna nummer två, den tredje med urna nummer tre och så vidare. Denna strategi är exakt ekvivalent med en genomgång av permutationens cykler representerade av urnorna. Varje fånge börjar med att urnan bär sitt nummer och fortsätter sin cykel upp till en gräns på femtio urnor. Antalet urna som innehåller hans nummer är förbilden av det numret under permutationen. Därför överlever fångarna om alla cykler av permutationen innehåller högst femtio element. Vi måste visa att denna sannolikhet är minst 30%.

Observera att detta förutsätter att väktaren väljer permutationen slumpmässigt; om vaktmästaren förutser denna strategi kan han helt enkelt välja en permutation med en cykel av längd 51. För att övervinna detta kan fångarna komma överens på förhand om en slumpmässig permutation av deras namn.

Vi överväger det allmänna fallet med fångar och urnor som öppnas. Vi beräknar först den komplementära sannolikheten, det vill säga att det finns en cykel med mer än element. Med detta i åtanke introducerar vi ${\ displaystyle 2n}$${\ displaystyle n}$${\ displaystyle n}$

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

eller

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

så att den önskade sannolikheten är

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

eftersom cykeln med mer än element nödvändigtvis kommer att vara unik. Med det faktum att vi hittar det ${\ displaystyle n}$${\ displaystyle 2 (n+1)> 2n}$

${\ displaystyle [z^{2n}] [u] g (z, u) = [z^{2n}] [u] {\ frac {1} {1-z}} \ vänster (1+ (u- 1) \ vänster ({\ frac {z^{n+1}} {n+1}}+{\ frac {z^{n+2}} {n+2}}+\ cdots \ höger) \ höger ),}$

Vilket ger

${\ displaystyle [z^{2n}] [u] g (z, u) = [z^{2n}] {\ frac {1} {1-z}} \ vänster ({\ 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}.}$

Slutligen, med hjälp av en integrerad uppskattning som Euler – Maclaurin summering , eller asymptotisk expansion av det n: e harmoniska talet , får vi

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

så att

${\ displaystyle [z^{2n}] [u] g (z, u) <\ log 2 \ quad {\ mbox {och}} \ quad 1- [z^{2n}] [u] g (z, u)> 1- \ log 2 = 0.30685281,}$

eller minst 30%, enligt kravet.

Ett relaterat resultat är att asymptotiskt är den förväntade längden för den längsta cykeln λn, där λ är Golomb – Dickman -konstanten , cirka 0,62.

Detta exempel beror på Anna Gál och Peter Bro Miltersen; konsultera tidningen av Peter Winkler för mer information och se diskussionen på Les-Mathematiques.net . Se referenser till 100 fångar för länkar till dessa referenser.

Beräkningen ovan kan utföras på ett mer enkelt och direkt sätt enligt följande: först notera att en permutation av element innehåller högst en längdcykel som är strikt större än . Alltså, om vi betecknar ${\ displaystyle 2n}$${\ displaystyle n}$

${\ displaystyle p_ {k} = \ Pr [{\ mbox {det finns en längdcykel}} k],}$

sedan

${\ displaystyle \ Pr [{\ mbox {det finns en längdcykel}}> n] = \ sum _ {k = n+1}^{2n} p_ {k}.}$

För , antalet permutationer som innehåller en cykel av längd exakt är ${\ displaystyle k> n}$${\ displaystyle k}$

${\ displaystyle {{2n} \ välj k} \ cdot {\ frac {k!} {k}} \ cdot (2n-k) !.}$

Förklaring: är antalet sätt att välja de element som ingår i cykeln; är antalet sätt att ordna objekt i en cykel; och är antalet sätt att permutera de återstående elementen. Det finns ingen dubbelräkning här eftersom det är högst en längdcykel när . Således, ${\ displaystyle {{2n} \ välj k}}$${\ displaystyle k}$${\ displaystyle {\ frac {k!} {k}}}$${\ displaystyle k}$${\ displaystyle (2n-k)!}$${\ displaystyle k}$${\ displaystyle k> n}$

${\ displaystyle p_ {k} = {\ frac {{{2n} \ välj k} \ cdot {\ frac {k!} {k}} \ cdot (2n-k)!} {(2n)!}} = {\ frac {1} {k}}.}$

Vi drar slutsatsen att

${\ displaystyle \ Pr [{\ mbox {det finns en längdcykel}}> n] = \ sum _ {k = n+1}^{2n} {\ frac {1} {k}} = H_ {2n } -H_ {n}.}$

En variant på problemet med 100 fångar (nycklar och lådor)

Det finns ett nära besläktat problem som passar metoden som presenteras här ganska bra. Säg att du har n beställt lådor. Varje låda innehåller en nyckel till någon annan låda eller möjligen själv som ger en permutation av nycklarna. Du får välja k av dessa n -lådor på en gång och bryta dem samtidigt och få åtkomst till k -nycklar. Vad är sannolikheten för att du med dessa nycklar kan öppna alla n -rutor, där du använder en hittad nyckel för att öppna rutan den tillhör och upprepa.

Det matematiska påståendet för detta problem är följande: välj en slumpmässig permutation på n element och k -värden från intervallet 1 till n , också slumpmässigt, kalla dessa märken. Vad är sannolikheten för att det finns minst ett märke på varje cykel av permutationen? Påståendet är att denna sannolikhet är k/n .

Art av permutationer av cykler med någon icke-tom delmängd av varje cykel som markeras har specifikationen ${\ displaystyle {\ mathcal {Q}}}$

${\ displaystyle {\ mathcal {Q}} = \ operatorname {SET} \ left (\ sum _ {q \ geq 1} \ operatorname {CYC} _ {= q} ({\ mathcal {Z}}) \ times \ summa _ {p = 1}^{q} {q \ välj p} {\ mathcal {U}}^{p} \ höger).}$

Indexet i den inre summan börjar med en eftersom vi måste ha minst ett märke på varje cykel.

Genom att översätta specifikationen till genererande funktioner får vi den bivariata genererande funktionen

${\ displaystyle G (z, u) = \ exp \ left (\ sum _ {q \ geq 1} {\ frac {z^{q}} {q}} \ sum _ {p = 1}^{q} {q \ välj p} u^{p} \ höger).}$

Detta förenklar till

${\ displaystyle \ exp \ left (\ sum _ {q \ geq 1} {\ frac {z^{q}} {q}} (u+1)^{q}-\ sum _ {q \ geq 1} {\ frac {z^{q}} {q}} \ höger)}$

eller

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

För att extrahera koefficienter från denna omskrivning så

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

Det följer nu det

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

och följaktligen

${\ displaystyle [u^{k}] [z^{n}] G (z, u) = {n \ välj k}-{n-1 \ välj k}.}$

Dela med för att få ${\ displaystyle {n \ välj k}}$

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

Vi behöver inte dela med n! eftersom är exponentiell i z . ${\ displaystyle G (z, u)}$

Antal permutationer som innehåller m -cykler

Tillämpa Flajolet – Sedgewicks grundläggande sats , dvs den märkta uppräkningssatsen med , på uppsättningen ${\ displaystyle G = S_ {m}}$

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

vi får genereringsfunktionen

${\ displaystyle g_ {m} (z) = {\ frac {1} {| S_ {m} |}} \ vänster (\ log {\ frac {1} {1-z}} \ höger)^{m} = {\ frac {1} {m!}} \ vänster (\ log {\ frac {1} {1-z}} \ höger)^{m}.}$

Termen

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

ger de signerade Stirling -numren av den första sorten , och är EGF för de osignerade Stirling -numren av den första sorten, dvs. ${\ displaystyle g_ {m} (z)}$

${\ displaystyle n! [z^{n}] g_ {m} (z) = \ left [{\ begin {matrix} n \\ m \ end {matrix}} \ right].}$

Vi kan beräkna OGF för de signerade Stirling -numren för n fast, dvs.

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

Börja med

${\ displaystyle g_ {m} (z) = \ sum _ {n \ geq m} {\ frac {(-1)^{n+m}} {n!}} s (n, m) z^{n }}$

Vilket ger

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

Sammanfattar vi detta får vi

${\ displaystyle \ sum _ {m \ geq 0} (-1)^{m} g_ {m} (z) w^{m} = \ sum _ {m \ geq 0} \ sum _ {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}.}$

Med hjälp av formeln som innefattar logaritmen för till vänster, definitionen av till höger och binomialsetningen , får vi ${\ displaystyle g_ {m} (z)}$${\ displaystyle s_ {n} (w)}$

${\ displaystyle (1-z)^{w} = \ sum _ {n \ geq 0} {w \ select n} (-1)^{n} z^{n} = \ sum _ {n \ geq 0 } {\ frac {(-1)^{n}} {n!}} s_ {n} (w) z^{n}.}$

Att jämföra koefficienterna för och använda definitionen av binomialkoefficienten har vi äntligen ${\ displaystyle z^{n}}$

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

en fallande faktor . Beräkningen av OGF för de osignerade Stirling -numren av den första typen fungerar på ett liknande sätt.

Förväntat antal cykler av en given storlek m

I detta problem använder vi en bivariat genererande funktion g ( z ,  u ) som beskrivs i inledningen. Värdet av b för en cykel som inte är av storlek m är noll, och ett för en cykel med storlek m . Vi har

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

eller

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

Detta innebär att det förväntade antalet cykler av storlek m i en permutation av längd n mindre än m är noll (uppenbarligen). En slumpmässig permutation av längden minst m innehåller i genomsnitt 1/ m cykler med längden m . I synnerhet innehåller en slumpmässig permutation ungefär en fast punkt.

OGF för det förväntade antalet cykler med längd mindre än eller lika med m är därför

${\ displaystyle {\ frac {1} {1-z}} \ sum _ {k = 1}^{m} {\ frac {z^{k}} {k}} {\ mbox {och}} [z ^{n}] {\ frac {1} {1-z}} \ sum _ {k = 1}^{m} {\ frac {z^{k}} {k}} = H_ {m} {\ mbox {för}} n \ geq m}$

där H _m är det m: e harmoniska talet . Därför är det förväntade antalet cykler av längd högst m i en slumpmässig permutation cirka ln  m .

Moment av fasta punkter

Den blandade GF av uppsättningen permutationer med antalet fasta punkter är ${\ displaystyle g (z, u)}$

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

Låt slumpvariabeln X vara antalet fasta punkter för en slumpmässig permutation. Med hjälp av Stirling -nummer av det andra slaget har vi följande formel för m: e ögonblicket av X :

${\ displaystyle E (X^{m}) = E \ left (\ sum _ {k = 0}^{m} \ left \ {{\ begin {matrix} m \\ k \ end {matrix}} \ right \} (X) _ {k} \ right) = \ sum _ {k = 0}^{m} \ left \ {{\ begin {matrix} m \\ k \ end {matrix}} \ right \} E ((X) _ {k}),}$

var är en fallande faktor . Använda , vi har ${\ displaystyle (X) _ {k}}$${\ displaystyle g (z, u)}$

${\ displaystyle E ((X) _ {k}) = [z^{n}] \ vänster ({\ frac {d} {du}} \ höger)^{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}},}$

som är noll när , och en annars. Därför bidrar endast termer med till summan. Detta ger ${\ displaystyle k> n}$${\ displaystyle k <= n}$

${\ displaystyle E (X^{m}) = \ sum _ {k = 0}^{n} \ left \ {{\ begin {matrix} m \\ k \ end {matrix}} \ right \}.}$

Förväntat antal fasta punkter i slumpmässig permutation höjd till viss effekt k

Antag att du väljer en slumpmässig permutation och höjer den till en viss effekt , med ett positivt heltal och frågar om det förväntade antalet fasta punkter i resultatet. Beteckna detta värde med . ${\ displaystyle \ sigma}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle E [F_ {k}]}$

För varje delare av en längdcykel delas upp i fasta punkter när de höjs till kraften Därför måste vi markera dessa cykler med För att illustrera detta${\ displaystyle d}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle d}$${\ displaystyle k.}$${\ displaystyle u^{d}.}$${\ displaystyle E [F_ {6}].}$

Vi får

${\ 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}} \ höger)}$

vilket är

${\ displaystyle {\ frac {1} {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}} \ höger).}$

Återigen, som beskrivs i inledningen, finner vi

${\ displaystyle \ left. {\ frac {\ partiell} {\ partiell u}} g (z, u) \ höger | _ {u = 1} = \ vänster. {\ frac {z+z^{2}+ z^{3}+z^{6}} {1-z}} \ exp \ vänster (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}}$

vilket är

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

Slutsatsen är att för och det finns fyra fasta punkter i genomsnitt. ${\ displaystyle E [F_ {6}] = 4}$${\ displaystyle n \ geq 6}$

Det allmänna förfarandet är

${\ displaystyle g (z, u) = \ exp \ left (\ sum _ {d \ mid k} \ left (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) \ rätt).}$

Än en gång fortsätter vi som tidigare, vi hittar

${\ displaystyle \ left. {\ frac {\ partiell} {\ partiell u}} g (z, u) \ höger | _ {u = 1} = \ vänster. {\ frac {\ sum _ {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}}.}$

Vi har visat att värdet på är lika med ( antalet delare av ) så snart det börjar på för och ökar med en varje gång träffar en delare av upp till och med sig själv. ${\ displaystyle E [F_ {k}]}$${\ displaystyle \ tau (k)}$${\ displaystyle k}$${\ displaystyle n \ geq k.}$${\ displaystyle 1}$${\ displaystyle n = 1}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$

Förväntat antal cykler av valfri längd av slumpmässig permutation

Vi konstruerar den bivariata genereringsfunktionen med , var är en för alla cykler (varje cykel bidrar en till det totala antalet cykler). ${\ displaystyle g (z, u)}$${\ displaystyle b (k)}$${\ displaystyle b (k)}$

Observera att den har stängt formulär ${\ displaystyle g (z, u)}$

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

och genererar osignerade Stirling -nummer av det första slaget .

Vi har

${\ displaystyle {\ frac {\ partiell} {\ partiell 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}} \ sum _ {k \ geq 1} {\ frac {z ^{k}} {k}} = {\ frac {1} {1-z}} \ log {\ frac {1} {1-z}}.}$

Därför är det förväntade antalet cykler det harmoniska talet , eller ungefär . ${\ displaystyle H_ {n}}$${\ displaystyle \ log n}$

Antal permutationer med en längdcykel större än n /2

(Observera att avsnitt hundra fångar innehåller exakt samma problem med en mycket liknande beräkning, plus också ett enklare elementärt bevis.)

Återigen, börja med den exponentiella genereringsfunktionen , denna gång i klassen permutationer enligt storlek där cykler med längd mer än är markerade med variabeln : ${\ displaystyle g (z, u)}$${\ displaystyle {\ mathcal {P}}}$${\ displaystyle n/2}$${\ displaystyle u}$

${\ displaystyle g (z, u) = \ exp \ left (u \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor}^{\ infty} {\ frac {z^{k }} {k}}+\ sum _ {k = 1}^{\ lfloor {\ frac {n} {2}} \ rfloor} {\ frac {z^{k}} {k}} \ höger). }$

Det kan bara vara en längdcykel mer än , varför svaret på frågan ges av ${\ displaystyle {\ frac {n} {2}}}$

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

eller

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

vilket är

${\ displaystyle n! [z^{n}] {\ frac {1} {1-z}} \ exp \ left (-\ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor }^{\ infty} {\ frac {z^{k}} {k}} \ höger) \ 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!}} \ vänster (\ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor}^{\ infty} {\ frac {z ^{k}} {k}} \ höger)^{m+1}}$

Exponenten för att i termen lyftas till makten är större än och därför kan inget värde för möjligen bidra till${\ displaystyle z}$${\ displaystyle m+1}$${\ displaystyle \ lfloor {\ frac {n} {2}} \ rfloor}$${\ displaystyle m> 0}$${\ displaystyle [z^{n}].}$

Därav följer att svaret är

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

Summan har en alternativ representation som man möter t.ex. i OEIS OEIS :  A024167 .

${\ displaystyle \ sum _ {k = 1}^{n} {\ frac {1} {k}}-\ sum _ {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 \ ovanpå k \; {\ text {jämn}}}^{n} (1-2 ) {\ frac {1} {k}}+\ sum _ {k = 1 \ ovanpå k \; {\ text {udda}}}^{n} {\ frac {1} {k}}}$

äntligen ger

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

Förväntat antal transpositioner av en slumpmässig permutation

Vi kan använda den osammanhängande cykelns sönderdelning av en permutation för att faktorisera den som en produkt av transpositioner genom att ersätta en cykel med längden k med k  - 1 transpositioner. Exempelvis cykelfaktorerna som . Funktionen för cykler är lika med och vi får ${\ displaystyle (1 \; 2 \; 34)}$${\ displaystyle (1 \; 2) \; (2 \; 3) \; (3 \; 4)}$${\ displaystyle b (k)}$${\ displaystyle k-1}$

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

och

${\ displaystyle {\ frac {\ partiell} {\ partiell u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} (k-1) {\ frac {z^{k}} {k}} = {\ frac {z} {(1-z)^{2}}}-{\ frac {1} {1-z}} \ log {\ frac {1} {1-z}}.}$

Därför förväntade antalet trans är ${\ displaystyle T (n)}$

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

var är det harmoniska numret . Vi kunde också ha fått denna formel genom att notera att antalet transpositioner erhålls genom att lägga till längderna på alla cykler (vilket ger n ) och subtrahera en för varje cykel (vilket ger med föregående avsnitt). ${\ displaystyle H_ {n}}$${\ displaystyle n^{th}}$ ${\ displaystyle \ log n}$

Observera att igen genererar osignerade Stirling -nummer av den första sorten , men i omvänd ordning. Mer exakt, vi har ${\ displaystyle g (z, u)}$

${\ displaystyle (-1)^{m} n! \; [z^{n}] [u^{m}] g (z, u) = \ vänster [{\ begin {matris} n \\ nm \ slutet {matris}} \ höger]}$

För att se detta, observera att ovanstående motsvarar

${\ displaystyle (-1)^{n+m} n! \; [z^{n}] [u^{m}] g (z, u) | _ {u = 1/u} | _ {z = uz} = \ vänster [{\ börja {matris} n \\ m \ slut {matris}} \ höger]}$

och det

${\ displaystyle [u^{m}] g (z, u) | _ {u = 1/u} | _ {z = uz} = [u^{m}] \ vänster ({\ frac {1} { 1-z}} \ höger)^{u} = {\ frac {1} {m!}} \ Vänster (\ log {\ frac {1} {1-z}} \ höger)^{m},}$

som vi såg vara EGF för de osignerade Stirling -numren av det första slaget i avsnittet om permutationer som består av exakt m -cykler.

Förväntad cykelstorlek för ett slumpmässigt element

Vi väljer ett slumpmässigt element q av en slumpmässig permutation och frågar om den förväntade storleken på cykeln som innehåller q . Här funktionen är lika med , eftersom en cykel av längd k bidrar k element som är på cykler av längd k . Notera att till skillnad från de tidigare beräkningarna måste vi i genomsnitt ut denna parameter när vi extrahera den från den genererande funktionen (dela med n ). Vi har ${\ displaystyle \ sigma}$${\ displaystyle b (k)}$${\ displaystyle k^{2}}$

${\ displaystyle {\ frac {\ partiell} {\ partiell u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} k^{2} {\ frac {z^{k}} {k}} = {\ frac {1} {1-z}} {\ frac {z} {(1-z)^ {2}}} = {\ frac {z} {(1-z)^{3}}}.}$

Därför förväntade längden av cykeln som innehåller q är

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

Sannolikhet att ett slumpmässigt element ligger på en cykel av storlek m

Denna genomsnittsparameter representerar sannolikheten att om vi igen väljer ett slumpmässigt element av en slumpmässig permutation, ligger elementet på en cykel med storlek m . Funktionen är lika med för och noll annars, eftersom endast cykler med längden m bidrar, nämligen m element som ligger på en cykel med längden m . Vi har ${\ displaystyle [n]}$${\ displaystyle b (k)}$${\ displaystyle m}$${\ displaystyle m = k}$

${\ displaystyle {\ frac {\ partiell} {\ partiell 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}} \; m \; {\ frac {z^{m} } {m}} = {\ frac {z^{m}} {1-z}}.}$

Det följer att sannolikheten för att ett slumpmässigt element ligger på en cykel med längden m är

${\ displaystyle {\ frac {1} {n}} [z^{n}] {\ frac {z^{m}} {1-z}} = {\ begin {cases} {\ frac {1} { n}}, och {\ mbox {if}} n \ geq m \\ 0, och {\ mbox {annars.}} \ slut {fall}}}$

Sannolikhet att en slumpmässig delmängd av [ n ] ligger på samma cykel

Välj en slumpmässig delmängd Q av [ n ] som innehåller m -element och en slumpmässig permutation, och fråga om sannolikheten att alla element i Q ligger på samma cykel. Detta är en annan genomsnittsparameter. Funktionen b ( k ) är lika med , eftersom en cykel med längden k bidrar med delmängder av storlek m , där för k < m . Detta ger ${\ displaystyle {\ begin {matris} {k \ välj m} \ slut {matris}}}$${\ displaystyle {\ begin {matris} {k \ välj m} \ slut {matris}}}$${\ displaystyle {\ begin {matris} {k \ välj m} = 0 \ slut {matris}}}$

${\ displaystyle {\ frac {\ partiell} {\ partiell u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq m} {k \ välj 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}}}.}$

I genomsnitt tar vi fram att sannolikheten för att elementen i Q är i samma cykel är

${\ displaystyle {n \ välj m}^{-1} [z^{n}] {\ frac {1} {m}} {\ frac {z^{m}} {(1-z)^{m +1}}} = {n \ välj m}^{-1} {\ frac {1} {m}} [z^{nm}] {\ frac {1} {(1-z)^{m+ 1}}}}$

eller

${\ displaystyle {\ frac {1} {m}} {n \ välj m}^{-1} {(nm) \;+\; m \ välj m} = {\ frac {1} {m}}. }$

I synnerhet är sannolikheten att två element p < q är i samma cykel 1/2.

Antal permutationer som innehåller ett jämnt antal jämna cykler

Vi kan använda Flajolet – Sedgewick grundläggande sats direkt och beräkna mer avancerad permutationsstatistik. (Kontrollera den sidan för en förklaring av hur de operatörer vi kommer att använda beräknas.) Till exempel ges uppsättningen permutationer som innehåller ett jämnt antal jämna cykler av

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC } _ {\ operatorname {even}} ({\ mathcal {Z}})).}$

Vi översätter till exponentiella genererande funktioner (EGF)

${\ displaystyle \ exp \ left ({\ frac {1} {2}} \ log {\ frac {1+z} {1-z}} \ right) \ cosh \ left ({\ frac {1} {2 }} \ log {\ frac {1} {1-z^{2}}} \ höger)}$

eller

${\ displaystyle {\ frac {1} {2}} \ exp \ left ({\ frac {1} {2}} \ left (\ log {\ frac {1+z} {1-z}}+\ log {\ frac {1} {1-z^{2}}} \ höger) \ höger)+{\ frac {1} {2}} \ exp \ vänster ({\ frac {1} {2}} \ vänster (\ log {\ frac {1+z} {1-z}}-\ log {\ frac {1} {1-z^{2}}} \ höger) \ höger).}$

Detta förenklar till

${\ displaystyle {\ frac {1} {2}} \ exp \ left ({\ frac {1} {2}} \ log {\ frac {1} {(1-z)^{2}}} \ right )+{\ frac {1} {2}} \ exp \ vänster ({\ frac {1} {2}} \ log (1+z)^{2} \ höger)}$

eller

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

Detta säger att det finns en permutation av storlek noll som innehåller ett jämnt antal jämna cykler (den tomma permutationen, som innehåller nollcykler med jämn längd), en sådan permutation av storlek ett (den fasta punkten, som också innehåller nollcykler med jämn längd ), och att det finns sådana permutationer. ${\ displaystyle n \ geq 2}$${\ displaystyle n!/2}$

Permutationer som är rutor

Tänk på vad som händer när vi kvadrerar en permutation. Fasta punkter mappas till fasta punkter. Udda cykler mappas till udda cykler i en en-till-en-korrespondens, t.ex. blir till . Även cykler delas i två och producerar ett par cykler med halva storleken på den ursprungliga cykeln, t.ex. blir till . Därför kan permutationer som är kvadrater innehålla valfritt antal udda cykler och ett jämnt antal cykler av storlek två, ett jämnt antal cykler av storlek fyra etc., och ges av ${\ displaystyle (1 \; 8 \; 9 \; 11 \; 13)}$${\ displaystyle (1 \; 9 \; 13 \; 8 \; 11)}$${\ displaystyle (5 \; 13 \; 6 \; 9)}$${\ displaystyle (5 \; 6) \; (9 \; 13)}$

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC } _ {= 2} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC} _ {= 4} ({\ mathcal {Z}}))) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC} _ {= 6} ({\ mathcal {Z}})) \ cdots}$

vilket ger EGF

${\ displaystyle \ exp \ left ({\ frac {1} {2}} \ log {\ frac {1+z} {1-z}} \ right) \ prod _ {m \ geq 1} \ cosh {\ frac {z^{2m}} {2m}} = {\ sqrt {\ frac {1+z} {1-z}}} \ prod _ {m \ geq 1} \ cosh {\ frac {z^{2m }} {2m}}.}$

Udda cykelvarianter

De typer av permutationer som presenteras i de föregående två sektionerna, det vill säga permutationer som innehåller ett jämnt antal jämna cykler och permutationer som är kvadrater, är exempel på så kallade udda cykel invarianter , studerade av Sung och Zhang (se externa länkar ). Termen udda cykel invariant betyder helt enkelt att medlemskap i respektive kombinatoriska klass är oberoende av storleken och antalet udda cykler som förekommer i permutationen. I själva verket kan vi bevisa att alla udda cykel invarianter följer en enkel upprepning, som vi kommer att härleda. Först, här är några fler exempel på udda cykel invarianter.

Permutationer där summan av längden på de jämna cyklerna är sex

Denna klass har specifikationen

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ left (\ operatorname {SET} _ {= 3} (\ operatorname {CYC } _ {= 2} ({\ mathcal {Z}}))+\ operatorname {CYC} _ {= 2} ({\ mathcal {Z}}) \ operatorname {CYC} _ {= 4} ({\ mathcal {Z}})+\ operatorname {CYC} _ {= 6} ({\ mathcal {Z}}) \ right)}$

och genereringsfunktionen

${\ displaystyle {\ sqrt {\ frac {1+z} {1-z}}} \ left ({\ frac {1} {6}} \ left ({\ frac {z^{2}} {2} } \ höger)^{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}}}.}$

De första värdena är

${\ displaystyle 0,0,0,0,0,225,1575,6300,56700,425250,4677750,46777500,608107500, \ ldots}$

Permutationer där alla jämna cykler har samma längd

Denna klass har specifikationen

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

och genereringsfunktionen

${\ displaystyle {\ sqrt {\ frac {1+z} {1-z}}} \ left (\ exp \ left ({\ frac {z^{2}} {2}} \ right) -1 \, +\, \ exp \ vänster ({\ frac {z^{4}} {4}} \ höger) -1 \,+\, \ exp \ vänster ({\ frac {z^{6}} {6} } \ höger) -1 \,+\, \ cdots \ höger).}$

Det finns en semantisk nyans här. Vi kan betrakta permutationer som inte innehåller några jämna cykler som tillhörande denna klass, eftersom noll är jämn . De första värdena är

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

Permutationer där den maximala längden på en jämn cykel är fyra

Denna klass har specifikationen

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ operatorname {SET} (\ operatorname {CYC} _ {= 2} ({ \ mathcal {Z}})+\ operatorname {CYC} _ {= 4} ({\ mathcal {Z}}))}}$

och genereringsfunktionen

${\ displaystyle {\ sqrt {\ frac {1+z} {1-z}}} \ exp \ left ({\ frac {z^{2}} {2}}+{\ frac {z^{4} } {4}} \ höger).}$

De första värdena är

${\ displaystyle 1,2,6,24,120,600,4200,28560,257040,2207520,24282720,258128640, \ ldots}$

Återkomsten

Observera noga hur specifikationerna för jämncykelkomponenten är konstruerade. Det är bäst att tänka på dem när det gäller parningsträd. Dessa träd har tre nivåer. Noderna på den lägsta nivån representerar summor av produkter av singlettons cykler med jämn längd . Noderna på mittenivå representerar begränsningar för uppsättningsoperatören. Slutligen summerar noden på översta nivån produkter av bidrag från mitten. Observera att begränsningar för uppsättningsoperatorn, när de tillämpas på en genereringsfunktion som är jämn, kommer att bevara denna funktion, dvs producera en annan jämn genererande funktion. Men alla ingångar till uppsättningsoperatörerna är jämna eftersom de härrör från jämna cykler. Resultatet är att alla involverade genereringsfunktioner har formen ${\ displaystyle {\ mathcal {Z}}}$

${\ displaystyle g (z) = h (z) {\ sqrt {\ frac {1+z} {1-z}}},}$

var är en jämn funktion. Detta innebär att ${\ displaystyle h (z)}$

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

är jämn också, och därför

${\ displaystyle {\ frac {1} {1+z}} \; g (z) = {\ frac {1} {1-z}} \; g (-z) \ quad {\ mbox {eller}} \ quad (1-z) \; g (z) = (1+z) \; g (-z).}$

Låta och extrahera koefficienter, finner vi det ${\ displaystyle g_ {n} = [z^{n}] g (z)}$

${\ displaystyle {\ frac {g_ {2m+1}} {(2m+1)!}}-{\ frac {g_ {2m}} {(2m)!}} =-{\ frac {g_ {2m+ 1}} {(2m+1)!}}+{\ Frac {g_ {2m}} {(2m)!}} \ Quad {\ mbox {eller}} \ quad 2 {\ frac {g_ {2m+1 }} {(2m+1)!}} = 2 {\ frac {g_ {2m}} {(2m)!}}}$

vilket ger återfall

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

Ett problem från Putnam -tävlingen 2005

En länk till Putnams tävlingswebbplats visas i avsnittet Externa länkar . Problemet ber om ett bevis på det

${\ displaystyle \ sum _ {\ pi \ i S_ {n}} {\ frac {\ sigma (\ pi)} {\ nu (\ pi) +1}} = (-1)^{n+1} { \ frac {n} {n+1}},}$

där summan är över alla permutationer av , är tecknet på , dvs om är jämnt och om är udda, och är antalet fasta punkter på . ${\ 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}$

Nu tecknet på ges av ${\ displaystyle \ pi}$

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

där produkten är över alla cykler c av , såsom förklaras t ex på sidan på jämna och udda permutationer . ${\ displaystyle \ pi}$

Därför betraktar vi den kombinatoriska klassen

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

där markerar en minus längden på en bidragande cykel och markerar fasta punkter. Översättning till genereringsfunktioner får vi ${\ displaystyle {\ mathcal {U}}}$${\ displaystyle {\ mathcal {V}}}$

${\ displaystyle g (z, u, v) = \ exp \ left (-z+vz+\ sum _ {k \ geq 1} u^{k-1} {\ frac {z^{k}} {k} }\rätt)}$

eller

${\ displaystyle \ exp \ left (-z+vz+{\ frac {1} {u}} \ log {\ frac {1} {1-uz}} \ right) = \ exp (-z+vz) \ left ({\ frac {1} {1-uz}} \ höger)^{1/u}.}$

Nu har vi

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

och därför ges den önskade mängden av

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

Genom att göra beräkningen får vi

${\ displaystyle \ int _ {0}^{1} g (z, -1, v) dv = \ exp (-z) (1+z) \ left ({\ frac {1} {z}} \ exp (z)-{\ frac {1} {z}} \ höger)}$

eller

${\ displaystyle \ left ({\ frac {1} {z}}+1 \ right) \ left (1- \ exp (-z) \ right) = {\ frac {1} {z}}+1- \ exp (-z)-{\ frac {1} {z}} \ exp (-z).}$

Genom att extrahera koefficienter finner vi att koefficienten för är noll. Konstanten är en, som inte håller med formeln (ska vara noll). För positivt får vi dock ${\ displaystyle 1/z}$${\ displaystyle n}$

${\ displaystyle n! [z^{n}] \ left (-\ exp (-z)-{\ frac {1} {z}} \ exp (-z) \ right) = n! \ left (-( -1)^{n} {\ frac {1} {n!}}-(-1)^{n+1} {\ frac {1} {(n+1)!}} \ Höger)}$

eller

${\ displaystyle (-1)^{n+1} \ left (1-{\ frac {1} {n+1}} \ right) = (-1)^{n+1} {\ frac {n} {n+1}},}$

vilket är önskat resultat.

Som en intressant sida observerar vi att det kan användas för att utvärdera följande determinant för en matris: ${\ displaystyle g (z, u, v)}$${\ displaystyle n \ gånger n}$

${\ displaystyle d (n) = \ det (A_ {n}) = {\ begin {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}}.}$

var . Återkalla formeln för determinanten: ${\ displaystyle a, b \ neq 0}$

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

Nu värdet av produkten på höger för en permutation är , där f är antalet fasta punkter . Därmed ${\ displaystyle \ pi}$${\ displaystyle a^{f} b^{nf}}$${\ displaystyle \ pi}$

${\ displaystyle d (n) = b^{n} n! [z^{n}] g \ vänster (z, -1, {\ frac {a} {b}} \ höger) = b^{n} n! [z^{n}] \ exp \ vänster ({\ frac {ab} {b}} z \ höger) (1+z)}$

Vilket ger

${\ displaystyle b^{n} \ vänster ({\ frac {ab} {b}} \ höger)^{n}+b^{n} n \ vänster ({\ frac {ab} {b}} \ höger )^{n-1} = (ab)^{n}+nb (ab)^{n-1}}$

och slutligen

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

Skillnaden mellan antalet cykler i jämna och udda permutationer

Här försöker vi visa att denna skillnad ges av

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

Minns att tecknet på en permutation ges av ${\ displaystyle \ sigma (\ pi)}$${\ displaystyle \ pi}$

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

där produkten sträcker sig över cyklerna c från den osammanhängande cykelsammansättningen av . ${\ displaystyle \ pi}$

Därav följer att den kombinatoriska arten som återspeglar tecknen och antalet cykler för uppsättningen permutationer ges av ${\ displaystyle {\ mathcal {Q}}}$

${\ displaystyle {\ mathcal {Q}} = \ operatorname {SET} ({\ mathcal {V}} \ operatorname {CYC} _ {1} ({\ mathcal {Z}})+{\ mathcal {U}} {\ mathcal {V}} \ operatorname {CYC} _ {= 2} ({\ mathcal {Z}}))+{\ mathcal {U}}^{2} {\ mathcal {V}} \ operatorname {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)}$

där vi har använt för att markera skyltar och för cykeltalet. ${\ displaystyle {\ mathcal {U}}}$${\ displaystyle {\ mathcal {V}}}$

Översätter till att generera funktioner vi har

${\ displaystyle Q (z, u, v) = \ exp \ left (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 \ höger).}$

Detta förenklar till

${\ displaystyle Q (z, u, v) = \ exp \ left ({\ frac {v} {u}} \ left ({\ 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)}$

vilket är

${\ displaystyle \ exp \ left ({\ frac {v} {u}} \ log {\ frac {1} {1-uz}} \ right) = \ left ({\ frac {1} {1-uz} } \ höger)^{\ frac {v} {u}}.}$

Nu ges de två genereringsfunktionerna och jämna och udda permutationer efter cykeltal av ${\ 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}} \ vänster ({\ frac {1} {1-z}} \ höger)^{v}+{\ frac {1} {2}} \ vänster ({ \ frac {1} {1+z}} \ höger)^{-v}}$

och

${\ displaystyle Q_ {2} (z, v) = {\ frac {1} {2}} Q (z,+1, v)-{\ frac {1} {2}} Q (z, -1, v) = {\ frac {1} {2}} \ vänster ({\ frac {1} {1-z}} \ höger)^{v}-{\ frac {1} {2}} \ vänster ({ \ frac {1} {1+z}} \ höger)^{-v}.}$

Vi kräver mängden

${\ displaystyle G (z, v) = \ left. {\ frac {d} {dv}} (Q_ {1} (z, v) -Q_ {2} (z, v)) \ right | _ {v = 1}}$

vilket är

${\ displaystyle \ left. {\ frac {d} {dv}} \ left ({\ frac {1} {1+z}} \ right)^{-v} \ right | _ {v = 1} =- \ vänster. \ log {\ frac {1} {1+z}} \ vänster ({\ frac {1} {1+z}} \ höger)^{-v} \ höger | _ {v = 1} = -(1+z) \ log {\ frac {1} {1+z}}.}$

Slutligen, genom att extrahera koefficienter från denna genereringsfunktion, får vi

${\ displaystyle -n! [z^{n}] (1+z) \ log {\ frac {1} {1+z}} =-n! \ left ({\ frac {(-1)^{n }} {n}}+{\ frac {(-1)^{n-1}} {n-1}} \ höger)}$

vilket är

${\ displaystyle -n! (-1)^{n-1} \ left (-{\ frac {1} {n}}+{\ frac {1} {n-1}} \ right) = n! ( -1)^{n} {\ frac {n- (n-1)} {n (n-1)}}}$

vilket i sin tur

${\ displaystyle n! (-1)^{n} {\ frac {1} {n (n-1)}} = (-1)^{n} (n-2)!}$

Detta avslutar beviset.

Se även

• Golomb – Dickman konstant

Referenser

externa länkar

• Panholzer, Alois; Prodinger, Helmut; Riedel, Marko. "Mät post-quickselect disorder" (PDF) . Citera journal kräver |journal=( hjälp )
• William Lowell Putnam Competition Archive
• Sung, Philip; Zhang, Yan. "Återkommande återfall i räknande permutationer". CiteSeerX  10.1.1.91.1088 . Citera journal kräver |journal=( hjälp )
• Marko Riedel et al., Skillnaden mellan antalet cykler av jämna och udda permutationer
• Marko Riedel et al., Nycklar i slutna lådor, en fråga om sannolikhet

100 fångar

• Anna Gál, Peter Bro Miltersen, Cellprobets komplexitet hos kortfattade datastrukturer
• Olika författare, Permutationer med en cykel> n/2
• Olika författare, en egenskap hos störningar
• Olika författare, Förväntat antal fasta punkter
• Peter Winkler, sju pussel som du tror att du inte måste ha hört rätt
• Olika författare, Les-Mathematiques.net . Cent fengslar (på franska)