Sådan beregnes kombinationer og permutationer

Antag at du har n typer varer, 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 emner 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 en gang, som kaldes 'med gentagelse', eller det tilfælde, hvor du kun vælger hver type en gang, som kaldes 'nej gentagelse'. Målet er at være i stand til at tælle antallet af kombinationer eller permutationer, der er mulige i en given situation.

Faktorafunktionen 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 emner er et faktum. Tag de tre bogstaver a, b og c. Du har tre valg for det første bogstav, to for det andet og kun et for det tredje. Med andre ord, i alt 3 × 2 × 1 = 6 ordrer. Generelt er der n! måder at bestille n varer på.

Antag, at du har tre rum, du skal male, og hver af dem males i en af ​​fem farver: rød (r), grøn (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 i en bestemt rækkefølge på n gentagelige valg n ^ r.

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

Glem derefter, hvilket rum der 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 ethvert 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-gentagelige valg på n! / [(N – r)! × r!] Måder.

Endelig skal du oprette et farveskema, hvor du kan bruge en hvilken som helst farve så mange gange som du vil. En smart bogføringskode hjælper denne tælleopgave. 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 knyt hver X til 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 gult. Et X skal have mindst en farve til venstre, så der er fem ledige pladser til den første X. Da listen nu indeholder en X, er der seks ledige pladser til 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å. Dog 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 på (n + r – 1)! / [(N – 1)! × r!] Måder.