Slumpmässig permutationsstatistik

Statistiken för slumpmässiga permutationer , såsom cykelstrukturen för en slumpmässig permutation, är av grundläggande betydelse i analysen av algoritmer, särskilt för sorteringsalgoritmer, som fungerar på slumpmässiga permutationer. Anta 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 kommer en permutation att vara mindre oordnad efter att snabbval har utförts. Mängden störning som finns kvar kan analyseras med genererande funktioner. Dessa genereringsfunktioner beror på ett fundamentalt sätt på genereringsfunktionerna för slumpmässig permutationsstatistik. Därför är det av avgörande betydelse att beräkna dessa genererande funktioner.

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. Använda det märkta fallet för Flajolet–Sedgewicks fundamentalsats och skriva $\scriptstyle {\mathcal {P}}$ för uppsättningen av permutationer och $\scriptstyle {\mathcal {Z}}$ för singeltonen set, vi har

$\operatörsnamn {SET} (\operatörsnamn {CYC} ({\mathcal {Z}}))={\mathcal {P}}.$

Att översätta till exponentiella genererande funktioner (EGF) har vi

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

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

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

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

för det finns k ! / k märkta cykler. Detta betyder att genom att ta bort termer från denna genererande funktion kan vi begränsa storleken på de cykler som förekommer i en permutation och erhålla en EGF av 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 av olika storlek. Om $b:\mathbb {N} \rightarrow \mathbb {R}$ är en viktfunktion som endast beror på storleken k på cykeln och för korthets skull skriver vi

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

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

$g(z,u)=1+\summa _{n\geq 1}\left(\summa _{\sigma \in S_{n }}u^{b(\sigma )}\right){\frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{ \frac {z^{k}}{k}}$

Detta är en "blandad" genererande funktion: det är en exponentiell genererande funktion i z och en vanlig genererande funktion i den sekundära parametern u. Att differentiera och utvärdera vid u = 1 har vi

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\summa _{ k\geq 1}b(k){\frac {z^{k}}{k}}=\summa _{n\geq 1}\left(\summa _{\sigma \in S_{n}}b (\sigma )\right){\frac {z^{n}}{n!}}$

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

Den här artikeln använder koefficientextraktionsoperatorn [ z ⁿ ], dokumenterad på sidan för formella effektserier .

Antal permutationer som är involutioner

Huvudartikel: Telefonnummer (matematik)

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

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

Detta ger den explicita formeln för det totala antalet $I(n)$ av involutioner bland permutationerna σ ∈ S _n :

$I(n)=n![z^{n}]g(z)=n!\sum _{a+2b=n}{\frac {1}{a!\;2^{b} \;b!}}=n!\summa _{b=0}^{\lvåning n/2\rvåning }{\frac {1}{(n-2b)!\;2^{b}\;b !}}.$

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

Antal permutationer som är m: te rötter till enhet

Detta generaliserar begreppet involution. En m: te roten av enhet är en permutation σ så att σ ^m = 1 under permutationssammansättning. Varje gång vi applicerar σ går vi nu ett steg parallellt längs alla dess cykler. En cykel med längden d applicerad d gånger producerar identitetspermutationen på d element ( d fixpunkter) och d är det minsta värdet för att göra det. Därför 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

$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

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

Antal permutationer av ordning 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 den kombinatoriska arten ${\mathcal {Q}}$ av permutationer vars ordning delar k ges av

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

Översättning till exponentiella genererande funktioner får vi EGF för permutationer vars ordning delar k , vilket är

$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 ordningen exakt k . Låt $p_{n,d}$ vara antalet permutationer på n vars ordning är exakt d och $q_{n,k}$ antalet permutationer på n permutationen räkna vars ordning delar k . Då har vi

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

Det följer av Möbius inversion att

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

Därför har vi EGF

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

Det önskade antalet ges sedan av

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

Denna formel ger t.ex. för k = 6 EGF

$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 på n = 5

$,\ldots }$ (sekvens A061121 i OEIS )

För k = 8 får vi EGF

$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 på n = 8

$56040,3040,450,450,450,450 00,363242880,3874590720,34767532800,\ldots$ (sekvens A061122 i OEIS )

Slutligen för k = 12 får vi EGF

$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 på n = 7

$\ldots }$ (sekvens A061125 i OEIS )

Antal permutationer som är störningar

Huvudartikel: Derangement

Anta att det är n personer på en fest, som var och en tog med sig ett paraply. I slutet av festen plockar alla ett paraply ur bunten med paraplyer och löv. Vad är sannolikheten att ingen lämnade med sitt eget paraply? Det här problemet är likvärdigt med att räkna permutationer utan fasta punkter (kallade derangements ), och därför EGF, där vi subtraherar ut fixpunkter (cykler med längd 1) genom att ta bort termen z från den grundläggande relationen är

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

Multiplikation med $1/(1-z)$ summerar koefficienterna för $e^{-z}$ , så $D(n)$ , det totala antalet avvikelser, ges av:

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

Därför finns det ca $n!/e$ avvikelser och sannolikheten att en slumpmässig permutation är en avvikelse är $1/e.$

Detta resultat kan också bevisas genom inkludering–uteslutning . Använda uppsättningarna $A_{p}$ där ${\begin{matrix}1\leq p\leq n\end{matrix}}$ för att beteckna uppsättningen av permutationer som fixar p , vi har

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

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

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

Därför är antalet permutationer utan fixpunkt

$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

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

Det finns en generalisering av dessa tal, vilket är känt som rencontres numbers , dvs antalet $D(n,m)$ av permutationer av $[n]$ som innehåller m fasta poäng. Motsvarande EGF erhålls genom att markera cykler av storlek ett med variabeln u , dvs. välja b ( k ) lika med ett för $k=1$ och noll annars, vilket ger genereringsfunktionen $g(z,u)$ av uppsättningen permutationer med antalet fasta punkter:

$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

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

och följaktligen

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

Detta innebär omedelbart det

$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 av en slumpmässig permutation

Om P är en permutation är ordningen för P det minsta positiva heltal n för vilket $P^{n}$ är identitetspermutationen. Detta är den minsta gemensamma multipeln av längderna av cyklerna för P .

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

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

där konstanten c är

$2{\sqrt {2\int _{0}^{\infty }\log \log \cleft {e}{1-e^{-t}}}\right)dt}}\approx 1,1178641511899$

Störningar 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 avvikelser $D_{0}(n)$ som innehåller ett jämnt antal cykler och talet $D_ {1}(n)$ som innehåller ett udda antal cykler. För att göra detta måste vi markera alla cykler och subtrahera fixpunkter, ge

$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 $q(z)$ för $D_{0}(n)$ ges av

$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å

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

vilket är

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

Om vi ​​subtraherar $D_{0}(n)$ från $D(n)$ finner vi

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

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

Hundra fångar

Huvudartikel: Problem med 100 fångar

En kriminalvårdare vill göra plats i sitt fängelse och överväger att befria hundra fångar och därmed befria hundra celler. Han samlar därför ihop hundra fångar och ber dem att spela följande spel: han radar upp hundra urnor i rad, som var och en innehåller namnet på en fånge, där varje fånges 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 omedelbart att avrättas, annars fortsätter spelet. Fångarna har några ögonblick på sig att bestämma sig för en strategi, i 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. Om du väljer 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

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

så detta är definitivt inte en praktisk strategi.

Strategin för 30 % överlevnad är att betrakta innehållet i urnorna som en permutation av fångarna och genomlöpa cykler. För att hålla notationen enkel, tilldela ett nummer till varje fånge, till exempel genom att sortera deras namn i alfabetisk ordning. Urnorna kan därefter anses innehålla nummer snarare än namn. Nu definierar innehållet i urnorna tydligt en permutation. Den första fången öppnar den första urnan. Om han hittar sitt namn har han gjort klart 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 urnan 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 cyklerna för permutationen som representeras av urnorna. Varje fånge börjar med urnan som bär hans nummer och fortsätter att korsa sin cykel upp till en gräns på femtio urnor. Numret på urnan 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 vaktmästaren 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 i förväg komma överens om en slumpmässig permutation av deras namn.

Vi betraktar det allmänna fallet med $2n$ fångar och $n$ urnor öppnas. Vi beräknar först den komplementära sannolikheten, dvs att det finns en cykel med fler än $n$ element. Med detta i åtanke introducerar vi

$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

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

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

eftersom cykeln för fler än $n$ element nödvändigtvis kommer att vara unik. Genom att använda det faktum att $2(n+1)>2n$ finner vi att

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

Vilket ger

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

Slutligen, med hjälp av en integraluppskattning som Euler-Maclaurin summation , eller den asymptotiska expansionen av det n :te övertonstalet , får vi

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

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

eller minst 30 %, enligt vad som påstås.

Ett relaterat resultat är att asymptotiskt är den förväntade längden av den längsta cykeln λn, där λ är Golomb–Dickman-konstanten , ungefär 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 referenserna om 100 fångar för länkar till dessa referenser.

Ovanstående beräkning kan utföras på ett enklare och mer direkt sätt, enligt följande: observera först att en permutation av $2n$ element innehåller högst en cykel med längd som är strikt större än $n$ . Alltså, om vi betecknar

$p_{k}=\Pr[{\mbox{det finns en cykel med längden }}k],$

sedan

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

För $k>n$ är antalet permutationer som innehåller en cykel med längden exakt $k$

${{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!.$

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

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

Det drar vi slutsatsen

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

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

Det finns ett närbesläktat problem som passar den metod som presenteras här ganska bra. Säg att du inte har några beställda lådor. Varje låda innehåller en nyckel till någon annan låda eller eventuellt sig själv som ger en permutation av nycklarna. Du får välja k av dessa n rutor på en gång och bryta upp dem samtidigt, och få tillgång 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 lådan den tillhör och upprepa.

Det matematiska uttalandet av detta problem är som följer: 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 att det finns minst ett märke på varje cykel av permutationen? Påståendet är att denna sannolikhet är k/n .

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

${\mathcal {Q}}=\operatörsnamn {SET} \left(\sum _{q\geq 1}\operatörsnamn {CYC} _{=q}({\mathcal {Z}})\ gånger \ summa _{p=1}^{q}{q \choose p}{\mathcal {U}}^{p}\right).$

Indexet i den inre summan börjar på ett 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

$G(z,u)=\exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}\sum _{p=1}^{q} {q \choose p}u^{p}\right).$

Detta förenklar till

$\exp \left(\sum _{q\geq 1}{\frac {z^{q }}{q}}(u+1)^{q}-\summa _{q\geq 1}{\frac {z^{q}}{q}}\right)$

eller

$\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 detta, skriv om så

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

Det följer nu att

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

och följaktligen

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

Dividera med ${n \choose k}$ för att få

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

Vi behöver inte dividera med n! eftersom $G(z,u)$ är exponentiell i z .

Antal permutationer som innehåller m cykler

Att tillämpa Flajolet–Sedgewicks fundamentalsats , dvs. den märkta uppräkningssatsen med $G=S_{m}$ , på mängden

$\operatörsnamn {SET} _{=m}(\operatörsnamn {CYC} ({\mathcal {Z}}))$

vi får genereringsfunktionen

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

Termen

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

ger de signerade stirlingtalen av det första slaget , och $g_{m}(z)$ är EGF för de osignerade stirlingtalen av det första slaget, dvs.

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

Vi kan beräkna OGF för de signerade Stirlingtalen för n fast, dvs

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

Börja med

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

Vilket ger

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

Sammanfattningsvis får vi

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

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

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

Genom att jämföra koefficienterna för $z^{n}$ och använda definitionen av binomialkoefficienten har vi slutligen

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

en fallande faktorial . Beräkningen av OGF för de osignerade Stirlingtalen av det första slaget fungerar på 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 på b för en cykel som inte har storlek m är noll och ett för en cykel av storlek m . Vi har

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

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

Detta betyder att det förväntade antalet cykler av storleken m i en permutation med längden n mindre än m är noll (uppenbarligen). En slumpmässig permutation med längd minst m innehåller i genomsnitt 1/ m cykler med längd 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

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

där H _m är det m :te övertonstalet . Det förväntade antalet cykler av längd som mest m i en slumpmässig permutation är därför ungefär ln m .

Moment av fixpunkter

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

$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 fixpunkter i en slumpmässig permutation. Med hjälp av Stirlingtal av det andra slaget har vi följande formel för det m :te momentet av X :

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

där $(X)_{k}$ är en fallande faktor . Genom att använda $g(z,u)$ har vi

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

vilket är noll när $k>n$ , och en annars. Därför bidrar bara termer med $k<=n$ till summan. Detta ger

$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öjt till någon potens k

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

För varje divisor $d$ av ${\displaystyle k} delas$ en cykel med längden $d$ upp i $d$ fasta punkter när den höjs till potensen $k.$ Därför måste vi markera dessa cykler med $u^{d}.$ För att illustrera detta, överväg $E[F_{6}].$

Vi får

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

vilket är

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

Än en gång att fortsätta som beskrivits i inledningen, finner vi

$\left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\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}$

vilket är

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

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

Det allmänna förfarandet är

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

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

$\left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {\sum _{d\mid k }z^{d}}{1-z}}\exp \left(\summa _{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å $E[F_{k}]$ är lika med $\tau (k)$ (antalet divisorer för $k$ ) så snart som $n\geq k.$ Det börjar på $1$ för $n=1$ och ökar med ett varje gång $n$ träffar en divisor av $k$ upp till och inklusive $k$ själv.

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

Vi konstruerar den bivariatgenererande funktionen $g(z,u)$ med hjälp av $b(k)$ , där $b(k)$ är en för alla cykler (varje cykel bidrar med en till det totala antalet cykler).

Observera att $g(z,u)$ har den slutna formen

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

och genererar de osignerade Stirlingtalen av det första slaget .

Vi har

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\summa _{ k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\summa _{k\geq 1}{\frac {z ^{k}}{k}}={\frac {1}{1-z}}\log {\frac {1}{1-z}}.$

Det förväntade antalet cykler är därför det övertonstalet $H_{n}$ , eller ungefär $\log n$ .

Antal permutationer med en cykel av längd större än n /2

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

Börja ännu en gång med den exponentiellt genererande funktionen $g(z,u)$ , denna gång av klassen ${\mathcal {P}}$ av permutationer enligt storlek där cykler med längd mer än $n/2$ är markerade med variabeln $u$ :

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

Det kan bara finnas en cykel som är längre än ${\displaystyle {\frac {n}{2}}} ,$ därför ges svaret på frågan av

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

eller

$n![z^{n}]\ exp \left(\log {\frac {1}{1-z}}-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z ^{k}}{k}}\höger)\summa _{k>\lgolv {\frac {n}{2}}\rgolv }^{\infty }{\frac {z^{k}}{k }}$

vilket är

$n![z^{n}]{\frac {1}{1-z}}\exp \left(-\summa _{ k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\summa _{k>\lfloor {\frac {n}{2}}\rgolv }^{\infty }{\frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z} }\summa _{m=0}^{\infty }{\frac {(-1)^{m}}{m!}}\left(\summa _{k>\lgolv {\frac {n}{ 2}}\rgolv }^{\infty }{\frac {z^{k}}{k}}\right)^{m+1}$

Exponenten för $z$ i termen som höjs till potensen $m+1$ är större än $\lfloor {\frac {n}{2}}\ rfloor$ och därmed inget värde för $m>0$ kan möjligen bidra till $[z^{n}].$

Därav följer att svaret är

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

$\sum _{k=1}^{n}{\frac {1}{k}}-\summa _{k=1}^{ \lgolv {\frac {n}{2}}\rgolv }{\frac {1}{k}}=\summa _{k=1}^{n}{\frac {1}{k}}-2 \sum _{k=1}^{\lgolv {\frac {n}{2}}\rgolv }{\frac {1}{2k}}=\summa _{k=1 \atop k\;{\ text{jämn}}}^{n}(1-2){\frac {1}{k}}+\summa _{k=1 \atop k\;{\text{udda}}}^{n} {\frac {1}{k}}$

äntligen ger

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

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

Vi kan använda den disjunkta cykelnedbrytningen 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. T.ex. cykeln $(1\;2\;34)$ faktorer som $(1\;2)\;(2\; 3)\;(3\;4)$ . Funktionen $b(k)$ för cykler är lika med $k-1$ och vi får

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

och

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

är det förväntade antalet transpositioner $T(n)$

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

där $H_{n}$ är $n^{th}$ övertonstalet . Vi kunde också ha erhållit denna formel genom att notera att antalet transpositioner erhålls genom att addera längden av alla cykler (vilket ger n ) och subtrahera en för varje cykel (vilket ger $\log n$ med föregående sektion).

Observera att $g(z,u)$ återigen genererar de osignerade stirlingtalen av det första slaget , men i omvänd ordning. Mer exakt har vi

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

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

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

och det

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

som vi såg vara EGF för de osignerade Stirlingtalen av det första slaget i avsnittet om permutationer som består av just 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 $\sigma$ och frågar om den förväntade storleken på cykeln som innehåller q . Här är funktionen $b(k)$ lika med $k^{2}$ , eftersom en cykel med längden k bidrar med k element som är på cykler med längden k . Observera att till skillnad från de tidigare beräkningarna måste vi medelvärde ut denna parameter efter att vi extraherat den från genereringsfunktionen (dividera med n ). Vi har

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

är den förväntade längden på cykeln som innehåller q

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

Sannolikheten att ett slumpmässigt element ligger på en cykel av storleken m

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

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\summa _{ 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

${\frac {1}{n}}[z^{n}]{\frac {z^{m}}{1-z}}={\begin{cases}{\frac {1}{ n}},&{\mbox{if }}n\geq m\\0,&{\mbox{annars.}}\end{cases}}$

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 i samma cykel. Detta är en annan genomsnittlig parameter. Funktionen b ( k ) är lika med ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}} ,$ eftersom en cykel med längden k bidrar med ${\begin{matrix}{k \choose m}\end{matrix}}$ delmängder av storlek m , där ${\begin{matrix}{k \choose m}=0\end{ matris}}$ för k < m . Detta ger

${\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\summa _{ k\geq m}{k \choose m}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {1}{m}}{\ frac {z^{m}}{(1-z)^{m}}}={\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m +1}}}.$

Med ett medelvärde erhåller vi att sannolikheten för att elementen i Q är i samma cykel är

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

eller

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

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

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

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

$\operatörsnamn {SET} (\operatörsnamn {CYC} _{\operatörsnamn {udda} }({\mathcal {Z}}))\operatörsnamn {SET} _{\operatörsnamn {jämn} }(\operatörsnamn {CYC } _{\operatörsnamn {jämn} }({\mathcal {Z}})).$

​​översätter till exponentiella genererande funktioner (EGF) får vi

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

eller

${\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\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).$

Detta förenklar till

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

eller

${\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 noll cykler 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 för $n\geq 2$ finns det $n!/2$ sådana permutationer.

Permutationer som är kvadrater

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. $(1\;8\;9\;11\;13)$ förvandlas till $(1\;9\;13\;8\;11)$ . Även cykler delas i två och ger ett par cykler som är hälften så stora som den ursprungliga cykeln, t.ex. $(5\;13\;6\;9)$ förvandlas till $(5\;6)\;(9\;13)$ . 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

$visning \operatörsnamn {SET} (\operatörsnamn {CYC} _{\operatörsnamn {odd} }({\mathcal {Z}}))\operatörsnamn {SET} _{\operatörsnamn {even} }(\operatörsnamn {CYC} _{ =2}({\mathcal {Z}}))\operatörsnamn {SET} _{\operatörsnamn {even} }(\operatörsnamn {CYC} _{=4}({\mathcal {Z}}))\operatörsnamn { SET} _{\operatörsnamn {even} }(\operatörsnamn {CYC} _{=6}({\mathcal {Z}}))\cdots }$

vilket ger EGF

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

De typer av permutationer som presenteras i de två föregående avsnitten, dvs permutationer som innehåller ett jämnt antal jämna cykler och permutationer som är kvadrater, är exempel på så kallade udda cykelinvarianter , studerade av Sung och Zhang (se externa länkar ). Termen udda cykel invariant betyder helt enkelt att medlemskap i respektive kombinatorisk klass är oberoende av storleken och antalet udda cykler som förekommer i permutationen. Faktum är att vi kan bevisa att alla udda cykelinvarianter lyder ett enkelt återkommande, som vi kommer att härleda. Först, här är några fler exempel på udda cykelinvarianter.

Permutationer där summan av längderna av de jämna cyklerna är sex

Denna klass har specifikationen

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

och genereringsfunktionen

${\sqrt {\frac {1+z}{1-z}}}\left({\frac {1}{6}}\left({\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}}}.$

De första värdena är

$_ ldots }$

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

Denna klass har specifikationen

$\operatörsnamn {SET} (\operatörsnamn {CYC} _{\operatörsnamn {odd} }({\mathcal {Z}}))\left(\operatörsnamn {SET} _{\geq 1 }(\operatörsnamn {CYC} _{=2}({\mathcal {Z}}))+\operatörsnamn {SET} _{\geq 1}(\operatörsnamn {CYC} _{=4}({\mathcal { Z}}))+\operatörsnamn {SET} _{\geq 1}(\operatörsnamn {CYC} _{=6}({\mathcal {Z}}))+\cdots \right)$

och genereringsfunktionen

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

Det finns en semantisk nyans här. Vi skulle kunna 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

$0,1,3,15,75,405,2835,221955,199ots$

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

Denna klass har specifikationen

$\operatörsnamn {SET} (\operatörsnamn {CYC} _{\operatörsnamn {odd} }({\mathcal {Z}}))\operatörsnamn {SET} (\operatörsnamn {CYC} _{=2}({\mathcal {Z}})+\operatörsnamn {CYC} _{=4}({\ mathcal {Z}}))$

och genereringsfunktionen

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

De första värdena är

$1,2,0602,0602,0602,0602,062,0620 7040,2207520,24282720,258128640,\ldots$

Upprepningen

Observera noga hur specifikationerna för den jämna cykelkomponenten är konstruerade. Det är bäst att tänka på dem i termer av att analysera träd. Dessa träd har tre nivåer. Noderna på den lägsta nivån representerar summor av produkter av cykler med jämn längd för singeltonen ${\mathcal {Z}}$ . Noderna på mellannivån representerar restriktioner för setoperatören. Slutligen summerar noden på översta nivån produkter av bidrag från mellannivån. Observera att begränsningar för setoperatorn, när de tillämpas på en genererande funktion som är jämn, kommer att bevara denna funktion, dvs producera en annan jämn genererande funktion. Men alla ingångar till setoperatörerna är jämna eftersom de härrör från cykler med jämn längd. Resultatet är att alla inblandade genererande funktioner har formen

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

där $h(z)$ är en jämn funktion. Detta innebär att

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

är också jämnt, och därmed

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

Genom att låta $g_{n}=[z^{n}]g(z)$ och extrahera koefficienter, finner vi att

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

$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 kräver ett bevis på det

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

där summan är över hela $n!$ permutationer av $[n]$ , $\sigma (\pi )$ är tecknet för $\pi$ , dvs. $\sigma (\pi )=1$ om $\pi$ är jämn och $\sigma (\pi )=-1$ om $\pi$ är udda, och $\nu (\pi )$ är antalet fasta punkter för $\pi$ .

ges tecknet för ${\displaystyle \pi } av$

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

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

Därför betraktar vi den kombinatoriska klassen

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

där ${\mathcal {U}}$ markerar ett minus längden på en bidragande cykel, och ${\mathcal {V}}$ markerar fixpunkter. Att översätta till att generera funktioner får vi

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

eller

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

Nu har vi

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

och följaktligen ges den önskade kvantiteten av

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

När vi gör beräkningen får vi

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

eller

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

Om man extraherar koefficienter finner vi att koefficienten $1/z$ är noll. Konstanten är ett, vilket inte stämmer överens med formeln (bör vara noll). För $n$ positiv får vi dock

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

eller

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

vilket är det önskade resultatet.

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

$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 &&\vdots \ddots &&\vdots \\b&&b&&b&&\cdots &&a\end{vmatrix}}.$

där $a,b\neq 0$ . Kom ihåg formeln för determinanten:

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

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

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

Vilket ger

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

och slutligen

$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

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

Kom ihåg att tecknet $\sigma (\pi )$ för en permutation $\pi$ ges av

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

där produkten sträcker sig över cyklerna c från den disjunkta cykelsammansättningen av $\pi$ .

Det följer att den kombinatoriska arten ${\mathcal {Q}}$ som reflekterar tecknen och cykelräkningen för uppsättningen av permutationer ges av

${\mathcal {Q}}=\operatörsnamn {SET} ({\mathcal {V}}\operatörsnamn {CYC} _{1}({\mathcal {Z}} )+{\mathcal {U}}{\mathcal {V}}\operatörsnamn {CYC} _{=2}({\mathcal {Z}}))+{\mathcal {U}}^{2}{\ mathcal {V}}\operatörsnamn {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}{\mathcal {V}}\operatörsnamn {CYC} _{ =4}({\mathcal {Z}})+{\mathcal {U}}^{4}{\mathcal {V}}\operatörsnamn {CYC} _{=5}({\mathcal {Z}}) +\cdots )$

där vi har använt ${\mathcal {U}}$ för att markera tecken och ${\mathcal {V}}$ för cykelräkningen.

Att översätta till att generera funktioner vi har

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

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

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

Nu de två genererande funktionerna $Q_{1}(z,v)$ och $Q_{2}(z,v)$ av jämn och udda permutationer av cykelräkning ges av

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

och

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

Vi kräver mängden

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

vilket är

$\left.{\frac {d}{dv}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{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}}.$

Slutligen, extrahera koefficienter från denna genererande funktion, får vi

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

vilket är

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

vilket är i sin tur

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

Detta avslutar beviset.

Se även

• Golomb–Dickman konstant

externa länkar

•   Sung, Philip; Zhang, Yan (2003). "Återkommande återkommande vid räkning av permutationer". CiteSeerX 10.1.1.91.1088 . {{ citera journal }} : 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 inuti stängda lådor, en fråga om sannolikhet

100 fångar

• Olika författare, Permutationer med en cykel > n/2
• Olika författare, A property of derangements
• Olika författare, Förväntat antal fixpunkter
• Peter Winkler, Sju pussel du tror att du inte måste ha hört rätt
• Olika författare, Les-Mathematiques.net . Cent prisonniers (på franska)