Permutatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Er zijn zes mogelijke permutaties van drie voorwerpen
Voorbeeld van permutatie die is samengesteld uit cyclische permutaties van disjuncte delen

Een permutatie is een rangschikking van een aantal voorwerpen of getallen, dat wil zeggen een manier om de voorwerpen of getallen in volgorde te plaatsen. Men kan 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. Uitgaande van een bepaalde beginvolgorde vat men een permutatie ook wel op als een herschikking van de voorwerpen of getallen.

Formele definitie[bewerken]

Een permutatie is een bijectie tussen een verzameling en zichzelf.

Voorbeelden[bewerken]

De identieke permutatie correspondeert met het niet veranderen van de volgorde; wiskundig: de bijectie die ieder element op zichzelf afbeeldt.

Een (paar)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.

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]

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.

Gebruik[bewerken]

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[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\!

Soms wordt ook een variatie als permutatie aangeduid.

Permutatiegroep[bewerken]

Nuvola single chevron right.svg 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.h

Even en oneven permutaties[bewerken]

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.

Alternerende permutaties[bewerken]

Een alternerende permutatie van {1, 2, 3, ..., n} is een permutatie naar de volgorde {c1, ..., cn} zodanig dat:

  • c1< c2
  • ci-1 > ci < ci+1 als i oneven is
  • ci-1 < ci > ci+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       omdat       1 < 3 > 2 < 4
  • 1, 4, 2, 3       omdat       1 < 4 > 2 < 3
  • 2, 3, 1, 4       omdat       2 < 3 > 1 < 4
  • 2, 4, 1, 3       omdat       2 < 4 > 1 < 3
  • 3, 4, 1, 2       omdat       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{align}
  \tan(x) &= x+\tfrac13 x^3+\tfrac{2}{15}x^5+\tfrac{17}{315}x^7+\dotsb\\
         &= x + \tfrac{2}{3!} x^3 + \tfrac {16}{5!} x^5 + \tfrac{272}{7!} x^7 + \dotsb .
\end{align}

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 + \cdots

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 gehele getallen, n=1,2,3,...:

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]

Zie ook[bewerken]

Bronnen, noten en/of referenties