LEKTION 03-03

“Kombinatorik handlar om konsten att räkna antalet möjliga händelser.” Det kan kännas lätt att säga och göra, men det kan ackså vara vänlig listig. Till

exempel:

• På hur mnga sätt kan man välja ett par (a, b) om man kan välja a på 100 olika sätt och b på 1000 olika sätt?

• Hur många gånger uppträder mönstret 0101 in en lång sekvens bestånde av 0 och

1? Först ska vi införa terminologin för att formulera problemet. Vi ska undersöka hur kan man “gruppera saker” och vilka matematiska operationer man kan utföra för att finna resultatet.

Mängdläran

Höjdpunkter är:

• Vad är en mängd;

• hur kan man beskriva en mängd;

• vilka operationer på mängder kan man utföra.

Definition 0.1. En mängd A är en samling av objekt som kallas element.

a ∈ A betyder att a är en element i A och a ∉ A betyder att a inte är en element i A.

Exempel • ∅ betecknar den tomma mängden, dvs mängden med inga element.

• universum U = {alla objekt};

• ℤ betecknar mängden av alla hela tal ..., −100, −99, ..., −1, 0, 1, ..., 100, ...; ℤ^{+} betecknar mängden av alla positiva hela tal 1, 2, ..., 100, ...;

• ℕ betecknar mängden av alla naturliga tal 0, 1, ..., 100, ...;

• ℚ betecknar mängden av alla rationella tal ..., −100, ..., \frac{−1}{2}, ..., \frac{1}{10}, ...; ℚ^{+} betecknar mängden av alla positiva rationella tal;

• ℝ betecknar mängden av alla reella tal ..., −100, ..., \frac{−1}{2}, ..., \frac{1}{10}, ..., \sqrt{3}, ...;

ℝ^{+} betecknar mängden av alla positiva reella tal; Det finns olika sätt för att beskriva en mängd:

(1) Man kan räkna upp mängdens element inom de så kallad mängdklammer. Exem-

pelvis

A = {1, 2, 3, 4, 5, 6, 7, 8}

(2) man kan ange egenskaperna hos mängdens element. Exempelvis kan mängden A

beskrivas som:

A = {n ∈ ℕ och 1 ≤ n ≤ 8}

(3) man kan visualisera mängden genom att använda ett så kallat venndiagram. Området

inom en sluten kurva i planet representerar elementen i mängden. Exempel: Beskriv mängden av alla heltal med absolut belopp mindre än eller lika med 4.

• {−4, −3, −2, −1, 0, 1, 2, 3, 4};

• {n ∈ ℤ och |n| ≤ 4};
• diagram;

Exempel: Betrakta mängden:

A = {n ∈ ℕ och n = k^{2} där k ∈ ℕ}.

• Är det så att 17 ∈ A? (Nej)

• Är det så att 21 ∉ A? (Ja)

• Är det så att 121 ∈ A? (Ja)

Storleken av en mängd kan vara mycket stor. Exempelvis är ℕ, ℤ, ℚ, ℝ oändliga mängder. Om man kan räkna upp alla element och det finns ett ändligt antal element säger man att mängden är ändlig. Symbolen |A| betecknar antalet element i A. Den kallas ofta för kardinaliteten av A. Exempel: Betrakta mängden

M = {n ∈ ℤ^{+}, n är udd och n ≤ 15}.

Då har vi M = {1, 3, 5, 7, 9, 11, 13, 15} och |M| = 8.

Klart är |∅| = 0.

Om man tar “bara några element av en mängd” får man en delmängd.

Definition 0.2. B är en delmängd av A (B ⊆ A) om varje element b ∈ B är ett element i A.

Exempel:

• Den tomma mängden ∅ är en delmängd av varje mängd. (Visa det!)

• A ⊆ A;

• { udda heltal } ⊂ ℤ;

• ℚ^{+} ⊂ ℚ; Nu kan vi bygga upp en ny mängd från A, nämlingen mängden av alla delmängder av

A:

P(A) = {B ⊆ A}

Låt A = {n ∈ ℕ, n jämn och 0 < n ≤ 6}. Då är A = {2, 4, 6} och

P(A) = {∅, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, A}

Så, |A| = 3 och |P(A)| = 8.

Fråga: Om |A| = k, vad är |P(A)|? Vi ska senare svara på detta!

Binära operationer på mängder

Låt A, B vara två mängder. Det finns ett antal sätt att bilda nya mängder från dem, genom så kallade binära operationer:

• Unionen: A ∪ B = {x, där x ∈ A eller x ∈ B};

• snittet: A ∩ B = {x, där x ∈ A och x ∈ B}; Om A ∩ B = ∅ säger vi att A och B är disjunkta.

• differensen: A \ B = {x, där x ∈ A och x ∉ B};

• komplement: A^{c} = {x, där x ∉ A}; (visa att A^{c} = U \ A).

Exempel:

• A ∩ B = B ochA ∪ B = A om B ⊆ A;

• ℕ ∩ ℤ = ℕ;

• ℤ^{+} = ℕ \ {0};

• {n ∈ ℕ där n är udda} ∪ {n ∈ ℕ där n är jämna} = ℕ. Vi har ofta skrivit att två mängder är lika, men vad betyder det? Vi säger att A = B om A ⊆ B och B ⊆ A.

Här finns en sammanställning av räkneregler:

(1) A ∩ A = A, A ∪ A = A, (A^{c})^{c} = A;

(2) A ∩ A^{c} = ∅, A ∪ A^{c} = U;

(3) A ∩ ∅ = ∅, A ∪ ∅ = A, A ∩ U = A,A ∪ U = U ;

(4) A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A

(5) Associativa lagar

(A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∪ C = A ∩ (B ∩ C)

(6) kommutativa lagar

A ∪ B = B ∪ A A ∩ B = B ∩ A

(7) distributiva lagar

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

(8) de Morgans lagar

(A ∪ B)^{c} = A^{c} ∩ B^{c} (A ∩ B)^{c} = A^{c} ∪ B^{c}

Övning: Visa dem.

Samband mellan delmängders storlek

Det är självklart att om B ⊆ A är |B| ≤ |A| (visa det!). Vad är sambanden mellan |A|, |B|, |A ∪ B| och |A ∩ B|? Låt A = {1, 2, 3, ..., 25} och B = {24, 25, ..., 100}. Vi har:

A ∪ B = {1, ..., 100}, A ∩ B = {24, 25}

och |A ∪ B| = 100 ≠ |A| + |B| = 25 + 77.

Faktiskt när räknar vi elementen i A och sedan elementen i B, så räknar vi elementen i A ∩ B två gånger, därför måste:

|A ∪ B| = |A| + |B| − |A ∩ B|

Detta är den Inklusion-exklusion principen.

Så gäller |A ∪ B| = |A| + |B| bara när A och B är disjunkta.

Exampel: Bestäm antalet jämna heltal mellan 1 och 2000.

Låt A = {jämna heltal} och B = {udda heltal}. Eftersöm de jämna och udda heltalen alternerar är |A| = |B| och |A ∩ B| = ∅, så har vi

2000 = |A ∪ B| = |A| + |B| = 2|A|

och |A| = 1000.

Det finns ett ytterligare mycket viktigt sätt att bygga upp en mängd från två mängder A och B, den så kallade produktmängden:

A × B = {(a, b) där a ∈ A, b ∈ B}

Ett element av (a, b) ∈ A × B kallas ett par av objekt i A och B. Lättast är att beskriva produktmängden som en tabell. Till exempel tåt A = {a, b, c} och B = {1, 2, 3, 4}. Följande tabellen ger alla element i A × B:

A B C
1 (a,1) (b,1) (c,1)
2 (a,2) (b,2) (c,2)
3 (a,3) (b,3) (c,3)
4 (a,4) (b,4) (c,4)

Övning. Bestäm |A × B| om |A| = k coh |B| = h.