Permutatie

Er zijn zes mogelijke permutaties van drie voorwerpen

Voorbeeld van een cyclische permutatie

Een permutatie is een wiskundig object dat een welbepaalde rangschikking weergeeft van een aantal voorwerpen of getallen.

Formele definitie

Een permutatie is een bijectie tussen een verzameling en zichzelf.

Voorbeelden

De identieke permutatie is de oorspronkelijke rangschikking, of ook nog, de bi-jectie die ieder element op zichzelf afbeeldt.

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

Eenvoudig voorbeeld met 4 knikkers; een rode, gele, groene en blauwe. Er zijn verschillende volgordes mogelijk, bijvoorbeeld "rood, geel, groen, blauw" of "rood, groen, geel, blauw". Er zijn in dit geval 4! = 1 x 2 x 3 x 4 = 24 mogelijkheden.

Gebruik

Een permutatie wordt onder andere toegepast in de telecommunicatie om informatie te spreiden over tijd en/of frequentie zodat foutcorrectiecodes, die slecht kunnen omgaan met opeenvolgende fouten, beter werken. Zo'n permutatie wordt gespecificeerd door een permutatieformule. Verder zijn permutaties belangrijk in kansrekening, statistiek en combinatoriek.

Aantal mogelijke permutaties

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

$n! = n(n-1)!\!$

en

$0! = 1\!$

kan n! berekend worden voor willekeurige n.

Soms wordt ook een variatie als permutatie aangeduid.

Permutatiegroep

Zie Permutatiegroep voor het hoofdartikel over dit onderwerp.

Twee permutaties $\pi_1$ en $\pi_2$ op een verzameling $A$ kunnen worden samengesteld. De samengestelde relatie $\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.h$

Even en oneven permutaties

Elke permutatie van een eindige verzameling kan geschreven worden als een samenstelling van een eindig aantal verwisselingen. Deze schrijfwijze is niet uniek, maar de pariteit van het aantal verwisselingen is wel onveranderlijk. Een even permutatie is een samenstelling van een even aantal verwisselingen, een oneven permutatie is een samenstelling van een oneven aantal verwisselingen. De identieke permutatie is even, elke verwisseling is oneven.

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

Zie ook

• combinatie (wiskunde)