Permutatie

Een permutatie is een begrip uit de discrete wiskunde. Een permutatie van een eindig aantal elementen, van bijvoorbeeld voorwerpen of getallen is een herschikking ervan, dat wil zeggen het uitvoeren van geen of meer verwisselingen. Uitgaande van een bepaalde beginvolgorde van de betreffende elementen ontstaat daaruit een permutatie door daar een eerste uit te kiezen, ze daarna allemaal een keer te kiezen en de volgorde te onthouden waarin ze zijn gekozen. Alle elementen blijven onder een permutatie behouden, alleen hun volgorde verandert. Ook het resultaat van het uitvoeren van een permutatie wordt vaak een permutatie genoemd.

Permutaties zijn onder meer belangrijk in de combinatoriek, kansrekening en statistiek.

Een variatie, een greep van een aantal elementen uit een verzameling, waarin de volgorde waarin zij worden getrokken telt, wordt ook vaak een permutatie genoemd. Een dergelijke permutatie lijkt daarbij op een combinatie, waarbij ook een aantal elementen uit een verzameling wordt genomen. Het verschil tussen een permutatie en een combinatie is dat bij het bepalen van het aantal mogelijkheden bij een permutatie de volgorde waarin de elementen worden getrokken telt, terwijl die volgorde bij een combinatie niet telt.

Dit artikel gaat verder alleen over permutaties waarbij elementen van plaats worden verwisseld. Het mag daarbij eventueel over oneindig elementen gaan.

Definitie

Een permutatie van een verzameling wordt gedefinieerd als een bijectie van die verzameling op zichzelf.^[1] Deze definitie concentreert zich op de wezenlijke eigenschappen van een permutatie en heeft als voordeel dat permutaties gemakkelijk samengesteld kunnen worden.

Opmerkingen

Als er bijvoorbeeld drie objecten zijn, genummerd 1, 2 en 3, en drie posities, ook genummerd 1, 2 en 3, dan bepaalt deze nummering een bijectie die aan elk object de positie met hetzelfde nummer toevoegt. Men kan nu de plaatsing van de objecten in de posities (één object per positie, een bijectie) beschrijven via de permutatie van de verzameling { 1, 2, 3 } die het objectnummer per positienummer aangeeft, bijvoorbeeld ( 2, 3, 1 ), in cykelnotatie (1 2 3), of de permutatie die het positienummer per objectnummer aangeeft, in dit geval ( 3, 1, 2 ), in cykelnotatie (3 2 1). Deze bijecties zijn elkaars inverse.

Als de objecten in eerste instantie nog geen nummer hebben en men wil een verplaatsing beschrijven, dan kan men de objecten nummeren op basis van de oorspronkelijke plaats. Omgekeerd, als de plaatsen in eerste instantie nog geen nummer hebben en men wil een verplaatsing beschrijven, dan kan men de plaatsen nummeren op basis van het object dat in eerste instantie op die plaats staat. Als de plaatsen op een rij liggen ligt echter nummering op basis van de plaats in de rij meer voor de hand.

De permutaties van een totaal geordende verzameling corresponderen een-op-een met de mogelijke totale ordeningen van die verzameling.

Neem het voorbeeld met vier knikkers, een rode, gele, groene en een blauwe knikker. Er zijn 4! = 4 x 3 x 2 x 1 = 24 permutaties mogelijk van deze vier, bijvoorbeeld rood, geel, groen, blauw en rood, groen, geel, blauw. De permutaties waarbij de knikkers in omgekeerde volgorde liggen tellen daarbij samen voor twee permutaties. Blauw, groen, geel, rood is niet hetzelfde als rood, geel, groen, blauw.

Aantal mogelijke permutaties

Het aantal mogelijke permutaties van $n$ verschillende elementen wordt genoteerd als $n!$ (lees: $n$ faculteit). Met behulp van de recursierelatie

n!=n(n-1)!

en

1!=1

kan $n!$ voor een willekeurig aantal elementen $n$ worden berekend. Hoewel het niet voor de hand ligt om over het aantal permutaties van 0 elementen te spreken, is het een afspraak dat

0!=1

,

wat correspondeert met het feit dat er één afbeelding is van de lege verzameling naar zichzelf, en dat deze een bijectie is.

Soms wordt ook een variatie als permutatie aangeduid.

Speciale permutaties

De identieke permutatie is de identieke afbeelding: de bijectie die ieder element op zichzelf afbeeldt.

Een transpositie is een permutatie die alleen in twee elementen van de identieke permutatie afwijkt, die elkaars plaats innemen.

Voorbeeld van permutatie die is samengesteld uit cyclische permutaties van disjuncte delen

Een cyclische permutatie houdt in dat men met een willekeurig voorwerp begint, en vervolgens steeds de volgende neemt, en na de laatste de eerste neemt, en vervolgens weer steeds de volgende neemt tot men ze allemaal gehad heeft. Voorbeeld: de volgorde (1, 2, 3, 4, 5) wordt (3, 4, 5, 1, 2).

Een permutatie zonder dekpunten of een derangement is een permutatie van een aantal elementen waarbij geen van de elementen op z'n plaats blijft. Een dekpunt is een element dat onder een permutatie niet van plaats verandert.

Permutatiegroep

Twee permutaties $\pi _{1}$ en $\pi _{2}$ op een verzameling $A$ kunnen worden samengesteld. De samenstelling $\pi _{2}\circ \pi _{1}$ is opnieuw een permutatie, en wel op een zodanige manier dat de bewerking " $\circ$ " van de collectie ${\mathcal {S}}(A)$ van alle permutaties van $A$ een groep maakt. In het bijzonder noteert men ${\mathcal {S}}_{n}$ voor de groep van alle permutaties van de verzameling $\{1,2,\ldots ,n\}$ . ${\mathcal {S}}_{n}$ is de symmetrische groep van $n$ elementen. Voor $n\geq 3$ is deze groep niet abels.

Een permutatiegroep is een ondergroep van de groep van alle permutaties op een gegeven verzameling. Elke groep $G$ is isomorf met een permutatiegroep op de verzameling $G$ . Associeer daartoe het groepselement $g$ met de permutatie $\pi _{g}$ die ieder element $h\in G$ afbeeldt op het groepselement $g\circ h$ .

Notatie

Neem de beginvolgorde (1, 2, 3, 4, 5) en de permutatie (3, 4, 5, 1, 2). De permutatie kan zo worden genoteerd, maar een andere mogelijkheid is de cykelnotatie, in dit geval (1 3 5 2 4), zonder komma's. Vergelijk het met

{\begin{matrix}1&2&3&4&5\\3&4&5&1&2\end{matrix}}

In de cykelnotatie blijft van deze twee rijen alleen de onderste staan.

Even en oneven permutaties

Elke permutatie van een eindige verzameling kan als een samenstelling worden geschreven van een eindig aantal verwisselingen, bijvoorbeeld door het element dat op de eerste plaats moet komen te verwisselen met het element op de eerste plaats (als het niet al op de eerste plaats staat), vervolgens het element dat op de tweede plaats moet komen te verwisselen met het element dat (nu) op de tweede plaats staat, enzovoort. Bij de permutatie van (1, 2, 3, 4) naar de volgorde (2, 3, 4, 1), met cykelnotatie (1 2 3 4), geeft dit (1 4) (1 3) (1 2), waarbij deze drie verwisselingen van rechts naar links worden uitgevoerd. Deze samenstelling is niet uniek, een andere is bijvoorbeeld (1 2) (2 4) (2 3). Gegeven een bepaalde permutatie, dan is de pariteit van het aantal verwisselingen in de verschillende samenstellingen ervan altijd hetzelfde, dus of altijd even of altijd oneven. Een even permutatie is een samenstelling van een even aantal verwisselingen, een oneven permutatie is een samenstelling van een oneven aantal verwisselingen. (1 2 3 4) is dus een oneven permutatie.

Een eigenschap (en gelijkwaardige definitie) is dat een permutatie van $(1,2,3,\ldots ,n)$ naar de volgorde $(c_{1},c_{2},c_{3},\ldots ,c_{n})$ even of oneven is als het aantal paren $(i,j)$ met $i<j$ waarvoor in de nieuwe volgorde de $i$ op enige plaats na de $j$ komt, dus niet in de oorspronkelijke onderlinge volgorde, even of oneven is. In het voorbeeld zijn dit de paren {1,2}, {1,3}, {1,4}. Gezien de eerste definitie is de pariteit van de permutatie niet afhankelijk van een gekozen ordening/nummering van de elementen.

De identieke permutatie is even, elke verwisseling is oneven. Van iedere verzameling met minstens twee elementen is de helft van de permutaties even.

De alternerende groep op $n$ elementen, genoteerd ${\mathcal {A}}_{n}$ , is de ondergroep van ${\mathcal {S}}_{n}$ die uit de even permutaties bestaat.

Een cykel van ten minste lengte 2 is een even permutatie als de lengte oneven is, en omgekeerd.

Het teken van een permutatie is 1 als deze even is, en -1 als deze oneven is, overeenkomstig het verheffen van -1 tot een even of oneven macht. Het teken van de samenstelling van permutaties is het product van de tekens van de afzonderlijke permutaties. Ook is het zo dat het even of oneven zijn van de samenstelling van permutaties overeenkomt met het even of oneven zijn van de som van getallen die even of oneven zijn overeenkomstig de samenstellende permutaties; de samenstelling van twee oneven permutaties is bijvoorbeeld even, net zoals de som van twee oneven getallen even is.

Voorbeeld:

Van de verzameling $\{1,2,3,4\}$ zijn de even permutaties

()\,

(123),\;(132),\;(124),\;(142),\;(134),\;(143),\;(234),\;(243)

(12)(34),\;(13)(24),\;(14)(23)

en de oneven permutaties

(12),\;(13),\;(14),\;(23),\;(24),\;(34)

(1234),\;(1243),\;(1324),\;(1342),\;(1423),\;(1432)

Alternerende permutaties

Een alternerende permutatie van $(1,2,3,\ldots ,n)$ is een permutatie naar de volgorde $(c_{1},c_{2},c_{3},\ldots ,c_{n})$ zodanig dat:

$c_{1}<c_{2}$
$c_{i-1}>c_{i}<c_{i+1}$ als $i$ oneven is
$c_{i-1}<c_{i}>c_{i+1}$ als $i$ even is

In de gepermuteerde rij wordt dus het eerste getal gevolgd door een groter getal, dat dan gevolgd wordt door een kleiner getal, dat weer door een groter enzovoort. Elk getal op een oneven plaats in de rij staat tussen twee getallen die groter zijn en elk getal op een even plaats staat tussen twee getallen die kleiner zijn.

Alternerende permutaties moet men niet verwarren met de alternerende groep.

De vijf alternerende permutaties van {1, 2, 3, 4} zijn:

$(1,3,2,4)\quad$ omdat $\quad 1<3>2<4$
$(1,4,2,3)\quad$ omdat $\quad 1<4>2<3$
$(2,3,1,4)\quad$ omdat $\quad 2<3>1<4$
$(2,4,1,3)\quad$ omdat $\quad 2<4>1<3$
$(3,4,1,2)\quad$ omdat $\quad 3<4>1<2$

Men noemt deze permutaties ook up-down-permutaties. Als men eist dat het eerste getal groter moet zijn dan het tweede, spreekt men van een down-up-permutatie. Vanwege de symmetrie zijn er evenveel up-down-permutaties als down-up-permutaties van een gegeven lengte. Hun aantal wordt in deze tabel opgelijst voor permutaties tot lengte 7:

Aantal up-down-permutaties van $n$ getallen, die met het getal $k$ beginnen
${}_{n}\!\diagdown \!\!{}^{k}$	1	2	3	4	5	6	7	Totaal
2	1	0						1
3	1	1	0					2
4	2	2	1	0				5
5	5	5	4	2	0			16
6	16	16	14	10	5	0		61
7	61	61	56	46	32	16	0	272

De totalen in de laatste kolom zijn, voor oneven $n$ , de eulergetallen die voorkomen als coëfficiënten in de maclaurin-reeksontwikkeling van de tangensfunctie:

{\begin{aligned}\tan(x)&=x+{\tfrac {1}{3}}x^{3}+{\tfrac {2}{15}}x^{5}+{\tfrac {17}{315}}x^{7}+\ldots \\&=x+{\tfrac {2}{3!}}x^{3}+{\tfrac {16}{5!}}x^{5}+{\tfrac {272}{7!}}x^{7}+\ldots \end{aligned}}

Ze worden gegeven door de volgende gesloten formule:

A_{2n+1}=\sum _{j=1}^{n}\sum _{k=j}^{n}(-1)^{j+n}{\binom {2k}{k-j}}(k+1){\frac {j^{2n}}{2^{k-1}}}

De aantallen voor even $n$ zijn de eulergetallen die de coëfficienten zijn in de maclaurin-reeksontwikkeling van de secans:

\sec(x)=1+{\tfrac {1}{2!}}x^{2}+{\tfrac {5}{4!}}x^{4}+{\tfrac {61}{6!}}x^{6}+\ldots

Ze worden gegeven door deze formule:

A_{2n}=\sum _{j=1}^{n}\sum _{k=j}^{n}(-1)^{j+n}{\binom {2k}{k-j}}{\frac {j^{2n}}{2^{k-1}}}

Dit geeft samen de volgende rij voor het aantal down-up- of up-down-permutaties van de eerste $n=1,2,3,\ldots$ gehele getallen:

1,1,2,5,16,61,272,1385,7936,\ldots

^[2]

Dit is tevens de eerste kolom in de bovenstaande tabel: het aantal alternerende up-down-permutaties van $n$ getallen is gelijk aan het aantal alternerende up-down-permutaties van $n+1$ getallen die beginnen met 1 (of het aantal down-up-permutaties van $n+2$ getallen die beginnen met 2).

Deze permutaties zijn in de 19e eeuw door de Franse wiskundige Désiré André bestudeerd.^[3]^[4]

Superpermutatie

Een superpermutatie van $n$ tekens is een tekenreeks die alle permutaties (in de hierboven eerstgenoemde notatie, maar dan zonder haakjes en komma's) als substring bevat ( $n$ opeenvolgende tekens in de reeks).^[5]

Voor $1\leq n\leq 5$ hebben de kortste van deze reeksen een lengte $1!+2!+\ldots +n!$ , dus 1, 3, 9, 33 en 153:

1
121
123121321
123412314231243121342132413214321
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

In de eerste vier gevallen is de kortste reeks, afgezien van omnummering, uniek, en een palindroom. Bij 5 tekens zijn er afgezien van omnummering 8 kortste reeksen.

Voor algemene $n\geq 2$ is de kortste lengte minstens $n!+(n-1)!+(n-2)!+n-3$ en hoogstens $n!+(n-1)!+(n-2)!+(n-3)!+n-3$ . Bijvoorbeeld voor $n=6$ is de kortste lengte dus minstens 870 en hoogstens 873. Er is echter een reeks gevonden van lengte 872, de kortste lengte is dus hoogstens dat aantal.