Willekeurige permutatiestatistieken - Random permutation statistics

De statistieken van willekeurige permutaties , zoals de cyclusstructuur van een willekeurige permutatie, zijn van fundamenteel belang bij de analyse van algoritmen , met name van sorteeralgoritmen, die op willekeurige permutaties werken. Stel bijvoorbeeld dat we quickselect (een neef van quicksort ) gebruiken om een ​​willekeurig element van een willekeurige permutatie te selecteren. Quickselect zal een gedeeltelijke sortering op de array uitvoeren, aangezien de array wordt gepartitioneerd volgens de spil. Een permutatie zal dus minder wanordelijk zijn nadat quickselect is uitgevoerd. De hoeveelheid wanorde die overblijft kan worden geanalyseerd met genererende functies. Deze genererende functies zijn op een fundamentele manier afhankelijk van de genererende functies van willekeurige permutatiestatistieken. Daarom is het van vitaal belang om deze genererende functies te berekenen.

Het artikel over willekeurige permutaties bevat een inleiding tot willekeurige permutaties.

De fundamentele relatie

Permutaties zijn sets van gelabelde cycli. Gebruikmakend van het gelabelde geval van de fundamentele stelling van Flajolet-Sedgewick en schrijven voor de verzameling permutaties en voor de singletonverzameling, hebben we ${\displaystyle \scriptstyle {\mathcal {P}}}$${\displaystyle \scriptstyle {\mathcal {Z}}}$

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

Vertalen naar exponentiële genererende functies (EGF's), hebben we:

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

waar we het feit hebben gebruikt dat de EGF van de combinatorische soorten permutaties (er zijn n ! permutaties van n elementen) is

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

Met deze ene vergelijking kan men een groot aantal permutatiestatistieken afleiden. Ten eerste, door termen van , dwz exp, te laten vallen , kunnen we het aantal cycli dat een permutatie bevat beperken, bijvoorbeeld door de EGF te beperken om permutaties te verkrijgen die twee cycli bevatten. Ten tweede, er rekening mee dat het EFG van gelabelde cycli, dwz , is ${\displaystyle \scriptstyle \operatornaam {SET} }$${\displaystyle \scriptstyle \operatornaam {SET} _{2}}$${\displaystyle \scriptstyle \operatornaam {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}}}$

omdat er k!/k gelabelde cycli zijn. Dit betekent dat door het weglaten van termen uit deze genererende functie, we de grootte van de cycli die voorkomen in een permutatie kunnen beperken en een EGF kunnen verkrijgen van de permutaties die alleen cycli van een bepaalde grootte bevatten.

In plaats van fietsen te verwijderen en te selecteren, kan men ook verschillende gewichten op fietsen van verschillende grootte plaatsen. Als is een gewichtsfunctie die alleen afhangt van de grootte k van de cyclus en kortheidshalve schrijven we ${\displaystyle b:\mathbb {N} \rightarrow \mathbb {R} }$

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

definiëren van de waarde van b voor een permutatie als de som van zijn waarden op de cycli, dan kunnen we cycli van lengte k markeren met u ^{b ( k )} en een twee-variabele genererende functie verkrijgen ${\displaystyle \sigma}$

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

Dit is een "gemengde" genererende functie: het is een exponentiële genererende functie in z en een gewone genererende functie in de secundaire parameter u. Differentiëren en evalueren bij u  = 1, hebben we

${\displaystyle {\frac {\partial}{\partial 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}\left(\sum _{\sigma \in S_{n}}b (\sigma )\right){\frac {z^{n}}{n!}}}$

Dit is de kansgenererende functie van de verwachting van b . Met andere woorden, de coëfficiënt van in deze machtreeks is de verwachte waarde van b op permutaties in , aangezien elke permutatie met dezelfde waarschijnlijkheid wordt gekozen . ${\displaystyle z^{n}}$${\displaystyle S_{n}}$${\displaystyle 1/n!}$

Dit artikel gebruikt de coëfficiëntextractie-operator [ z ⁿ ], gedocumenteerd op de pagina voor formele machtreeksen .

Aantal permutaties die involuties zijn

Een involutie is een permutatie σ zodat σ ² = 1 onder permutatiesamenstelling. Hieruit volgt dat σ alleen cycli van lengte één of twee mag bevatten, dwz de exponentieel genererende functie g ( z ) van deze permutaties is

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

Dit geeft de expliciete formule voor het totale aantal involuties onder de permutaties σ ∈  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 !}}.}$

Delen door n ! geeft de kans dat een willekeurige permutatie een involutie is. Deze nummers staan ​​bekend als telefoonnummers .

Aantal permutaties dat m de eenheidswortels zijn

Dit generaliseert het concept van een involutie. Een m de eenheidswortel is een permutatie σ zodat σ ^m = 1 onder permutatiesamenstelling. Elke keer dat we σ toepassen, gaan we een stap parallel langs al zijn cycli. Een cyclus van lengte d toegepast d keer levert de identiteitspermutatie op d elementen ( d vaste punten) en d is de kleinste waarde om dit te doen. Daarom moet m een veelvoud zijn van alle cyclusgroottes d , dwz de enige mogelijke cycli zijn die waarvan de lengte d een deler is van m . Hieruit volgt dat de EGF g ( x ) van deze permutaties is

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

Als m = p , waarbij p een priemgetal is, vereenvoudigt dit tot

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

Aantal permutaties van de orde precies k

Dit kan worden gedaan door Möbius inversie . Werkend met hetzelfde concept als in het vorige item merken we op dat de combinatorische soorten permutaties waarvan de volgorde k deelt wordt gegeven door ${\displaystyle {\mathcal {Q}}}$

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

Vertaling naar exponentiële genererende functies verkrijgen we de EGF van permutaties waarvan de volgorde k deelt , wat is

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

Nu kunnen we deze genererende functie gebruiken om permutaties van orde exact k te tellen . Laat het aantal permutaties op n zijn waarvan de volgorde exact d is en het aantal permutaties op n het aantal permutaties waarvan de volgorde k deelt . Dan hebben we ${\displaystyle p_{n,d}}$${\displaystyle q_{n,k}}$

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

Hieruit volgt door Möbius inversie dat

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

Daarom hebben we de EGF

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

Het gewenste aantal wordt dan gegeven door

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

Deze formule levert bijv. voor k  = 6 de 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}}}$

met de reeks waarden beginnend bij n  = 5

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

Voor k  = 8 krijgen we de 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}}}$

met de reeks waarden beginnend bij n  = 8

${\displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots}$(volgorde A061122 in de OEIS )

Eindelijk voor k  = 12 krijgen we de 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}}}$

met de reeks waarden beginnend bij n  = 7

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

Aantal permutaties die derangements zijn

Stel dat er n mensen op een feestje zijn, die allemaal een paraplu hebben meegenomen. Aan het einde van het feest kiest iedereen een paraplu uit de stapel paraplu's en bladeren. Wat is de kans dat niemand met zijn/haar eigen paraplu vertrokken is? Dit probleem is gelijk aan het tellen van permutaties zonder vaste punten ( derangements genoemd ), en dus de EGF, waar we vaste punten (cycli van lengte 1) aftrekken door de term z te verwijderen uit de fundamentele relatie is

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

Vermenigvuldiging met sommaties van de coëfficiënten van , dus , het totale aantal verstoringen, wordt gegeven door: ${\displaystyle 1/(1-z)}$${\displaystyle e^{-z}}$${\displaystyle D(n)}$

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

Er zijn dus ongeveer verstoringen en de kans dat een willekeurige permutatie een verstoring is is${\displaystyle n!/e}$${\displaystyle 1/e.}$

Dit resultaat kan ook worden bewezen door inclusie-uitsluiting . Gebruikmakend van de verzamelingen waar de verzameling permutaties die p fixeren aan te duiden , hebben we ${\displaystyle A_{p}}$${\displaystyle {\begin{matrix}1\leq p\leq n\end{matrix}}}$

${\displaystyle \left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\ left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\ rechts|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.}$

Deze formule telt het aantal permutaties met ten minste één vast punt. De kardinaliteiten zijn als volgt:

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

Vandaar dat het aantal permutaties zonder vast punt is

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

of

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

en we hebben de claim.

Er is een veralgemening van deze getallen, die bekend staat als rencontres-getallen , dat wil zeggen het aantal permutaties dat m vaste punten bevat. De overeenkomstige EGF wordt verkregen door cycli van grootte één te markeren met de variabele u , dwz b ( k ) gelijk aan één te kiezen voor en anders nul, wat de genererende functie van de verzameling permutaties oplevert door het aantal vaste punten: ${\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}.}$

Het volgt dat

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

en daarom

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

Dit houdt meteen in dat

${\displaystyle D(n,m)={n \kies m}D(nm,0)\;\;{\text{ and }}\,\;{\frac {D(n,m)}{n !}}\ongeveer {\frac {e^{-1}}{m!}}}$

voor n groot, m vast.

Volgorde van een willekeurige permutatie

Als P een permutatie is, is de volgorde van P het kleinste positieve gehele getal n waarvoor de identiteitspermutatie is. Dit is het kleinste gemene veelvoud van de lengtes van de cycli van P . ${\displaystyle P^{n}}$

Een stelling van Goh en Schmutz stelt dat als is de verwachte volgorde van een willekeurige permutatie van grootte n , dan ${\displaystyle \mu _{n}}$

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

waar de constante c is

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

Verstoringen met een even en een oneven aantal cycli

We kunnen dezelfde constructie als in de vorige paragraaf gebruiken om het aantal verstoringen met een even aantal cycli en het aantal met een oneven aantal cycli te berekenen . Om dit te doen, moeten we alle cycli markeren en vaste punten aftrekken, waardoor ${\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}}\rechts)^{u}.}$

Nu blijkt uit een zeer basale redenering dat het EFG van wordt gegeven door: ${\displaystyle q(z)}$${\displaystyle D_{0}(n)}$

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

We hebben dus

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

wat is?

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

Aftrekken van , vinden we ${\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).}$

Het verschil van deze twee ( en ) is${\displaystyle D_{0}(n)}$${\displaystyle D_{1}(n)}$${\displaystyle n-1.}$

Honderd gevangenen

Een gevangenisdirecteur wil ruimte maken in zijn gevangenis en overweegt honderd gevangenen te bevrijden, waardoor honderd cellen vrijkomen. Hij verzamelt daarom honderd gevangenen en vraagt ​​hen het volgende spel te spelen: hij zet honderd urnen op een rij, elk met de naam van één gevangene, waarbij de naam van elke gevangene precies één keer voorkomt. Het spel wordt als volgt gespeeld: elke gevangene mag in vijftig urnen kijken. Vindt hij of zij zijn of haar naam niet in een van de vijftig urnen, dan worden alle gevangenen direct geëxecuteerd, anders gaat het spel verder. De gevangenen hebben even de tijd om een ​​strategie te bepalen, wetende dat als het spel eenmaal is begonnen, ze niet meer met elkaar kunnen communiceren, de urnen op geen enkele manier kunnen markeren of de urnen of de namen erin kunnen verplaatsen. Als je urnen willekeurig kiest, zijn hun overlevingskansen bijna nul, maar er is een strategie die hen een overlevingskans van 30% geeft, ervan uitgaande dat de namen willekeurig aan urnen worden toegewezen - wat is het?

Allereerst is de overlevingskans met behulp van willekeurige keuzes:

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

dus dit is zeker geen praktische strategie.

De 30% overlevingsstrategie is om de inhoud van de urnen te beschouwen als een permutatie van de gevangenen en doorkruisende cycli. Om de notatie eenvoudig te houden, wijst u een nummer toe aan elke gevangene, bijvoorbeeld door hun namen alfabetisch te sorteren. De urnen kunnen daarna worden beschouwd als nummers in plaats van namen. Nu definieert de inhoud van de urnen duidelijk een permutatie. De eerste gevangene opent de eerste urn. Als hij zijn naam vindt, is hij klaar en overleeft hij. Anders opent hij de urn met het nummer dat hij in de eerste urn heeft gevonden. Het proces herhaalt zich: de gevangene opent een urn en overleeft als hij zijn naam vindt, anders opent hij de urn met het zojuist opgehaalde nummer, tot een limiet van vijftig urnen. De tweede gevangene begint met urn nummer twee, de derde met urn nummer drie, enzovoort. Deze strategie is precies gelijk aan een doorloop van de cycli van de permutatie voorgesteld door de urnen. Elke gevangene begint met de urn met zijn nummer en blijft zijn cyclus doorlopen tot een limiet van vijftig urnen. Het nummer van de urn die zijn nummer bevat, is de voorafbeelding van dat nummer onder de permutatie. Vandaar dat de gevangenen overleven als alle cycli van de permutatie ten hoogste vijftig elementen bevatten. We moeten aantonen dat deze kans minimaal 30% is.

Merk op dat dit veronderstelt dat de directeur de permutatie willekeurig kiest; als de bewaker anticipeert op deze strategie, kan hij eenvoudig een permutatie kiezen met een cyclus van lengte 51. Om dit te verhelpen, kunnen de gevangenen vooraf een willekeurige permutatie van hun namen afspreken.

We beschouwen het algemene geval van het openen van gevangenen en urnen. We berekenen eerst de complementaire kans, dat wil zeggen dat er een cyclus is van meer dan elementen. Met dit in gedachten introduceren we: ${\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)}$

of

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

zodat de gewenste kans is

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

omdat de cyclus van meer dan elementen noodzakelijkerwijs uniek zal zijn. Gebruikmakend van het feit dat , vinden we dat ${\displaystyle n}$${\displaystyle 2(n+1)>2n}$

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

wat oplevert

${\displaystyle [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)=\sum _{k=n+1}^{2n} {\frac {1}{k}}=H_{2n}-H_{n}.}$

Ten slotte, met behulp van een integrale schatting zoals Euler-Maclaurin-sommatie of de asymptotische expansie van het n- de harmonische getal , verkrijgen we

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

zodat

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

of ten minste 30%, zoals wordt beweerd.

Een gerelateerd resultaat is dat asymptotisch de verwachte lengte van de langste cyclus λn is, waarbij λ de Golomb-Dickman-constante is , ongeveer 0,62.

Dit voorbeeld is te danken aan Anna Gál en Peter Bro Miltersen; raadpleeg de paper van Peter Winkler voor meer informatie, en zie de discussie op Les-Mathematiques.net . Raadpleeg de referenties over 100 gevangenen voor links naar deze referenties.

De bovenstaande berekening kan op een meer eenvoudige en directe manier worden uitgevoerd, als volgt: merk eerst op dat een permutatie van elementen ten hoogste één cyclus bevat met een lengte die strikt groter is dan . Dus, als we aanduiden ${\displaystyle 2n}$${\displaystyle n}$

${\displaystyle p_{k}=\Pr[{\mbox{er is een cyclus van lengte }}k],}$

dan

${\displaystyle \Pr[{\mbox{er is een cyclus van lengte}}>n]=\sum _{k=n+1}^{2n}p_{k}.}$

Voor het aantal permutaties die een cyclus lengte bevatten precies is ${\displaystyle k>n}$${\displaystyle k}$

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

Toelichting: is het aantal manieren om de elementen waaruit de cyclus bestaat te kiezen ; is het aantal manieren om items in een cyclus te rangschikken ; en is het aantal manieren om de overige elementen te permuteren. Er wordt hier niet dubbel geteld omdat er maximaal één cyclus van lengte is wanneer . Dus, ${\displaystyle {{2n} \kies k}}$${\displaystyle k}$${\displaystyle {\frac {k!}{k}}}$${\displaystyle k}$${\displaystyle (2n-k)!}$${\displaystyle k}$${\displaystyle k>n}$

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

We concluderen dat:

${\displaystyle \Pr[{\mbox{er is een cyclus van lengte}}>n]=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n }-H_{n}.}$

Een variatie op het 100 gevangenen probleem (sleutels en dozen)

Er is een nauw verwant probleem dat goed past bij de hier gepresenteerde methode. Stel dat je n dozen hebt besteld. Elke doos bevat een sleutel naar een andere doos of mogelijk zelf die een permutatie van de sleutels geeft. Je mag k van deze n vakken allemaal tegelijk selecteren en ze tegelijkertijd openbreken om toegang te krijgen tot k sleutels. Wat is de kans dat je met deze sleutels alle n vakjes kunt openen , waarbij je een gevonden sleutel gebruikt om het vakje waartoe het behoort te openen en te herhalen.

De wiskundige verklaring van dit probleem is als volgt: kies een willekeurige permutatie op n elementen en k waarden uit het bereik 1 tot n , ook willekeurig, noem deze tekens. Wat is de kans dat er op elke cyclus van de permutatie minstens één teken staat? De claim is dat deze kans k/n is .

De soorten permutaties door cycli met een niet-lege subset van elke cyclus die wordt gemarkeerd, heeft de specificatie: ${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatornaam {SET} \left(\sum _{q\geq 1}\operatornaam {CYC} _{=q}({\mathcal {Z}}) \times \ som _{p=1}^{q}{q \kies p}{\mathcal {U}}^{p}\right).}$

De index in de binnenste som begint bij één omdat we op elke cyclus minstens één cijfer moeten hebben.

Als we de specificatie vertalen naar het genereren van functies, verkrijgen we de bivariate genererende functie

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

Dit vereenvoudigt om

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

of

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

Om coëfficiënten hieruit te extraheren, herschrijf je zo

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

Daaruit volgt nu dat

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

en daarom

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

Delen door om te verkrijgen ${\displaystyle {n \kies k}}$

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

We hoeven niet te delen door n! omdat exponentieel is in z . ${\displaystyle G(z,u)}$

Aantal permutaties met m cycli

Het toepassen van de fundamentele stelling van Flajolet-Sedgewick , dat wil zeggen de gelabelde opsommingsstelling met , op de verzameling ${\displaystyle G=S_{m}}$

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

we verkrijgen de genererende functie

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

De voorwaarde

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

levert de getekende Stirling-getallen van de eerste soort op , en is de EGF van de niet-ondertekende Stirling-getallen van de eerste soort, dat wil zeggen ${\displaystyle g_{m}(z)}$

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

We kunnen de OGF van de getekende Stirling-getallen berekenen voor n vast, d.w.z

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

Beginnen met

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

wat oplevert

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

Als we dit optellen, krijgen we:

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

Met behulp van de formule met de logaritme voor aan de linkerkant, de definitie van aan de rechterkant en de binominale stelling , verkrijgen we ${\displaystyle g_{m}(z)}$${\displaystyle s_{n}(w)}$

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

Als we de coëfficiënten van vergelijken en de definitie van de binomiale coëfficiënt gebruiken , hebben we uiteindelijk ${\displaystyle z^{n}}$

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

een vallende faculteit . De berekening van de OGF van de niet-ondertekende Stirling-getallen van de eerste soort werkt op een vergelijkbare manier.

Verwacht aantal cycli van een bepaalde grootte m

In dit probleem gebruiken we een bivariate genererende functie g ( z ,  u ) zoals beschreven in de inleiding. De waarde van b voor een cyclus niet van grootte m is nul, en één voor een cyclus van grootte m . Wij hebben

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

of

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

Dit betekent dat het verwachte aantal cycli van grootte m in een permutatie met lengte n kleiner dan m nul is (uiteraard). Een willekeurige permutatie van een lengte van ten minste m bevat gemiddeld 1/ m cycli van lengte m . In het bijzonder bevat een willekeurige permutatie ongeveer één vast punt.

De OGF van het verwachte aantal cycli met een lengte kleiner dan of gelijk aan m is dus

${\displaystyle {\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}{\mbox{ en }}[z ^{n}]{\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}=H_{m}{\ mbox{ voor }}n\geq m}$

waarbij H _m het m- de harmonische getal is . Daarom is het verwachte aantal cycli met een lengte van maximaal m in een willekeurige permutatie ongeveer ln  m .

Momenten van vaste punten

De gemengde GF van de verzameling permutaties door het aantal vaste punten is ${\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).}$

Laat de willekeurige variabele X het aantal vaste punten van een willekeurige permutatie zijn. Met behulp van Stirlinggetallen van de tweede soort hebben we de volgende formule voor het m -de moment van 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}),}$

waar is een dalende faculteit . Met behulp van , hebben we ${\displaystyle (X)_{k}}$${\displaystyle g(z,u)}$

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

die nul is wanneer , en één anders. Vandaar dat alleen termen met bijdragen aan de som. Dit levert ${\displaystyle k>n}$${\displaystyle k<=n}$

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

Verwacht aantal vaste punten in willekeurige permutatie verhoogd tot een macht k

Stel dat je een willekeurige permutatie kiest en deze verheft tot een bepaalde macht , met een positief geheel getal en vraagt ​​naar het verwachte aantal vaste punten in het resultaat. Geef deze waarde aan met . ${\displaystyle \sigma}$${\displaystyle k}$${\displaystyle k}$${\displaystyle E[F_{k}]}$

Voor elke deler van een cyclus van lengte splitst in vaste punten wanneer verheven tot de macht. Daarom moeten we deze cycli markeren met Om dit te illustreren overwegen${\displaystyle d}$${\displaystyle k}$${\displaystyle d}$${\displaystyle d}$${\displaystyle k.}$${\displaystyle u^{d}.}$${\displaystyle E[F_{6}].}$

We krijgen

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

wat is?

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

Nog een keer doorgaan zoals beschreven in de inleiding, vinden we:

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

wat is?

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

De conclusie is dat voor en er gemiddeld vier vaste punten zijn. ${\displaystyle E[F_{6}]=4}$${\displaystyle n\geq 6}$

De algemene procedure is:

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

Nog een keer doorgaan zoals voorheen, vinden we:

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

We hebben laten zien dat de waarde van gelijk is aan (het aantal delers van ) zodra Het begint bij voor en met één toeneemt telkens wanneer het een deler tot en met zichzelf raakt . ${\displaystyle E[F_{k}]}$${\displaystyle \tau (k)}$${\displaystyle k}$${\displaystyle n\geq k.}$${\displaystyle 1}$${\displaystyle n=1}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k}$

Verwacht aantal cycli van een willekeurige lengte van een willekeurige permutatie

We construeren de bivariate genererende functie met , waarbij één is voor alle cycli (elke cyclus draagt ​​één bij aan het totale aantal cycli). ${\displaystyle g(z,u)}$${\displaystyle b(k)}$${\displaystyle b(k)}$

Merk op dat de gesloten vorm heeft ${\displaystyle g(z,u)}$

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

en genereert de niet-ondertekende Stirling-getallen van de eerste soort .

Wij hebben

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

Vandaar dat het verwachte aantal cycli het harmonische getal is , of ongeveer . ${\displaystyle H_{n}}$${\displaystyle \log n}$

Aantal permutaties met een cyclus met een lengte groter dan n /2

(Merk op dat sectie honderd gevangenen precies hetzelfde probleem bevat met een zeer vergelijkbare berekening, plus ook een eenvoudiger elementair bewijs.)

Begin opnieuw met de exponentiële genererende functie , deze keer van de klasse van permutaties volgens grootte waar cycli van meer dan lengte zijn gemarkeerd met de variabele : ${\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}}\right). }$

Er kan maar één cyclus langer zijn dan , vandaar dat het antwoord op de vraag wordt gegeven door ${\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}}}$

of

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

wat is?

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\exp \left(-\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}}=n![z^{n}]{\frac {1}{1-z}}\sum _{m=0}^{\infty }{\ frac {(-1)^{m}}{m!}}\left(\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z ^{k}}{k}}\rechts)^{m+1}}$

De exponent van in de term wordt verheven tot de macht is groter dan en daarom kan er geen waarde voor bijdragen aan${\displaystyle z}$${\displaystyle m+1}$${\displaystyle \lvloer {\frac {n}{2}}\rvloer}$${\displaystyle m>0}$${\displaystyle [z^{n}].}$

Hieruit volgt dat het antwoord is:

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

De som heeft een alternatieve representatie die men bijvoorbeeld tegenkomt in de 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 \atop k\;{\text{even}}}^{n}(1-2 ){\frac {1}{k}}+\sum _{k=1 \atop k\;{\text{odd}}}^{n}{\frac {1}{k}}}$

eindelijk geven

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

Verwacht aantal transposities van een willekeurige permutatie

We kunnen de disjuncte cyclusdecompositie van een permutatie gebruiken om deze te ontbinden als een product van transposities door een cyclus met lengte k te vervangen door k  1 transposities. Bijvoorbeeld de cyclusfactoren als . De functie voor cycli is gelijk aan en we verkrijgen ${\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}}$

en

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

Het verwachte aantal omzettingen is dus ${\displaystyle T(n)}$

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

waar is het Harmonische getal . We hadden deze formule ook kunnen krijgen door op te merken dat het aantal transposities wordt verkregen door de lengtes van alle cycli op te tellen (wat n geeft ) en er één af te trekken voor elke cyclus (wat in de vorige sectie geeft). ${\displaystyle H_{n}}$${\displaystyle n^{de}}$ ${\displaystyle \log n}$

Merk op dat opnieuw de niet-ondertekende Stirling-nummers van de eerste soort worden gegenereerd , maar in omgekeerde volgorde. Meer precies, we hebben ${\displaystyle g(z,u)}$

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

Om dit te zien, moet u er rekening mee houden dat het bovenstaande gelijk is aan:

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

en dat

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

die we zagen als de EGF van de niet-ondertekende Stirling-getallen van de eerste soort in de sectie over permutaties die uit precies m cycli bestaan.

Verwachte cyclusgrootte van een willekeurig element

We selecteren een willekeurig element q van een willekeurige permutatie en vragen naar de verwachte grootte van de cyclus die q bevat . Hier is de functie gelijk aan , omdat een cyclus van lengte k k elementen bijdraagt die op cycli van lengte k staan . Merk op dat we, in tegenstelling tot de vorige berekeningen, deze parameter moeten uitgemiddelden nadat we deze uit de genererende functie hebben geëxtraheerd (delen door n ). Wij hebben ${\displaystyle \sigma}$${\displaystyle b(k)}$${\displaystyle k^{2}}$

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

Vandaar dat de verwachte lengte van de cyclus die q bevat is

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

Kans dat een willekeurig element op een cyclus van grootte m . ligt

Deze gemiddelde parameter geeft de kans weer dat als we opnieuw een willekeurig element van een willekeurige permutatie selecteren, het element op een cyclus van grootte m ligt . De functie is gelijk aan for en anders nul, omdat alleen cycli met lengte m bijdragen, namelijk m elementen die op een cyclus met lengte m liggen . Wij hebben ${\displaystyle [n]}$${\displaystyle b(k)}$${\displaystyle m}$${\displaystyle m=k}$

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

Hieruit volgt dat de kans dat een willekeurig element op een cyclus met lengte m ligt, is

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

Waarschijnlijkheid dat een willekeurige deelverzameling van [ n ] op dezelfde cyclus ligt

Selecteer een willekeurige deelverzameling Q van [ n ] die m elementen en een willekeurige permutatie bevat, en vraag naar de kans dat alle elementen van Q in dezelfde cyclus liggen. Dit is een andere gemiddelde parameter. De functie b ( k ) is gelijk aan , omdat een cyclus met lengte k deelverzamelingen van grootte m bijdraagt , waarbij voor k < m . Dit levert ${\displaystyle {\begin{matrix}{k \kies m}\end{matrix}}}$${\displaystyle {\begin{matrix}{k \kies m}\end{matrix}}}$${\displaystyle {\begin{matrix}{k \kies m}=0\end{matrix}}}$

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

Als we het gemiddelde nemen, krijgen we dat de kans dat de elementen van Q zich in dezelfde cyclus bevinden, is

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

of

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

In het bijzonder is de kans dat twee elementen p < q zich in dezelfde cyclus bevinden 1/2.

Aantal permutaties met een even aantal even cycli

We kunnen de fundamentele stelling van Flajolet-Sedgewick direct gebruiken en meer geavanceerde permutatiestatistieken berekenen. (Kijk op die pagina voor een uitleg van hoe de operatoren die we zullen gebruiken worden berekend.) De verzameling permutaties die een even aantal even cycli bevat, wordt bijvoorbeeld gegeven door

${\displaystyle \operatornaam {SET} (\operatornaam {CYC} _{\operatornaam {oneven} }({\mathcal {Z}}))\operatornaam {SET} _{\operatornaam {even} }(\operatornaam {CYC } _{\operatornaam {even} }({\mathcal {Z}})).}$

Vertalen naar exponentiële genererende functies (EGF's), verkrijgen we:

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

of

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

Dit vereenvoudigt om

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

of

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

Dit zegt dat er één permutatie van grootte nul is die een even aantal even cycli bevat (de lege permutatie, die nul cycli van even lengte bevat), één zo'n permutatie van grootte één (het vaste punt, dat ook nul cycli van even lengte bevat) ), en dat voor , zijn er dergelijke permutaties. ${\displaystyle n\geq 2}$${\displaystyle n!/2}$

Permutaties die vierkanten zijn

Bedenk wat er gebeurt als we een permutatie kwadrateren. Vaste punten worden toegewezen aan vaste punten. Oneven cycli worden toegewezen aan oneven cycli in een één-op-één correspondentie, bijvoorbeeld verandert in . Zelfs cycli worden in tweeën gesplitst en produceren een paar cycli van de helft van de oorspronkelijke cyclus, bijvoorbeeld verandert in . Vandaar dat permutaties die vierkant zijn een willekeurig aantal oneven cycli kunnen bevatten, en een even aantal cycli van grootte twee, een even aantal cycli van grootte vier enz., en worden gegeven door ${\displaystyle (1\;8\;9\;11\;13)}$${\displaystyle (1\;9\;13\;8\;11)}$${\displaystyle (5\;13\;6\;9)}$${\displaystyle (5\;6)\;(9\;13)}$

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

wat het EGF . oplevert

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

Oneven cyclus invarianten

De typen permutaties die in de voorgaande twee paragrafen zijn gepresenteerd, dwz permutaties die een even aantal even cycli bevatten en permutaties die kwadraten zijn, zijn voorbeelden van zogenaamde oneven cyclusinvarianten , bestudeerd door Sung en Zhang (zie externe links ). De term oneven cyclusinvariant betekent eenvoudig dat lidmaatschap van de respectieve combinatorische klasse onafhankelijk is van de grootte en het aantal oneven cycli die in de permutatie voorkomen. In feite kunnen we bewijzen dat alle oneven cyclusinvarianten gehoorzamen aan een eenvoudige herhaling, die we zullen afleiden. Ten eerste zijn hier nog enkele voorbeelden van oneven cyclusinvarianten.

Permutaties waarbij de som van de lengtes van de even cycli zes is

Deze klasse heeft de specificatie:

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

en de genererende functie

${\displaystyle {\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 eerste paar waarden zijn

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

Permutaties waarbij alle even cycli dezelfde lengte hebben

Deze klasse heeft de specificatie:

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

en de genererende functie

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

Er is hier een semantische nuance. We kunnen permutaties die geen even cycli bevatten, beschouwen als behorend tot deze klasse, aangezien nul even is . De eerste paar waarden zijn

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

Permutaties waarbij de maximale lengte van een even cyclus vier is

Deze klasse heeft de specificatie:

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

en de genererende functie

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

De eerste paar waarden zijn

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

de herhaling

Let goed op hoe de specificaties van het even cycle-onderdeel zijn opgebouwd. Het is het beste om ze te beschouwen in termen van ontleden bomen. Deze bomen hebben drie niveaus. De knooppunten op het laagste niveau vertegenwoordigen sommen producten van even lengte cycli van de singleton . De knooppunten op het middelste niveau vertegenwoordigen beperkingen van de set-operator. Ten slotte somt het knooppunt op het bovenste niveau de producten van bijdragen van het middelste niveau op. Merk op dat beperkingen van de set-operator, wanneer toegepast op een genererende functie die even is, dit kenmerk zal behouden, dwz een andere even genererende functie zal produceren. Maar alle invoer voor de set-operators is even, omdat ze voortkomen uit cycli van even lengte. Het resultaat is dat alle betrokken genererende functies de vorm hebben ${\displaystyle {\mathcal {Z}}}$

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

waar is een even functie. Dit betekent dat ${\displaystyle h(z)}$

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

is even, ook, en vandaar

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

Door coëfficiënten te laten en te extraheren, vinden we dat: ${\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{ of }}\quad 2{\frac {g_{2m+1 }}{(2m+1)!}}=2{\frac {g_{2m}}{(2m)!}}}$

wat de herhaling oplevert

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

Een probleem van de Putnam-competitie van 2005

Een link naar de Putnam wedstrijdwebsite verschijnt in de sectie Externe links . Het probleem vraagt ​​om een ​​bewijs dat:

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

waar de som is over alle permutaties van , is het teken van , dwz als is even en als is oneven, en is het aantal vaste punten van . ${\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 wordt het teken van gegeven door ${\displaystyle \pi}$

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

waarbij het product zich over alle cycli c van bevindt , zoals uitgelegd op de pagina over even en oneven permutaties . ${\displaystyle \pi}$

Daarom beschouwen we de combinatorische klasse

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

waar markeert één minus de lengte van een bijdragende cyclus, en markeert vaste punten. Vertalen naar het genereren van functies, verkrijgen we: ${\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} }\Rechtsaf)}$

of

${\displaystyle \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 hebben we

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

en daarom wordt de gewenste hoeveelheid gegeven door

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

Door de berekening uit te voeren, verkrijgen we:

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

of

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

Als we coëfficiënten extraheren, vinden we dat de coëfficiënt van nul is. De constante is één, wat niet overeenkomt met de formule (moet nul zijn). Voor positief krijgen we echter ${\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)!}}\right)}$

of

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

wat het gewenste resultaat is.

Interessant terzijde, we merken op dat dit kan worden gebruikt om de volgende determinant van een matrix te evalueren : ${\displaystyle g(z,u,v)}$${\displaystyle n\times 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 && \ddots &&\vdots \\b&&b&&b&&\cdots &&a\end{vmatrix}}.}$

waar . Denk aan de formule voor de determinant: ${\displaystyle a,b\neq 0}$

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

Nu de waarde van het product op de juiste een permutatie is , waarbij f het aantal vaste punten . Vandaar ${\displaystyle \pi}$${\displaystyle a^{f}b^{nf}}$${\displaystyle \pi}$

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

wat oplevert

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

en tenslotte

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

Het verschil tussen het aantal cycli in even en oneven permutaties

Hier proberen we aan te tonen dat dit verschil wordt gegeven door

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

Bedenk dat het teken van een permutatie wordt gegeven door ${\displaystyle \sigma (\pi)}$${\displaystyle \pi}$

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

waarbij het product varieert over de cycli c van de disjuncte cyclussamenstelling van . ${\displaystyle \pi}$

Hieruit volgt dat de combinatorische soort die de tekens en het aantal cycli van de reeks permutaties weerspiegelt, wordt gegeven door ${\displaystyle {\mathcal {Q}}}$

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

waar we hebben gebruikt om borden te markeren en voor de cyclustelling. ${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {V}}}$

Vertalen naar het genereren van functies die we hebben

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

Dit vereenvoudigt om

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

wat is?

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

Nu worden de twee genererende functies en van even en oneven permutaties door cyclustelling gegeven door ${\displaystyle Q_{1}(z,v)}$${\displaystyle Q_{2}(z,v)}$

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

en

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

We hebben de hoeveelheid nodig:

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

wat is?

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

Als we ten slotte coëfficiënten uit deze genererende functie halen, verkrijgen we:

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

wat is?

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

wat op zijn beurt is

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

Hiermee is het bewijs afgesloten.

Zie ook

• Golomb-Dickman-constante

Referenties

Externe links

• Panholzer, Alois; Prodinger, Helmut; Riedel, Marko. "Het meten van post-quickselect-stoornis" (PDF) . Cite journaal vereist |journal=( hulp )
• Archief van William Lowell Putnam Competitie
• Gezongen, Philip; Zhang, Yan. "Terugkerende recidieven bij het tellen van permutaties". CiteSeerX  10.1.1.91.1088 . Cite journaal vereist |journal=( hulp )
• Marko Riedel et al., Het verschil van het aantal cycli van even en oneven permutaties
• Marko Riedel et al., Sleutels in gesloten dozen, een vraag over waarschijnlijkheid

100 gevangenen

• Anna Gál, Peter Bro Miltersen, De celprobe- complexiteit van beknopte gegevensstructuren
• Diverse auteurs, Permutaties met een cyclus > n/2
• Diverse auteurs, A property of derangements
• Diverse auteurs, Verwacht aantal vaste punten
• Peter Winkler, Zeven puzzels waarvan je denkt dat je ze niet goed gehoord hebt
• Diverse auteurs, Les-Mathematiques.net . Cent prisonniers (in het Frans)