Multiplikationsprincipen

I det här kapitlet kommer vi att lära oss om kombinatorikens grunder genom att vi studerar multiplikationsprincipen, permutationer och kombinationer.

I detta inledande avsnitt bekantar vi oss med multiplikationsprincipen och hur vi med hjälp av den kan beräkna antalet sätt som vi kan välja ett element var ur två eller flera mängder.

Multiplikationsprincipen

I kapitlet om mängdlära bekantade vi oss med begreppet mängd.

Om vi har två mängder A och B, och vill veta på hur många olika sätt som vi kan välja ett element från mängd A och ett element från mängd B, då har vi användning för multiplikationsprincipen.

Multiplikationsprincipen säger oss att om det finns x sätt att göra ett första val och y sätt att göra ett andra val, då finns det xy möjliga sätt att sammantaget göra dessa båda val på.

Om vi ser det första valet som att vi ska välja ett element ur en mängd A och det andra valet som att vi ska välja ett element ur en mängd B, då kommer vi att kunna välja ett element ur mängden A på |A| olika sätt och ett element ur mängden B på |B| olika sätt (där |A| och |B| betecknar kardinaliteten för mängden A respektive B, det vill säga antalet element i respektive mängd). Enligt multiplikationsprincipen kommer vi alltså att kunna välja ett element ur A och ett element ur B på |A|∙|B| sätt.

Om vi till exempel ska välja ett element ur A = {a, b, c} och ett element ur B = {1, 2, 3, 4} kan detta göras på följande sätt:

$$\begin{matrix}(a,\,1), & (a,\,2), & (a,\,3), & (a,\,4), \\(b,\,1), & (b,\,2), & (b,\,3), & (b,\,4), \\(c,\,1), & (c,\,2), & (c,\,3), & (c,\,4)\end{matrix}$$

där t.ex. (c, 3) innebär att vi väljer elementet c ur mängden A och elementet 3 ur mängden B.

Genom denna uppräkning ovan ser vi att antalet olika sätt är 12, men vi kunde även ha beräknat detta direkt med hjälp av de båda mängdernas kardinalitet:

$$|A|\cdot |B|=3\cdot 4=12$$

Vi kan illustrera denna situation med hjälp av ett träddiagram, där vi först väljer ett element ur A och sedan ett element ur B, på följande sätt:

Kombinatorik

I detta exempel var det två val som skulle göras (ett element skulle väljas ur respektive mängd), men multiplikationsprincipen utvidgas enkelt till fler än två val. Ska vi till exempel välja ett element ur var och en av mängderna A, B och C, kan det första valet göras på |A| sätt, det andra på |B| sätt, och det tredje på |C| sätt, vilket ger oss att ett element ur A, B respektive C kan väljas på |A|∙|B|∙|C| olika sätt.

Vi inser också att när vi bara är intresserade av att beräkna antalet sätt som vi kan göra dessa val på, då spelar det ingen roll i vilken ordning vi gör valen, eftersom t.ex. |A|∙|B| = |B|∙|A| gäller.


Anton har två par byxor, fyra skjortor och tre slipsar. På hur många olika sätt kan han välja ett par byxor, en skjorta och en slips?

Det här problemet kan vi lösa med hjälp av multiplikationsprincipen.

Vi betecknar mängden av byxor med A, mängden av skjortor med B och mängden av slipsar med C. Vi vet att mängden A har två element, mängden B har fyra element och mängden C har tre element. Kardinaliteten för respektive mängd är alltså |A| = 2, |B| = 4 respektive |C| = 3.

Antalet sätt som vi sammantaget kan göra dessa tre val beräknar vi med multiplikationsprincipen på följande sätt:

$$|A|\cdot |B|\cdot |C|=2\cdot 4\cdot 3=24$$

Det finns alltså i det här fallet 24 olika sätt som Anton kan välja ett par byxor, en skjorta och en slips.


Produktkoder

Ett företag bestämmer sig för att införa ett system där varje produkt ges en kod, så att man lätt kan identifiera varje produkt enbart utifrån denna kod. På företaget tänker man sig att produktkoderna ska bestå av två bokstäver följt av fem siffror, men man vet inte till hur många produkter dessa koder kommer att räcka.

Hur många produkter kan unikt identifieras med hjälp av detta system? Vi antar att de bokstäver som får användas är alla bokstäver i det svenska alfabetet förutom å, ä och ö, och att de siffror som får användas är 0 till 9.

Lösningsförslag:

Enligt det sätt som koderna är uppbyggda ska vi först välja en bokstav, sedan ytterligare en bokstav, och slutligen göra fem val av siffror 0 till 9.

Vi kan se det som att vi har två mängder A och B, där elementen i  A utgörs av de tillåtna bokstäverna och elementen i B utgörs av de tillåtna siffrorna. Vad vi ska göra är alltså först två val av element ur mängden A och sedan fem val av element ur mängden B.

Antalet bokstäver i det svenska alfabetet förutom å, ä och ö är 26 stycken. Alltså finns det 26 element i mängden A, det vill säga |A| = 26.

Siffrorna 0 till 9 är 10 stycken siffror, så detta är antalet element i mängden B, det vill säga |B| = 10.

Bokstäverna kan därför väljas på 262 olika sätt, eftersom det är två val ur en mängd som innehåller 26 element som ska göras.

Var och en av de fem siffrorna i koden kan väljas på 10 olika sätt, eftersom siffrorna 0 till 9 används. Det innebär att det finns 105 olika sätt att välja de fem siffrorna på.

Sammanlagt är det alltså sju val (två bokstäver och fem siffror) som ska göras oberoende av varandra, så multiplikationsprincipen säger oss att vi kan göras dessa val på så här många olika sätt:

$${|A|}^{2}\cdot {|B|}^{5}={26}^{2}\cdot {10}^{5}=676\cdot 100\,000=67\,600\,000$$

Detta innebär alltså att systemet kan skapa 67,6 miljoner produktkoder. Om företaget räknar med att inte ha fler produkter än så kommer antalet produktkoder att räcka för företagets behov. 


Videolektion

Har du en fråga du vill ställa om Multiplikationsprincipen? Ställ den i Mattebokens forum!
Har du kommentarer till materialet på den här sidan? Mejla feedback@matteboken.se!