Sådan beregnes kombinationer og permutationer

Antag at du har n typer elementer, og du ønsker at vælge en samling af r af dem. Vi vil måske have disse varer i en bestemt rækkefølge. Vi kalder disse sæt af varer permutationer. Hvis ordren ikke betyder noget, kalder vi sæt samlingskombinationer. For både kombinationer og permutationer kan du overveje det tilfælde, hvor du vælger nogle af n typerne mere end én gang, som kaldes 'med gentagelse', eller det tilfælde, hvor du kun vælger hver type én gang, som kaldes 'ingen gentagelse '. Målet er at kunne tælle antallet af kombinationer eller permutationer, der er mulige i en given situation.

Ordninger og Factorials

Faktorfunktionen bruges ofte til beregning af kombinationer og permutationer. N! betyder N × (N-1) × ... × 2 × 1. For eksempel 5! = 5 × 4 × 3 × 2 × 1 = 120. Antallet af måder at bestille et sæt af elementer på er et faktorialt. Tag de tre bogstaver a, b og c. Du har tre valg til første bogstav, to til den anden og kun en til den tredje. Med andre ord, i alt 3 × 2 × 1 = 6 ordrer. Generelt er der n! måder at bestille n ting på.

Permutationer med gentagelse

Antag at du har tre værelser, du skal male, og hver enkelt vil blive malet en af ​​fem farver: rødt (r), grønt g), blå (b), gul (y) eller orange (o). Du kan vælge hver farve så mange gange som du vil. Du har fem farver at vælge imellem til det første værelse, fem til det andet og fem til det tredje. Dette giver i alt 5 × 5 × 5 = 125 muligheder. Generelt er antallet af måder at vælge en gruppe af r emner i en bestemt rækkefølge fra n gentagelige valg på, n ^ r.

Permuteringer uden gentagelse

Antag nu, at hvert rum skal være en anden farve. Du kan vælge mellem fem farver til det første værelse, fire til det andet og kun tre til det tredje. Dette giver 5 × 4 × 3 = 60, som bare tilfældigvis er 5! /2 !. Generelt er antallet af uafhængige måder at vælge r-poster i en bestemt rækkefølge fra n ikke-repeterbare valg n! /(N-r)!

Kombinationer uden gentagelse

Dernæst glem hvilket rum er hvilken farve Vælg bare tre uafhængige farver til farveskemaet. Ordren betyder ikke noget her, så (rød, grøn, blå) er den samme som (rød, blå, grøn). For enhver valg af tre farver er der 3! måder du kan bestille dem på. Så du reducerer antallet af permutationer med 3! for at få 5! /(2! × 3!) = 10. Generelt kan du vælge en gruppe af r-poster i en hvilken som helst rækkefølge fra et udvalg af n ikke-reflekterbare valg i n! /[(n-r)! × r! ] måder.

Kombinationer med gentagelse

Endelig skal du oprette et farveskema, hvor du kan bruge enhver farve så mange gange som du vil. En smart bogholderikode hjælper denne tælleropgave. Brug tre X'er til at repræsentere værelserne. Din liste over farver er repræsenteret af 'rgbyo'. Bland X'erne i din farveliste, og associer hver X med den første farve til venstre for den. For eksempel betyder rgXXbyXo at det første rum er grønt, det andet er grønt og det tredje er gul. En X skal have mindst en farve til venstre, så der er fem ledige pladser til den første X. Fordi listen nu indeholder en X, er der seks tilgængelige slots for den anden X og syv ledige pladser til den tredje X. I Alt er der 5 × 6 × 7 = 7! /4! måder at skrive koden på. Imidlertid er rækkefølgen af ​​værelserne vilkårlig, så der er virkelig kun 7! /(4! × 3!) Unikke arrangementer. Generelt kan du vælge r poster i en hvilken som helst rækkefølge fra n gentagelige valg i (n + r-1)! /[(N-1)! × r!] Måder.