For hver av de syv blyantene, kan vi velge å gi dem til tre ulike personer. Altså har vi syv valg med tre muligheter for hvert valg, og svaret blir $3^7 = 2187$.
Kapitteltest – Kapittel 19
Test deg selv
Vi ønsker å fordele syv fargeblyanter mellom tre personer, hvor alle har forskjellig farge. På hvor mange måter kan man fordele blyantene mellom de tre personene? Vi er her kun opptatt av hvilke blyanter de ulike personene får.
Test deg selv
Vi ønsker å fordele syv identiske blyanter mellom tre ulike personer. På hvor mange måter kan man fordele de syv blyantene? Vi er her kun opptatt av hvor mange blyanter hver person får.
Dette er et uordnet utvalg med repetisjon, og dermed kan man bruke formelen $\binom{3+7-1}{2} = \binom{9}{2} = 36$. Alternativt kan man bruke «stars and bars»-tankegangen (se s. 219 i boka), og da blir dette problemet det samme som hvor mange strenger man kan lage med to skillevegger og syv stjerner. Det kan ses på som å velge to plasser av ni mulige hvor man skal plassere de to veggene, og resten av plassene går til stjernene. Da får vi $\binom{9}{2} = 36$.
Test deg selv
Hvor mange strenger over $\set{a,b}$ av lengde ni finnes det som enten slutter på $\str{b}$ eller begynner med $\str{aa}$?
Det finnes $2^8$ strenger som slutter på $\str{b}$ og $2^7$ strenger som begynner med $\str{aa}$. Vi må trekke fra de strengene som er talt to ganger, nemlig de som både begynner med $\str{aa}$ og slutter på $\str{b}$. Det finnes $2^6$ slike strenger. Totalt får vi da $2^8 + 2^7 - 2^6 = 320$.
Test deg selv
La $M$ være mengden $\set{1,2,3,4,5,6}$.
Hvor mange delmengder av $M$ finnes det som har partall antall elementer?
Hvor mange delmengder av $M$ har minst tre elementer?
Hvor mange delmengder av $M$ finnes det som ikke inneholder $5$ eller $6$?
Antall delmengder med partall antall elementer er $\binom{6}{0} + \binom{6}{2} + \binom{6}{4} + \binom{6}{6} = 1 + 15 + 15 +1= 32$.
Antall delmengder med minst tre elementer er $2^6 -(\binom{6}{0}+\binom{6}{1} +\binom{6}{2})=64-(1+6+15)=42$.
Antall delmengder som ikke inneholder $5$ eller $6$ er det samme som å finne antall delmengder av $\set{1,2,3,4}$, som er $2^4 = 16$.
Test deg selv
Hvor mange relasjoner på mengden $A = \set{1, 2, 3, 4}$ finnes det dersom vi ser bort fra de som har nøyaktig fem tupler?
Vi finner først antallet relasjoner på mengden $A$. Den universelle relasjonen på en mengde med $4$ elementer har $4\cdot 4 = 16$ tupler i seg. Og siden vi for hvert tuppel kan velge om det skal være med eller ikke, får vi $2^{16} = 65538$ relasjoner.
Så må vi ta hensyn til restriksjonen som er at vi skal se bort i fra alle relasjoner med $5$ elementer. Antall relasjoner blir antall måter man kan velge $5$ elementer fra $16$ mulige, siden det er $16$ mulige tupler å velge fra. Det blir altså ${16\choose 5} = 4368$. Svaret får vi ved å trekke relasjonene med $5$ elementer, fra antall relasjoner på mengden $A$: $2^{16} - {16\choose 5} = 65538 - 4368 = 61168$
Utfordring
For et vilkårlig naturlig tall $n$, la $B= \set{1,2,\ldots,n}$, altså mengden av alle naturlige tall fra $1$ til $n$, og la $A=\set{1,2,\ldots, 2n}$. Dersom $n=4$, hvor mange funksjoner finnes det fra $A$ til $B$, som er slik at for hvert element $z \in B$, finnes det nøyaktig to ulike elementer $x,y \in A$ som er slik at $f(x) = f(y) = z$?
For hvert element i verdimengden $B$, tenk at vi skal velge to elementer fra definisjonsmengden $A$. Dette tilsvarer at de to elementene i $A$ peker på dette elementet i $B$. For $n=4$ har vi åtte elementer i $A$, og fire elementer i $B$. Så for element nummer $1$ i $B$, har vi da åtte elementer i $A$ å velge to ut fra. Dette kan vi gjøre på $\binom{8}{2} = 28$ måter.
For element nummer $2$ i $B$ har vi nå seks elementer i $A$ som ikke er brukt allerede. Disse kan vi velge to fra på $\binom{6}{2} = 15$ ulike måter. For element nummer $3$ kan vi velge to elementer på $\binom{4}{2} = 6$ måter. For det siste elementet i $B$ gjenstår det bare to elementer i $A$, som vi da kan velge på $\binom{2}{2} = 1$ måte. Multipliserer vi dette sammen, får vi $\binom{8}{2} \cdot \binom{6}{2}\cdot\binom{4}{2}\cdot\binom{2}{2} = 28\cdot 15\cdot 6 \cdot 1 = 2520$.