LEKTION 03-16

Vi börjar med några räkningsprinciper.

Antag att vi ska välja mellan två objekt, A och B, där A förekommer i n varianter och B förekommer i m varianter. Det betyder att vi har två mängder, A med kardinaliteten n och B med kardinaliteten m och vi ska välja ett element i A eller ett element i B.

Så vi ska välja bland elementen i A ∪ B. Då vi kan anta att mängder är disjunkta har vi att

|A ∪ B| = |A| + |B| = n + m

Så det finns n + m varianter att välja ett objekt som förekommer i n varianter eller ett objekt som förekommer i m varianter. Detta kallas additionsprincipen.

Antag att vi har n möjlighet att välja ett objekt i A och m möjlighet att välja ett objekt i B ( samma som tidigare), men antag nu att vi vill välja först ett objekt i A och därefter ett objekt i B.

Hur många alternativ har vi totalt?

Här ska vi beräkna antal par (a, b), där a ∈ A och b ∈ B, så |A × B| = |A| · |B|. Så antalet sätt att välja först en av n varianter och därefter en av m varianter är n · m. Det kallas multiplicationsprincipen.

Exempel. Låt A vara en mängd. Vi har redan definerat

P (A) = {B ⊆ A}.

Antag |A| = k då är

|P (A)| = 2^{k}.

Man kan faktiskt bilda en delmängd B ⊆ A genom att man går genom alla element i A och beslutar om de ingår i B eller inte. Eftersom det finns två alternativ för varje elemnt i |A| kan man tänka på B som (Ja, Nej, Nej, ...), en sekvens med |A| antal platser, som består av Ja och Nej.

En sekvensen på formen (Y a, Nej, Nej, ...) kan betraktas som ett elemnet i

T × T × ... × T |A| gånger, dät T = {Y a, Nej}

Och |T × T × ... × T | = |T | · |T | · ... · |T | = 2^{|A|}.

Exempel. Ett vanligt svensk bilnummer består av tre bokstver mellan A och Z, inklusive W, men utan I, Q och V, följt av tre siffror. Hur många bilnummer kan man konstruera enligt denna specifikation?

En bilnummer kan skrivas som

(Bokstav, Bokstav, Bokstav, Siffra, Siffra, Siffra)

Låt B = { bokstäver mellan A och Z, inklusive W, men utan I, Q och V } och A = {n ∈ ℕ|n ≤ 9}. Så är |A| = 10 och |B| = 26 − 3 = 23. En bilnummer är ett element i B × B × B × A × A × A. Så det finns 10^{3} · 23^{3} många bilnummer som man kan konstruera enligt denna specifikation.

1. Permutationer

Betrakta mängden A = {1, 2, 3, 4, 5}. Om vi vill välja 3 element i A “med uppprepning”, dvs att varje elemnt kan väljas mer än en gång har vi 5 · 5 · 5 alternativ.

Om vi vill välja 3 element “utan upprepning”, dvs att först vi väljer ett element, sedan väljer vi ett element some är skillt från föregående element och så vidare, då har vi bara 5 · 4 · 3 alternativ.

Notera att val (123) och (321) är olika. Det betyder att två olika ordning ger två olika val. Vi säger att vi väljar “med hänsyn till ordning”.

Så man kan välja med eller utan upprepring och med eller utan hänsyn till ordning! Vi ska först prata om ordnade urval. På samma sätt som tidigare ser vi att:

• Det finns n · ... · n (r gånger) många alternativ att välja r element från n element, med uppprepning.

• Det finns n(n − 1)(n − 2) · ... · (n − r + 1) många alternativ att välja r element

från n element, utan uppprepning. För att kunna fortsätta diskussionen behöver vi lite mer terminologi. Först ska vi prata lite om “ordningen”.

Definition 1.1. Varje uppställning av ett antal olika objekt i någon ordning kallas permutation av dessa objekt.

Hur kan man “konstruera” en permutation? Om vi har n objekt kan vi först bestämma objekt som ska stå på plats 1, sedan objekt på plats 2 , och så vidare. Vi ser alltså att antalet permutationer är lika med antalet alternativ att välja, utan upprepning och med hänsyn till ordning n element av n element så:

n(n − 1)(n − 2)(n − 3)...2 · 1

Detta heltal betecknas med n! (n fakultet).

Exempel. Antalet permutationer mellan A, B, C är 3! = 6 De är: ABC, ACB, BAC, BCA, CAB, ABA. Notera att:

• vi sätt 0! = 1.

• n! = n · (n − 1)!.

Genom att använda “fakultetsbeteckningen” kan man skriva:

n(n−1)·(n−r+1) = \frac{[n(n − 1) · (n − r + 1)](n − r)!}{(n − r)!} = \frac{n(n − 1)(n − 2)(n − 3)...2 · 1}{(n − r)!} = \frac{n!}{(n − r)!}

Vi ska använda symbolen P (n, r) för antalet sätt att välja r objekt mellan n olika objekt med hänsyn till ordning och utan upprepning. Så:

P (n, r) = \frac{n!}{(n − r)!}.

Exempel. Bestäm antalet 6 siffriga jämna heltal om ingen siffra förekommer mer än en gång.

Jämna heltal slutar med en jämn siffra, 0, 2, 4, 6, 8. Vi ska beräkna antal sätt att välja 6 siffror, utan upprepning när

• första siffra kan väljas bland 1, ..., 9

• följande 4 kan väljas bland 0 och 9

• sista kan väljas bland 0, 2, 4, 6, 8. Det är lättare att dela upp alternativ i tvaa grupper:

(1) heltal som slutar med 0

(2) heltal där sista siffran är skild från 0. Enligt multiplikations principen finns det 9 · 8 · 7 · 6 · 5 = 15120 element i första gruppen.

För att beräkna antal element i andra gruppen börjar vi på sista siffran (där vi har 4 olika alternativ) och sedan fortsätter vi från första siffran. Så det finns 4·8·8·7·6·5 = 53760 många alternativ.

Totalt har vi 53760 + 15120

Exempel.

• Antalet permutationer av bokstäverna i BLÅGRÖN är

7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040.

• Om vi vill bara välja 4 bokstäver kan vi göra så det P (7, 4) olika sätt:

P (7, 4) = \frac{7!}{(7 − 4)!} = 7 · 6 · 5 · 4 = 840

• Om vi vill välja 4 bokstäver med uppräpning har vi

7^{4} = 2401

många alternativ. Idag har vi visat att:

• Det finns n! sätt att ordna upp n ebjekt.

• Antal sätt att välja k element bland totalt n, med hänsyn till ordning och med upprepning är n^{k}.

4 LEKTION 03-16

• Antal sätt att välja k element bland totalt n, med hänsyn till ordning och utan upprepning är \frac{n!}{(n−k)!}.