permutatie

Een permutatie is een specifieke volgorde waarin de elementen van een verzameling zijn gerangschikt. Als de verzameling uit n verschillende elementen bestaat, dan is elke voorgestelde volgorde een permutatie. De verzameling van alle permutaties van een set met n elementen vormt de symmetrische groep S_n.

Het aantal permutaties van n verschillende elementen is n! (n faculteit). Permutaties houden rekening met de volgorde; bij combinaties telt daarentegen alleen de selectie, zonder rekening te houden met de volgorde.

Varianten: bij volledige permutaties zonder herhaling selecteer en ordeneer je k elementen uit n, waarbij het aantal geordende keuzes nPk = n!/(n−k)!. Als herhaling is toegestaan, zijn er n^k mogelijke geordende keuzes van lengte k.

Permutaties van een multiset ontstaan wanneer sommige elementen identiek zijn. Het aantal verschillende permutaties is dan n!/(m1! m2! ... mr!), waarbij mi het aantal keren dat het i-de type element voorkomt.

Voorbeelden: met de letters A, B, C zijn er 3! = 6 permutaties. Voor een woord als AAB is het aantal verschillende permutaties 3!/(2!1!) = 3, namelijk AAB, ABA en BAA.

Toepassingen: permutaties komen van pas in kansrekening, statistiek, combinatoriek en informatica bij het bepalen van mogelijke ordeningen van elementen en bij puzzels zoals anagrammen en rijtjes. In abstracte termen vormen alle permutaties van een n-elementenverzameling de symmetrische groep S_n, die de structuur van de permutaties beschrijft.

Samenvatting: een permutatie is een specifieke volgorde van elementen; het aantal permutaties hangt af van het aantal elementen en van of herhaling is toegestaan.