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
Een permutatie van een verzameling is een bijectie van die verzameling op zichzelf.

Opmerkingen
Als  een bijectie is van een verzameling  op een verzameling , dan is  een een-op-eencorrespondentie tussen de permutaties  van  en de bijecties  van  op .

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
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
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
Het aantal mogelijke permutaties van  verschillende elementen wordt genoteerd als  (lees: n faculteit).
Met behulp van de recursierelatie

en

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

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

Twee permutaties  en  op een verzameling  kunnen worden samengesteld. De samenstelling  is opnieuw een permutatie, en wel op een zodanige manier dat de bewerking "" van de collectie  van alle permutaties van  een groep maakt. In het bijzonder noteert men  voor de groep van alle permutaties van de verzameling . Als  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  is isomorf met een permutatiegroep op de verzameling . Associeer daartoe het groepselement  met de permutatie  die ieder element  afbeeldt op het groepselement

Even en oneven permutaties
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  naar de volgorde  even resp. oneven is als het aantal paren  met  waarvoor in de nieuwe volgorde de  op enige plaats na de  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  elementen, genoteerd , is de deelgroep van  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  zijn de even permutaties

en de oneven permutaties

Alternerende permutaties
Een alternerende permutatie van  is een permutatie naar de volgorde  zodanig dat:
 
  als  oneven is
  als  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:
  omdat 
  omdat 
  omdat 
  omdat 
  omdat 

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:

{| class="wikitable float-right" style="text-align:right"
|+ Aantal up-down-permutaties van  getallen, die met het getal  beginnen
|- class="hintergrundfarbe8"
| style="width:2em" | 
| style="width:1.5em" | 1
| style="width:1.5em" | 2
| style="width:1.5em" | 3
| style="width:1.5em" | 4
| style="width:1.5em" | 5
| style="width:1.5em" | 6
| style="width:1.5em" | 7
| style="width:2em" | 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 , de Eulergetallen die voorkomen als coëfficiënten in de Maclaurin-reeksontwikkeling van de tangensfunctie:

Ze worden gegeven door de volgende gesloten formule:

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

Ze worden gegeven door deze formule:

Dit geeft samen de volgende rij voor het aantal down-up- of up-down-permutaties van de eerste  gehele getallen:

  

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

Deze permutaties werden in de negentiende eeuw bestudeerd door de Franse wiskundige Désiré André.

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

Voor  hebben de kortste van deze reeksen een lengte , 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  is de kortste lengte minstens  en hoogstens . Bijvoorbeeld voor  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
 Combinatie (wiskunde)
 Derangement

Combinatoriek
Relaties op verzamelingen
Groepentheorie
Discrete wiskunde