Permutatie

Een permutatie van een eindige verzameling (van bijvoorbeeld voorwerpen of getallen) is een herschikking ervan, dat wil zeggen het uitvoeren van nul of meer verwisselingen. Uitgaande van een bepaalde beginvolgorde kan men een permutatie verkrijgen door te kiezen welke men als eerste neemt, vervolgens welke van de overige men als tweede neemt, enzovoort tot alle gekozen zijn. Als er een standaardvolgorde is zoals bij de verzameling {1, 2, 3, 4} neemt men deze wel impliciet als beginvolgorde, waardoor de permutaties corresponderen met de mogelijke volgordes.

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

Het begrip kan ook worden gedefinieerd voor een oneindige verzameling.

Definitie[bewerken | brontekst bewerken]

Een permutatie van een verzameling is een bijectie van die verzameling op zichzelf.

Opmerkingen[bewerken | brontekst bewerken]

Als $b_{0}:X\to Y$ een bijectie is van een verzameling $X$ op een verzameling $Y$ , dan is $b=b_{0}\circ p$ een een-op-eencorrespondentie tussen de permutaties $p$ van $X$ en de bijecties $b$ van $X$ op $Y$ .

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.

Voorbeeld met 4 knikkers, een rode, gele, groene en blauwe: uitgaande van een bepaalde volgorde (bijvoorbeeld de genoemde) leveren de 4! = 4 x 3 x 2 x 1 = 24 permutaties alle 24 volgordes op, bijvoorbeeld "rood, geel, groen, blauw" en "rood, groen, geel, blauw".

Speciale permutaties[bewerken | brontekst bewerken]

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

Een (paar)verwisseling (transpositie) is een permutatie die slechts van de identieke permutatie afwijkt in twee elementen (die elkaars plaats innemen).

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

Notatie[bewerken | brontekst bewerken]

Uitgaande van de standaardvolgorde (1, 2, 3, 4, 5) kan het laatste voorbeeld kortweg genoteerd worden als (3, 4, 5, 1, 2). Een andere mogelijkheid is de cykelnotatie, in dit geval (1 3 5 2 4), zonder komma's.

Aantal mogelijke permutaties[bewerken | brontekst bewerken]

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!$ berekend worden voor een willekeurig aantal elementen $n$ . 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 formeel één afbeelding is van de lege verzameling naar zichzelf, en dat deze een bijectie is.

Soms wordt ook een variatie als permutatie aangeduid.

Permutatiegroep[bewerken | brontekst bewerken]

Zie Permutatiegroep voor het hoofdartikel over dit onderwerp.

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\}$ . Als $A$ minstens drie elementen bevat, is deze groep niet abels.

Een permutatiegroep is een deelgroep 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$

Even en oneven permutaties[bewerken | brontekst bewerken]

Elke permutatie van een eindige verzameling kan geschreven worden als een samenstelling 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). De pariteit van het aantal verwisselingen is echter wel onveranderlijk. 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. Het even of oneven zijn van een permutatie wordt de pariteit van de permutatie genoemd.

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 resp. 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 resp. 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 deelgroep van ${\mathcal {S}}_{n}$ die bestaat uit de even permutaties.

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[bewerken | brontekst bewerken]

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 secansfunctie:

\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

^[1]

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 werden in de negentiende eeuw bestudeerd door de Franse wiskundige Désiré André.^[2]^[3]

Superpermutatie[bewerken | brontekst bewerken]

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).^[4]

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.

Zie ook[bewerken | brontekst bewerken]

Bronnen, noten en/of referenties

[1] rij A000111 in OEIS

[2] André, D. "Développements de sec x et tan x." Comptes Rendus de l'Académie des Sciences (1879), vol. 88, blz. 965-967.

[3] André, D. "Mémoire sur les permutations alternées." Journal de mathématiques pures et appliquées, 3e série (1881), vol. 7, blz. 167-184.

[4] rij A180632 in OEIS

[1]

[2]

[3]

[4]