Kombinatorik
XYZKVANOG
Räkna antalet möjliga sätt – allt hänger på om ordningen spelar roll eller inte.
Formler
antal sätt = n1 × n2 × … × nk
Multiplikationsprincipen. Görs flera val efter varandra multiplicerar man antalet möjligheter i varje steg. Tre förrätter och fyra huvudrätter ger 3 × 4 = 12 menyer.
n! = n × (n-1) × (n-2) × … × 1
Fakultet, antalet sätt att ordna n olika föremål i rad. 4! = 4 × 3 × 2 × 1 = 24.
ordnat urval av k ur n = n × (n-1) × … × (n-k+1)
En faktor för varje plats, där den valda saken tas bort ur högen inför nästa. Guld, silver och brons bland 8 löpare: 8 × 7 × 6 = 336 sätt.
oordnat urval av k ur n = ordnat urval ÷ k!
Spelar ordningen ingen roll har varje uppsättning räknats en gång för varje inbördes ordning, alltså k! gånger. Tre av 8 löpare till ett lag: 336 ÷ 6 = 56 sätt.
Så fungerar det
Kombinatorik är konsten att räkna antalet möjligheter utan att skriva upp dem. Grunden är multiplikationsprincipen: sker valet i flera steg multiplicerar du antalet möjligheter i varje steg. Fyra tröjor och tre byxor ger 4 × 3 = 12 kombinationer, och det gäller oavsett hur många steg det är.
Innan du räknar måste du besvara två frågor om uppgiften. Får samma sak väljas igen? En pinkod får ha samma siffra flera gånger, men samma person kan inte få både guld och silver. Spelar ordningen roll? Guld och silver är olika saker, men två personer i samma kommitté är samma kommitté oavsett i vilken ordning de valdes.
Svaren ger tre fall som täcker i stort sett allt på provet:
- Upprepning tillåten, ordningen spelar roll: n × n × … med k faktorer. En fyrsiffrig kod ger 104 = 10 000 möjligheter.
- Ingen upprepning, ordningen spelar roll: n × (n-1) × … med k faktorer. Antalet faktorer är antalet platser, inte n.
- Ingen upprepning, ordningen spelar ingen roll: samma produkt dividerad med k!.
Divisionen med k! är hela poängen och det som glöms bort. Väljer du tre personer av sju i en bestämd ordning har varje trio räknats 3! = 6 gånger, en gång för varje ordning de kan stå i. Delar du bort de sex får du antalet trior. En snabb rimlighetskontroll: det oordnade antalet är alltid mindre än det ordnade.
Räknade exempel
Exempel 1 En kod består av två bokstäver följda av tre siffror. Bokstäverna väljs bland A, B, C och D, siffrorna bland 0 till 9, och både bokstäver och siffror får upprepas. Hur många koder finns det?
Lösning. Koden byggs i fem steg, så multiplikationsprincipen gäller. Första bokstaven kan väljas på 4 sätt och andra bokstaven också på 4, eftersom upprepning är tillåten. Var och en av de tre siffrorna kan väljas på 10 sätt. Totalt blir det 4 × 4 × 10 × 10 × 10 = 16 × 1 000 = 16 000 koder. Hade bokstäverna inte fått upprepas hade den andra bara kunnat väljas på 3 sätt och antalet blivit 4 × 3 × 1 000 = 12 000. Det är därför meningen om upprepning måste läsas innan man börjar räkna.
Exempel 2 En förening med 7 medlemmar ska utse en styrelse på 3 personer. Hur många styrelser är möjliga om (a) de tre har samma roll, respektive (b) de tre ska bli ordförande, kassör och sekreterare?
Lösning. Börja med (b), där ordningen spelar roll eftersom rollerna är olika. Ordförandeposten kan besättas på 7 sätt, kassörsposten på 6 av de kvarvarande och sekreterarposten på 5. Det ger 7 × 6 × 5 = 210 möjliga styrelser. I (a) har rollerna ingen betydelse, så samma tre personer har räknats en gång för varje inbördes ordning, alltså 3! = 3 × 2 × 1 = 6 gånger. Antalet blir därför 210 ÷ 6 = 35. Svaret på (a) är alltid mindre än svaret på (b), och att glömma divisionen med 3! och svara 210 på båda frågorna är det vanligaste felet i kombinatorik.
Vanliga fällor
- Att glömma dividera med k! när ordningen inte spelar roll. Ett handslag mellan A och B är samma handslag som mellan B och A.
- Att inte kontrollera om upprepning är tillåten. Skillnaden mellan 4 × 4 och 4 × 3 avgörs av en enda mening i uppgiften.
- Att addera i stället för att multiplicera i flerstegsval. Tre förrätter och fyra huvudrätter ger 12 menyer, inte 7.
- Att multiplicera hela vägen ner till 1 vid ett ordnat urval. Väljs 3 av 8 ska det bli tre faktorer, 8 × 7 × 6, inte 8!.
Läs mer
Andra begrepp i statistik och sannolikhet:
Läs mer
- Högskoleprovet
- Gamla högskoleprov
- Normering av högskoleprovet
- Vanliga frågor om högskoleprovet
- Formelblad för högskoleprovet