Hvordan beregne kombinasjoner og permutasjoner

Anta at du har n typer ting, og at du ønsker å velge en samling av r av dem. Vi vil kanskje ha disse varene i en bestemt rekkefølge. Vi kaller disse artiklene for permutasjoner. Hvis ordren ikke betyr noe, kaller vi settet med samlingskombinasjoner. For både kombinasjoner og permutasjoner kan du vurdere tilfellet der du velger noen av n-typene mer enn en gang, som kalles "med repetisjon", eller tilfellet der du velger hver type bare en gang, som kalles "nei gjentakelse'. Målet er å kunne telle antall kombinasjoner eller permutasjoner som er mulige i en gitt situasjon.

Faktorafunksjonen brukes ofte når man beregner kombinasjoner og permutasjoner. N! betyr N × (N – 1) ×... × 2 × 1. For eksempel 5! = 5×4×3×2×1 = 120. Antallet måter å bestille et sett på er et faktum. Ta de tre bokstavene a, b og c. Du har tre valg for den første bokstaven, to for den andre og bare en for den tredje. Med andre ord totalt 3 × 2 × 1 = 6 bestillinger. Generelt er det n! måter å bestille n varer.

Anta at du har tre rom du skal male, og hvert av dem vil bli malt en av fem farger: rød (r), grønn (g), blå (b), gul (y) eller oransje (o). Du kan velge hver farge så mange ganger du vil. Du har fem farger å velge mellom for det første rommet, fem for det andre og fem for det tredje. Dette gir totalt 5 × 5 × 5 = 125 muligheter. Generelt er antall måter å velge en gruppe r-elementer i en bestemt rekkefølge fra n repeterbare valg, n ^ r.

Anta at hvert rom kommer til å ha en annen farge. Du kan velge mellom fem farger for det første rommet, fire for det andre og bare tre for det tredje. Dette gir 5 × 4 × 3 = 60, som tilfeldigvis er 5! / 2!. Generelt er antallet uavhengige måter å velge r elementer i en bestemt rekkefølge fra n ikke-gjentatte valg n! / (N – r) !.

Deretter glemmer du hvilket rom som er hvilken farge. Bare velg tre uavhengige farger for fargevalget. Rekkefølgen spiller ingen rolle her, så (rød, grønn, blå) er den samme som (rød, blå, grønn). For alle valg av tre farger er det 3! måter du kan bestille dem på. Så du reduserer antall permutasjoner med 3! for å få 5! / (2! × 3!) = 10. Generelt kan du velge en gruppe r-elementer i hvilken som helst rekkefølge fra et utvalg av n ikke-repeterbare valg på n! / [(N – r)! × r!] Måter.

Til slutt må du lage et fargevalg der du kan bruke hvilken som helst farge så mange ganger du vil. En smart bokføringskode hjelper denne telleoppgaven. Bruk tre Xer til å representere rommene. Din fargeliste er representert med 'rgbyo'. Bland X-ene i fargelisten din, og knytt hver X til den første fargen til venstre for den. For eksempel betyr rgXXbyXo at det første rommet er grønt, det andre er grønt og det tredje er gult. En X må ha minst en farge til venstre, så det er fem ledige plasser for den første Xen. Fordi listen nå inneholder en X, er det seks tilgjengelige spor for den andre X og syv tilgjengelige spor for den tredje X. I alt er det 5 × 6 × 7 = 7! / 4! måter å skrive koden på. Imidlertid er rekkefølgen på rommene vilkårlig, så det er egentlig bare 7! / (4! × 3!) Unike ordninger. Generelt kan du velge r-elementer i hvilken som helst rekkefølge fra n gjentakbare valg på (n + r – 1)! / [(N – 1)! × r!] Måter.