Kombinatorikk gjør det mulig å telle utfall uten å skrive opp alle sammen. Metoden avhenger av hva som skiller to utfall: rekkefølgen, elementene som er valgt, eller begge deler. Du må også vite om samme element kan velges flere ganger.
Multiplikasjonsprinsippet
En butikk selger tre skomodeller, hver i to farger. Å velge modell og farge gir 3 × 2 = 6 muligheter. Multipliser antall valg i hvert trinn. Dersom et valg begrenser senere trinn, bruker du antall alternativer som faktisk gjenstår.
Hva betyr fakultet?
Fakultetet til et positivt heltall er produktet av tallet og alle mindre positive heltall. Null fakultet er definert som én. Det passer med den ene måten å ordne et tomt utvalg på.
Å ordne alle elementene
For n ulike elementer på n plasser finnes først n valg, så n − 1 og så videre. Tre kandidater kan få tre sluttplasseringer i seks rekkefølger dersom ingen deler en plassering.
Identiske elementer gir ingen ny ordning når de byttes. Derfor deler du på fakultetet til antallet i hver gjentatt gruppe. ANNA har fire bokstaver, to A-er og to N-er, og dermed seks forskjellige bokstavordninger.
Ordnede utvalg: rekkefølgen teller
Å lage tresifrede tall uten gjentakelse fra {1, 2, 3, 5, 7, 9} er et ordnet utvalg. Siden 123 og 321 er forskjellige, blir antallet 6 × 5 × 4 = 120.
Med gjentakelse har hver plass igjen alle n alternativer. To plasser fylt med de fem bokstavene A, E, I, O og U gir 25 følger, blant annet AA og AE.
Kombinasjoner: bare gruppen teller
Å velge tre ulike kuler blant tolv gir 220 grupper. Her velges én gruppe på tre, ikke en fordeling av alle tolv kulene på flere beholdere. Ulike rekkefølger innen samme gruppe telles bare én gang.
Hvorfor tre kuler blant tolv gir 220 grupper
Tolv kuler er forskjellige, og vi velger tre uten tilbakelegging. En annen rekkefølge av de samme tre lager ingen ny gruppe. Derfor brukes en kombinasjon med n = 12 og k = 3.
Sett antallene inn i formelen. Siden 12 − 3 = 9, er det andre fakultetet i nevneren 9 fakultet.
Forkort bort det felles fakultetet av 9. De tre gjenværende faktorene i telleren teller ordnede utvalg; nevneren fjerner gruppens seks rekkefølger.
Beregn produktene og del. Hver uordnet gruppe telles nå nøyaktig én gang.
Det finnes 220 utvalg. Multiplisert med de seks interne rekkefølgene gir det 1 320 ordnede utvalg og kontrollerer den opprinnelige opptellingen.
Utvalg med gjentakelse
Velges tre par sko blant ti merker, kan merker gjentas og rekkefølgen ignoreres, finnes det 220 merkeutvalg. Dette forutsetter tilstrekkelig tilgjengelighet og at bare merket skiller alternativene.
Her er n antall tilgjengelige elementer eller typer og k antall valgte elementer. Uten gjentakelse kan k ikke overstige n. Sammenlign AB og BA: Er de samme utfall? Undersøk deretter separat om AA er tillatt. De to svarene bestemmer tellemodellen.
