Föreläsningsanteckningar till diskret matematik Thore Husfeldt

Materialet på dessa sidor skall uppfylla två syften på introduktionskursen i diskret matematik, där det används.

För det första är kursen i diskret matematik för många studenter det första mötet med matematisk formalism. Jag anser det för viktigt, att den basala terminologiska apparaten etableras på svenska, så att matematikens språk inte blir ytterligare främmandegjort. Det är därför min ambition att erbjuda en introducerande text på svenska, mitt fjärde språk – i sakens natur en uppgift, som kräver samvetsgrann rapportering av språkliga fel, vartill läsaren härmed är uppmuntrad.

För det andra tillåter jag mig att avvika från kursboken på några punkter, varför dessa anteckningar innehåller kompletterande material: En rad problematiserande exempel, som jag anser som värdefulla, och alternativa presentationer av till exempel diskret sannolikhetsteori. Dessutom finns det en fördjupning av grafteori till Ramseyteori och slumpgrafer.

Framställningen är vald kort och koncis snarare än beskrivande och förväntas kompletterad med föreläsningar eller en mer omfattande kursbok, som till exempel ‘Discrete mathematics with applications’ (McGraw–Hill, 1999), med vars notation och ämnesortering jag försökt vara kompatibel.

Thore Husfeldt Lund, 2001–2002

1. Två icke-triviala bevistekniker

1.1. Motsägelsebevis. Heltalen är mängden Z = {…, −2, −1, 0, 1, 2, … } (Z står för »Zahl«). Ett tal a är jämnt om det kan skrivas a = 2c för något c ∈ Z; annars är a udda.

Lemma 1. För alla a ∈ Z gäller att om a^{2} är jämnt, så är a jämnt.

Bevis. Om a är udda, så kan vi skriva a = 2c + 1 för något c ∈ Z. Då fås

a^{2} = (2c + 1)^{2} = 4c^{2} + 4c + 1 = 2(2c^{2} + 2c) + 1,

dvs a^{2} är udda.

De rationella talen är mängden Q = { p/q | p, q ∈ Z, q ≠ 0 } (Q för »Quotient«). Roten √y av y är den positiva lösningen till x^{2} = y.

Påstående 1 (Aristoteles). √2 ∉ Q.

Bevis. Antag att √2 ∈ Q för att nå en motsägelse. Vi kan välja a, b ∈ Z så att √2 = a/b och bråket är förkortat. Genom att kvadrera båda sidor fås 2 = a^{2}/b^{2}, som kan skrivas

2b^{2} = a^{2}. (1)

Vi ser att a^{2} är jämnt, och från lemmat ovan fås att även a är jämnt, dvs a = 2c för något c ∈ Z. Vi kan omskriva (1) till

2b^{2} = (2c)^{2} = 4c^{2},

varav b^{2} = 2c^{2}. Lemmat ovan ger att även b är jämnt. Men om båda a och b är jämna, så kan a/b förkortas. Detta strider mod att a/b är förkortat, vilket är absurt. Antagendet måste vara fel, dvs √2 ∉ Q.

1.2. Kåseri inför matematisk induktion. Låt P (n) beteckna påståendet

n < n^{2}.

Exempel.

1. P (5) är påståndet 5 < 5^{2}, som är sant. Även P (2), P (−1) och P (π) är sanna.

2. P (0), P (1) och P ( \frac{1}{2} ) är falska, så P (n) gäller inte för alla n ∈ Q och inte ens för alla n ∈ Z.

3. Matematisk analys tillåter följande resonemang: Låt f(n) = n och g(n) = n^{2}. Vi har f(2) < g(2). Derivatorna är f′(n) = 1 och g′(n) = 2n. Det är klart att 2n ≥ 1 för n ≥ 2, så f växer långsammare än g for n ≥ 1. Vi konkluderar att n < n^{2} för alla reella tal n ≥ 2.

Vi kan visa, att egenskapen P (n) ärvs av ett tals »högre granne«, dvs att om det gäller för ett konkret tal n (till exempel 5422,7), så gäller det också för n + 1 (till exempel 5423,7).

Lemma 2. Om n ≥ 0 och n < n^{2} så n + 1 < (n + 1)^{2}.

Bevis. Vi har

n + 1 < n^{2} + 1 ≤ n^{2} + 2n + 1 = (n + 1)^{2}.

Första olikheten gäller enligt hypotesen n < n^{2}. Andra olikheten gäller eftersom 2n > 0, vilket följer av hypotesen n > 0.

Vi kan nu använda lemmat som en sorts bevismaskin. Vi har set att P (2) gäller. Enligt lemmat gäller det då också för P (3). Men om det gäller för n = 3 så, enligt lemmat, gäller det för n = 4. Et cetera ad infimum; vi har implicit visat P (n) för alla heltal n ≥ 2. Observera att P (n) gäller för många flera tal (−1, π, …), vilket kräver andra bevis.

1.3. Exempel på matematisk induktion.

Påstående 2. n < n^{2} för varje heltal n ≥ 2.

Bevis. Låt P (n) beteckna påståendet n < n^{2}.

Bas: P(2) är sann eftersom 2 < 2^{2} = 4. Induktionssteg: Antag att P (n) är sann, dvs n < n^{2}. Vi skall visa att P (n + 1)

är sann, dvs (n + 1) < (n + 1)^{2}. Detta kan visas som följer:

n + 1 < n^{2} + 1 ≤ n^{2} + 2n + 1 = (n + 1)^{2},

där den första olikheten använder induktionshypotesen P (n), och den andra olikheten utnyttjar att n ≥ 0.

1.4. Kommentarer till notation. Följande alternativ till formuleringen av påståendet är ekvivalenta:

1. n < n^{2} för alla heltal n ≥ 2

2. n < n^{2} (n ∈ Z, n ≥ 2)

3. Låt n vara ett heltal som uppfyller n ≥ 2. Då gäller n < n^{2}.

4. Om 2 ≤ n ∈ Z så n < n^{2}. Det finns också alternativ till bevisets formulering. Speciellt kan manipulation-

erna i induktionssteget dekoreras med deras förklaring:

n + 1 < n^{2} + 1 (med induktion)
≤ n^{2} + 1 + 2n (eftersom 2n ≥ 0 för n ≥ 2)
= (n + 1)^{2}.

Det sista är en enkel omskrivning och behöver ingen förklaring.

Uppgifter.

1. Visa \sqrt[3]{2} ∉ Q.

2. Visa per induktion n < n^{3} för varje heltal n ≥ 2.

3. På en ö lever k logiker, varav exakt b har blå ögon (0 ≤ b ≤ k). Öns religion föreskriver att (1) hela befolkningen träffas varje kväll till gemensam bön och (2) om man får reda på att man har blå ögon, måste man begå självmord nästa morgon kl sju på offerplatsen. Eftersom det inte finns speglar och alla på ön är snälla (det är tabu att tala om för någon att de har blå ögon), vet ingen om att hon själv har blå ögon, och samhället fungerar utan problem. Tills en brunögd kristen missionär besöker ön. I frustration över sitt misslyckande att omvända befolkningen säger han till kvällsbönen, så alla kan höra det, »Det finns blåögda på ön, dvs b ≠ 0.« Vad händer och när?

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

2. Informell logik

2.1. Logiska utsagor. En utsaga är ett påstående som har ett sanningsvärde, dvs är antingen sant eller falskt. Vi skriver s och f för dessa värden.

Om p är en utsaga definieras (¬p), kallad negationen av p, enligt följande:

\begin{matrix}p & ¬p \\ s & f \\ f & s \end{matrix}

Om p och q är utsagor definieras deras disjunktion (p ∨ q), konjunktion (p ∧ q), exklusive disjunktion (p ⊕ q), implikation (p → q) och ekvivalens (p ↔ q) enligt följande:

p q p ∨ q p ∧ q p ⊕ q p → q p ↔ q
f f f  f  f  s  s
s f s  f  s  f  f
f s s  f  s  s  f
s s s  s  f  s  s

För att reducera antalet parenteser antar vi konventionen att negation används först: ¬p ∨ q är det samma som ((¬p) ∨ q).

2.2. Logisk ekvivalens och sanningstabeller. En utsaga som alltid är sann kallas tautologi, och en som alltid är falsk kallas en motsägelse. Utsagorna p och q kallas logiskt ekvivalenta om p ↔ q är tautologisk. Detta skrivs p ⇔ q.

Exempel.

1. (p ∨ ¬p) är en tautologi. För att inse detta kollar vi alla värden för p genom att betrakta sanningstabellen för (p ∨ ¬p):

\begin{matrix}p & ¬p & (p ∨ ¬p) \\ s & f & s \\ f & s & s \end{matrix}

Vi har visat (p ∨ ¬p) ⇔ s.

2. (p ∧ ¬p) är en motsägelse:

\begin{matrix}p & ¬p & (p ∧ ¬p) \\ s & f & f \\ f & s & f \end{matrix}

3. (p → q) och (¬p ∨ q) är logiskt ekvivalenta:

p q ¬p ¬p ∨ q
s s f  s
s f f  f
f s s  s
f f s  s

Vi ser att kolumnen till höger är den samma som definitionen av (p → q). Vi har visat (p → q) ⇔ (¬p ∨ q) .

2.3. Logisk algebra.

Påstående 3. Låt p och q vara utsagor. Då gäller

1. Absorbering:

p ∧ s ⇔ p, p ∨ f ⇔ p.

2. Dominans:

p ∨ s ⇔ s, p ∧ f ⇔ f

3. Idempotens:

p ∨ p ⇔ p, p ∧ p ⇔ p

4. Dubbel negation:

¬(¬p) ⇔ p

5. Kommutativa lagar:

p ∨ q ⇔ q ∨ p, p ∧ q ⇔ q ∧ p.

6. Associativa lagar:

(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r), (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r).

7. Distributiva lagar:

p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r).

8. De Morgans lagar:

¬(p ∧ q) ⇔ ¬p ∨ ¬q, ¬(p ∨ q) ⇔ ¬p ∧ ¬q.

9. Logisk ekvivalens av kontraposition:

p → q ⇔ ¬q → ¬p

10. Ytterligare ekvivalenser:

p ↔ q ⇔ (p → q) ∧ (q → p), p → q ⇔ (¬p ∨ q).

Bevis. Sanningstabeller.

Associativitetslagen tillåter att vi skriver p ∨ q ∨ r för båda (p ∨ q) ∨ r och p ∨ (q ∨ r).

Exempel.

1. Vi kan visa

¬(p ∨ (¬p ∧ q)) ⇔ ¬p ∧ ¬q.

genom att använda de algebraiska lagarna från påstående 3. [R: example 1.2.5]

2. Vi kan visa samma resultat med sanningstabeller.

Om p_{1}, p_{2}, …, p_{n} är utsagor skrivs

p_{1} ∨ p_{2} ∨ ⋯ ∨ p_{n}, eller ⋁_{i=1}^{n} p_{i},

för utsagan som är sann om och endast om minst en p_{i} är sann. Motsvarande skrivs

p_{1} ∧ p_{2} ∧ ⋯ ∧ p_{n}, eller ⋀_{i=1}^{n} p_{i},

för utsagan som är sann om och endast om alla p_{i} är sanna.

Påstående 4. Låt p_{1}, …, p_{n} vara utsagor och n ≥ 2. Då gäller De Morgans lagar,

¬ ⋁_{i=1}^{n} p_{i} ⇔ ⋀_{i=1}^{n} ¬p_{i}, ¬ ⋀_{i=1}^{n} p_{i} ⇔ ⋁_{i=1}^{n} ¬p_{i}.

Bevis. Vi visar första påstående med induktion efter n. Andra påståendet visas på samma sätt.

Bas: För n = 2 är påståendet ¬(p_{1} ∨ p_{2}) ⇔ (¬p_{1} ∧ ¬p_{2}). Detta har visats i påstående 3.

Induktionssteg: Antag n ≥ 2 och att påståendet gäller för n−1. Låt q beteckna utsagan p_{1} ∨ … ∨ p_{n−1}. Vi har

¬ ⋁_{i=1}^{n} p_{i} ⇔ ¬(q ∨ p_{n}) ⇔ ¬q ∧ ¬p_{n},

från påstående 3. Per induktion har vi

¬q ⇔ ⋀_{i=1}^{n−1} ¬p_{i},

dvs att

¬q ∧ ¬p_{n} ⇔ ( ⋀_{i=1}^{n−1} ¬p_{i}) ∧ ¬p_{n} ⇔ ⋀_{i=1}^{n} ¬p_{i}.

Uppgifter.

1. Visa hela påstående 3 med sanningstabeller.

2. Komplettera beviset för påstående 4.

2.4. Kvantorer. Ett påstående där det ingår (fria) variabler kallas ett predikat och har generellt inget sanningsvärde.

Exempel. Predikatet (x + y = z) ∨ (z > 5) har tre fria variabler, x, y och z. Vi kan beteckna det med P (x, y, z). Påståendet P (1, 2, 3) anger (1 + 2 = 3) ∨ (3 > 5) och är sant. Påståendet P (1, 1, 0) är falskt. Påståendet P (x, y, 6) är sant, även om det innehåller fria variabler.

Om P (x) är ett predikat och U är en mängd anger universalkvantifieringen

∀x ∈ U: P (x)

utsagan att P (x) är sann för alla element x i U, och existenskvantifieringen

∃x ∈ U: P (x)

utsagan att P (x) är sann för något element x i U. Om mängden U (universet) är känd från kontexten skrivs ibland ∀xP (x) och ∃xP (x).

Exempel.

1. Den kommutativa lagen för de reella talen är

∀x ∈ R ∀y ∈ R: x + y = y + x.

2. Om U är mängden av människor och B(x, y) påståendet att y är x:s bästa vän, så säger

∀x ∈ U ∃y ∈ U ∀z ∈ U: B(x, y) ∧ ((z ≠ y) → ¬B(x, z))

att alla människor har exakt en bästa vän.

3. Gränsvärdet lim_{x→a} f(x) = L kan definieras som

∀ϵ > 0 ∃δ > 0 ∀x ∈ R: 0 < |x − a| < δ → |f(x) − L| < ϵ.

Observera den kreativa notation ∀ϵ > 0. Alternativet vore att definiera mängden av positiva heltal R_{+} och skriva ∀ϵ ∈ R_{+}.

4. Låt Q(x, y) beteckna utsagan x + y = 0 om reella tal x och y. Påståendet

∃y∀x Q(x, y)

är falskt medan påståendet

∀x∃y Q(x, y)

är sant.

Vi formulerar ytterligare två påstående om predikatlogiken utan bevis. Påstående 5. Låt [n] beteckna mängden {1, 2, …, n} och P ett predikat. Då

gäller 1. ⋁_{i=1}^{n} P (x_{i}) ⇔ ∃i ∈ [n]: P (x_{i}).

2. ⋀_{i=1}^{n} P (x_{i}) ⇔ ∀i ∈ [n]: P (x_{i}). Påstående 6. Låt P vara en utsaga. Då gäller

1. ¬∀x P (x) ⇔ ∃x ¬P (x).

2. ¬∃x P (x) ⇔ ∀x ¬P (x).

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

3. Mängder

3.1. Sekvenser. En sekvens är en lista av element i en specifik ordning. Vi skriver en sekvens genom att lista dess medlemmar i denna ordning inom ( ):

(x_{1}, x_{2}, …, x_{n}),

för en sekvens av längd n. Två sekvenser är lika, (x_{1}, …, x_{n}) = (y_{1}, …, y_{m}) om n = m och ∀i(x_{i} = y_{i}). En sekvens av längd 2 kallas en tuppel och en sekvens av längd n en n-tuppel.

Exempel.

1. Sekvensen av de första 6 primtalen är (2, 3, 5, 7, 11, 13).

2. Observera att

(1, 2) ≠ (2, 1), (1, 2) ≠ (1, 2, 2). (2)

3.2. Mängder. En mängd är en oordnad samling av element. Om elementet a tillhör mängden M skrivs a ∈ M, i motsatt fall a ∉ M. Vi skriver en mängd genom att lista dess medlemmar minst en gång och i godtycklig ordning inom { }:

{x_{1}, x_{2}, …, x_{n}}.

Exempel.

1. Observera att notationen inte är entydigt: mängden av de första 5 primtalen kan skrivas {2, 3, 5, 7, 11} men också {5, 11, 7, 2, 3} och även {2, 2, 2, 2, 2, 5, 11, 7, 3, 3}.

2. Varje typ eller klass i ett programspråk definierar en mängd bestånde av dess medlemmar (eller objekt). Till exempel kan vi betrakta boolean som mängden {s, f} och int={−2147483648, …, 2147483647}.

För att ange stora eller oändliga mängder används ofta tre prickar {e_{1}, e_{2}, … } för att uppfordra läsaren till att använda sin fantasi till att utvidga listan, fast på ett konservativt sätt.

Ett annat viktigt sätt att ange mängder är mängdkonstruktören

A = {x | P (x) }, (3)

där P är ett predikat, eller, om vi vill specificera en delmängd av en annan mängd,

B = { x ∈ A | P (x) }.

Exempel.

1. Mängden av tvåpotenser kan anges som {1, 2, 4, 8, 16, 32, … } eller som { i | i = 2^{j}, j ∈ N } eller med en ytterligare flexibilisering av notationen som { 2^{j} | j ∈ N }.

2. Om A är mängden av män anger

{ x ∈ A | x är son till Adam }

mängden { Kain, Abel } och

{ x ∈ A | x är Abels fader }

är mängden {Adam}. En låda som innehåller en hatt är inte det samma som en hatt, och av samma andledning är {Adam} inte det samma som Adam.

3. Välkända talmängder är:

N = {0, 1, 2, … }, naturliga tal,
Z = {…, −2, −1, 0, 1, 2 … }, heltal,
R, reella tal,
Q = { a/b | a, b ∈ Z och b ≠ 0 }, rationella tal
C = { a + bi | a, b ∈ R }, komplexa tal

4. Samma mängd kan anges på många sätt. Observera

{3, 5} = { x ∈ N | x är ett udda primtal mindre än 6 } =

{ x ∈ R | x^{2} − 8x + 15 = 0 }

Detta kanske känns fel för en datalog (eftersom talen har olika »typer«) men matematiken gör inte denna skillnad.

5. Det finns en del friheter map vad man får skriva i mängdkonstruktören, och tyvärr en massa godtyckligheter. Speciellt är { x ∈ A | P (x) } det samma som { x | P (x) och x ∈ A }. Vi föredrar ofta den första varianten, eftersom den preciserar universet.

6. Betrakta mängden av alla mängder, som inte har sig själv som element:

R = { x | x ∉ x }.

För alla mängder y gäller nu y ∈ R om och endast om y ∉ y, speciellt gäller (med y = R), att

R ∈ R om och endast om R ∉ R,

vilket är absurt. Detta exempel, Russels paradox, dyker upp i många variationer (till exempel barberaren som rakar alla på ön som inte rakar sig själva). Här är det menat som varning att mängdteorien kräver en ganska försiktig formalisering för att undvika inbyggda inkonsistenser. Läsaren får lita på, att en kraftfull och konsistent definition av vad (3) skall betyda, är möjlig.

Mängden utan element kallas den tomma mängden och betecknas ∅, vi har ∀x(x ∉ ∅). Vi säger att A är en delmängd av B och skriver A ⊆ B om varje element i A är ett element i B, dvs

∀x(x ∈ A → x ∈ B).

Observera notationsskillnaden: x ∈ A om och endast om {x} ⊆ A.

Påstående 7. För en godtycklig mängd B gäller ∅ ⊆ B.

Bevis. Givet elementet x. Vi vill visa implikationen x ∈ ∅ → x ∈ B. Men x ∈ ∅ är aldrig sant pga definitionen av ∅, så implikationen är sann.

Två mängder är lika, A = B, om A ⊆ B och B ⊆ A, som till exempel

{1, 2} = {2, 1}, {1, 2} = {1, 2, 2},

som bör jämföras med (2).

3.3. Mängdalgebra. Den kartesiska produkten av A och B är

A × B = { (a, b) | a ∈ A ∧ b ∈ B },

unionen eller föreningsmängden av A och B är

A ∪ B = { a | a ∈ A ∨ a ∈ B },

snittet eller skärningsmängden av A och B är

A ∩ B = { a | a ∈ A ∧ a ∈ B },

och differensen mellan A och B är

A − B = { a | a ∈ A ∧ a ∉ B }.

Mängderna A och B är disjunkta om A ∩ B = ∅. Om grundmängden U, som alla x tas från (universet) är entydigt, skrivs U − A även \overline{A}.

Påstående 8. Låt A, B, C ⊆ U vara mängder. Då gäller

1. Absorbering:

A ∩ U = A, A ∪ ∅ = A.

2. Dominans:

A ∪ U = U, A ∩ ∅ = ∅.

3. Idempotens:

A ∪ A = A, A ∩ A = A.

4. Dubbelt komplement:

\overline{(\overline{A})} = A.

5. Kommutativa lagar:

A ∪ B = B ∪ A, A ∩ B = B ∩ A.

6. Associativa lagar:

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

7. Distributiva lagar:

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

8. De Morgans lagar:

\overline{A ∪ B} = \overline{A} ∩ \overline{B}, \overline{A ∩ B} = \overline{A} ∪ \overline{B}.

Bevis. Vi visar den ena av De Morgans lagar och lämnar resten till läsaren.

För att visa \overline{A ∩ B} = \overline{A} ∪ \overline{B} visar vi inklusion åt båda hållen. Antag först att x ∈ \overline{A ∩ B}, dvs x ∉ A ∩ B. Detta ger att x ∉ A eller x ∉ B, dvs x ∈ \overline{A} eller x ∈ \overline{B}, varav x ∈ \overline{A} ∪ \overline{B}. Vi har visat att \overline{A ∩ B} ⊆ \overline{A} ∪ \overline{B}.

Antag nu att x ∈ \overline{A} ∪ \overline{B}. Detta ger att x ∈ \overline{A} eller x ∈ \overline{B}, dvs x ∉ A eller x ∉ B. Därför har vi x ∉ A ∩ B, dvs x ∈ \overline{A ∩ B}. Vi har visat att \overline{A} ∪ \overline{B} ⊆ \overline{A ∩ B} och vilket färdiggör beviset.

Exempel. Här är ett alternativt bevis för De Morgans lag, som använder logiska ekvivalenser: Eftersom

x ∉ A ∩ B ⇔ ¬(x ∈ (A ∩ B)) ⇔ ¬(x ∈ A ∧ x ∈ B) ⇔

¬(x ∈ A) ∨ ¬(x ∈ B) ⇔ (x ∉ A) ∨ (x ∉ B) ⇔ (x ∈ \overline{A}) ∨ (x ∈ \overline{B}) ⇔ (x ∈ \overline{A} ∪ \overline{B}) genom att använda De Morgans lag för propositioner, kan vi skriva

\overline{A ∩ B} = \{ x | x ∉ A ∩ B \} = \{ x | x ∈ \overline{A} ∪ \overline{B} \} = \overline{A} ∪ \overline{B}.

Om A_{1}, …, A_{n} är mängder skriver vi

⋃_{i=1}^{n} A_{i} = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n}

för föreningen av alla A_{i}, dvs mängden som innehåller alla element som finns i något A_{i}. Vi skriver

⋂_{i=1}^{n} A_{i} = A_{1} ∩ A_{2} ∩ ⋯ ∩ A_{n}

för snittet av alla A_{i}, dvs mängden som innehåller alla element som finns i varje A_{i}.

Påstående 9. Låt A_{1}, …, A_{n} ⊆ U vara mängder och n ≥ 1. Då gäller

\overline{⋃_{i=1}^{n} A_{i}} = ⋂_{i=1}^{n} \overline{A_{i}}, \overline{⋂_{i=1}^{n} A_{i}} = ⋃_{i=1}^{n} \overline{A_{i}}.

Bevis. Uppgift (induktion efter n).

3.4. Kardinalitet av ändliga mängder. Om A har exakt n element kallas A ändlig och kardinaliteten |A| är n. Potensmängden P (S) är mängden av alla delmängder av S.

Påstående 10. Om S är ändlig så gäller |P (S)| = 2^{|S|}.

Bevis. Induktion efter n = |S|.

Bas: Om n = 0 då är S = ∅, som bara har en delmängd: ∅ ⊆ ∅. Dvs |P (S)| = |P (∅)| = |{∅}| = 1 = 2^{0} = 2^{|S|}.

Induktionssteg: Antag som induktionshypotes att varje mängd med n element har 2^{n} delmängder. Vi skall visa, att varje mängd med n + 1 element har 2^{n+1} = 2^{n} + 2^{n} delmängder. Låt härtill A vara en mängd med |A| = n + 1 och fixera något a ∈ A. Vi kan skriva A = B ∪ {a} där B = A − {a}. Varje delmängd S av A antingen innehåller a eller inte, dvs

P (A) = { S | S ⊆ A, a ∈ S } ∪ { S | S ⊆ A, a ∉ S}
= { T ∪ {a} | T ⊆ B } ∪ { T | T ⊆ B }.

Eftersom uppdelningen är disjunkt har vi |P (A)| = |P (B)| + |P (B)| = 2^{n} + 2^{n} per induktion.

En k-delmängd är en delmängd med k element. Vi låter \binom{A}{k} beteckna mängden av k-delmängder av A.

3.5. Strängar. Ett alfabet Σ är en mängd vars element kallas tecken. En sträng över Σ är en ändlig sekvens av tecken från Σ. Mängden av strängar över Σ betecknas Σ^{∗}. En typisk sträng i Σ^{∗} skrivs w = (w_{1}, …, w_{n}) eller w_{1}w_{2} ⋯ w_{n}, där w_{i} ∈ Σ (1 ≤ i ≤ n). Strängens längd är l(w) = n. Strängen av längd noll betecknas λ (lambda, för tyska »leer«). Mängden av strängar av längd n över Σ betecknas Σ^{n}, dvs

Σ^{∗} = ⋃_{n≥0} Σ^{n}.

Sammanfogningen av två strängar u = (u_{1}, …, u_{n}) och v = (v_{1}, …, v_{m}) betecknas

uv = (u_{1}, …, u_{n}, v_{1}, …, v_{m}).

Den m-faldiga repitionen av en sträng u är sammanfogningen

u^{m} = \underbrace{uu ⋯ u}_{m termer} .

Speciellt definierar vi u^{0} = λ.

Exempel.

1. Mängden av bitsträngar är {0, 1}^{∗} = {λ, 0, 1, 00, 01, 10, 11, 000, … }.

2. {a}^{∗} = {λ, a, aa, aaa, …, a^{n}, … }.

3. ∅^{∗} = {λ}. För alla andra Σ ≠ ∅ har Σ^{∗} oändligt många element.

4. Om C är en javaklass så anger C[ ] klassen av strängar över C. Till exempel är boolean[ ] klassen av bitsträngar. Metoden length är längdfunktionen l.

Påstående 11. Låt u, v, w vara strängar och m, n ≥ 0. Då gäller

1. Absorbering: uλ = λu = u.

2. Konkatenering är associativ: u(vw) = (uv)w

3. u^{m}u^{n} = u^{m+n}.

4. l(uv) = l(u) + l(v).

5. l(u^{m}) = ml(u)

Det finns ett närt samband mellan sekvenser och strängar, så närt att vi ofta blandar ihop notation och begrepp.

Låt U = {u_{1}, …, u_{n}} vara ett ändligt univers. För en delmängd A ⊆ U definierar vi dess bitsträngsrepresentation som strängen a ∈ {0, 1}^{n} där

a_{i} = \{ \begin{matrix}1, & u_{i} ∈ A, \\ 0, & u_{i} ∉ A. \end{matrix}

Uppgifter.

1. Hitta en mängd A som är disjunkt med sig själv.

2. Visa |A ∩ B| ≤ |A ∪ B|. När gäller |A ∩ B| = |A ∪ B|?

3. Hitta ett nödvändigt och tillräckligt villkor för att (A ∩ B) ∪ C = A ∩ (B ∪ C). Villkoret får inte innehålla B. Bevisa ditt svar.

4. Ange ett element från varje av de följande mängder: N × Z × R, P (N × N), P (∅) × N, (N × N) − ((N − {0, 1}) × N), P (P (P (∅))).

5. Definiera tuppeln ( , ) som (x, y) = {x, {x, y}}. Visa att denna definition är ekvi-

valent med den urspungliga genom att visa att

(4) (x_{1}, y_{1}) = (x_{2}, y_{2}) medför x_{1} = x_{2} och y_{1} = y_{2}.

6. Definiera tuppeln ( , ) som (x, y) = {{x, 0}, {y, 1}}. Är egenskapen (4) fortvarande uppfylld? Bevisa ditt svar.

7. Ge motexempel som visar att följande definition av ( , ) inte uppfyller (4): (x, y) = {x, y}.

8. Här är några försök på att definiera 3-tuppeln ( , , ). Diskutera.

(a) (x, y, z) = {{x}, {x, y}, {x, y, z}}.

(b) (x, y, z) = (x, (y, z)).

(c) (x, y, z) = {{x, 0}, {y, 1}, {z, 3}}.

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

4. Funktioner

Låt A och B vara mängder. En funktion f från A till B, skrivit f: A → B är en tilldelning av exakt ett element från B till varje element i A. Vi kan skriva a ↦ b eller b = f(a) för att ange att b är detta element. Vi säger att b är a:s bild. Mängderna A och B heter f:s domän och kodomän. Funktionens värdemängd är

f(A) = ⋃_{a∈A} f(a).

Mängden av funktioner från A till B betecknas B^{A}.

Exempel.

1. Låt A vara en mängd. Identitetsfunktionen är

ι_{A}: A → A, a ↦ a

2. Låt A, U vara mängder med A ⊂ U. Den karakteristiska funktionen χ_{A}: S → {s, f} är

χ_{A}(a) = \{ \begin{matrix}s & x ∈ A \\ f & x ∉ A \end{matrix} .

3. För varje tal n ∈ Z definieras den konstanta funktionen

n: A → Z, x ↦ n.

Till exempel är 6(x) = 6 för alla x.

4. Golvfunktionen R → Z definieras av

⌊x⌋ = max{ n ∈ N | n ≤ x }

och takfunktionen R → Z definieras av

⌈x⌉ = min{ n ∈ N | n ≥ x }.

Det gäller (a) x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1

(b) ⌈−x⌉ = −⌊x⌋, ⌊−x⌋ = −⌈x⌉

(c) ⌈x + n⌉ = ⌈x⌉ + n, ⌊x + n⌋ = ⌊x⌋ + n, om n ∈ N.

5. I det funktionella programspråket Lisp definieras funktionen

f: Z → Z, x ↦ x^{2}

som

(define (f x) (* x x)) Språket Haskell är ett typad funktionellt språk, och här skrivs samma funktion på följande sätt:

f :: Integer → Integer

f x = x * x

6. Även en statisk metod i et objektorienterad språk som Java,

static B f(A x) kan betraktas som en funktion

f: A → B, x ↦ f(x).

Till exempel är följande funktion precis identitetsfunktionen på mängden int.

static int f(int x) { return x; }

7. En icke-statisk metod i Java är ingen funktion. Betrakta följande klass: class C { int i= 0;

int f(int x) { return i++; } } Första anrop av f returnerar 0, men nästa returnerar 1. Metoden tilldelar inte exakt ett element från kodomänet till varje element i domänet. Vi säger att ickestatiska metoder har tillstånd (eller minne); funktioner är därimot tillståndslösa.

8. Modelleringen av programspråkskonstruktioner vha matematiken är icke-trivial och föremål för datalogisk forskning på särdelas hög nivå. För att antyda problemen kan vi nämna terminering. Icke alla metoder, även de statiska, terminerar, som till exempel

static int f() { while(true) ; } eller

static float f(int x) { return 5/x; } I detta exempel går det ändå att beskriva

f: int − {0} → float

men generellt är metoders beteende för komplext till att restringera domänet. I stället kan man betrakta metoden som som

f: A → B ∪ {abort},

där »abort« är ett speciellt värde (som inte är i B), som tar hand om icketerminering.

4.1. Egenskaper. En funktion f: A → B är injektiv om

f(x) = f(y) ⇒ x = y (x, y ∈ A);

En ekvivalent och möjligen mera naturlig formulering är att f ger olika bilder på olika variabler:

x ≠ y ⇒ f(x) ≠ f(y) (x, y ∈ A).

Funktionen är surjektiv om f(A) = B. Funktionen är bijektiv om den är både injektiv och surjektiv.

Exempel. Identitetsfunktionen är bijektiv.

Sats 1. Givet två ändliga mängder A och B. Vi har |A| = |B| om och endast om det finns en bijektion A → B.

Bevis. Antag först att det finns en bijektion f: A → B. Sätt n = |A| och skriv A = {a_{1}, …, a_{n}}. Betrakta nu mängden

f(A) = {f(a_{1}), …, f(a_{n})}.

Eftersom alla element är olika (f är ju injektiv) har vi |f(A)| = n. Surjektivitet ger f(A) = B. Därför fås |B| = |f(A)| = n.

Skriv mängderna som A = {a_{1}, …, a_{n}} och B = {b_{1}, …, b_{m}} och antag nu n = m. Betrakta funktionen

f: A → B, a_{i} ↦ b_{i}.

Denna är väldefinierad eftersom n ≤ m. Funktionen är klart injektiv. Den är surjektiv eftersom m ≤ n.

För en injektiv funktion f: A → B definieras dess invers som

f^{−1} : f(A) → A, f(a) ↦ a.

Dvs att f^{−1}(b) = a när f(a) = b, vi kallar a för b:s urbild. Observera att f^{−1} inte är definierad för B − f(A).

Funktionens graf är en delmängd av A × B definierad med

graf(f) = { (a, b) | b = f(a), a ∈ A }.

Låt g: A → B och f: B → C. Då definieras den sammansatta funktionen h = f ∘ g som

h: A → C, a ↦ f(g(a)).

4.2. Uppräkneliga mängder. Vi återvänder till mängders kardinalitetsbegrepp. En mängd M är ändlig om |M| < ∞. En mängd är uppräknelig om den är

ändlig eller det finns en bijektion M → N. Kardinaliteten av en oändlig, uppräknelig mängd skrivs |N| = ℵ_{0} (alef-null). En mängd som inte är uppräknelig är överuppräknelig.

Exempel.

1. Z är uppräknelig; observera att detta strider mot intuitionen om att den är drygt dubbelt så stor som N. För att se detta, betrakta

f: N → Z, z ↦ \{ \begin{matrix}\frac{1}{2} z, & om z är jämnt; \\ − \frac{1}{2} (z + 1), & om z är udda. \end{matrix}

några värden kan ses här:

\begin{matrix}f(z) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & ⋯ \\ z & 0 & −1 & 1 & −2 & 2 & −3 & 3 & ⋯ \end{matrix}

Det är klart att alla heltal finns någonstans och exakt en gång på denna lista. Funktionen f är alltså en bijektion mellan N och Z.

Det är möjligen instruktivt att se ett felaktigt försök på en uppräkning, t ex först alla positiva tal, och sen alla negativa, som i

0, 1, 2, …, −1, −2, ….

Detta fungerar inte, vilket blir klart så fort man försöker att formalisera denna lista som en bijektion till N – vilket »nummer« får −1?

2. N × N är uppräknelig. Cantors argument för detta är som följer: Vi räknar N^{2} i varv. I varv 1 räknas bara (0, 0). I varv 2 räknas (1, 0) och (0, 1). Generellt räknas alla tuppler (i, j) i varv i + j + 1 i någon ordning. Varje varv är ändligt, så alla tuppler räknas (exakt en gång) förr eller senare. Bijektionen är t ex

f: N^{2} → N, f(i, j) = i + ∑_{k=1}^{i+j} k.

3. Σ^{∗} är uppräknelig om Σ = {σ_{1}, …, σ_{k}} är ändligt. Vi listar först λ, sen hela Σ, sen hela Σ^{2}, etc. i någon ordning, till exempel den lexikografiska. För Σ = {a, b} är avbildningen till exempel

z 0 1 2 3 4 5 6 7 ⋯; f(z) λ a b aa ab ba bb aaa ⋯

Bijektionen är

f: Σ^{∗} → N, f(σ_{i_{1}} ⋯ σ_{i_{n}}) = | ⋃_{r=0}^{n−1} Σ^{r}| + ∑_{r=1}^{n} i_{r}|Σ|^{r},

och f(λ) = 0.

Påstående 12. Om B är uppräknelig och A ⊆ B så är A uppräknelig.

Bevis. Om A är ändlig är vi klara. Antag alltså att A är oändlig. Uppräkningen av elementen i A är den samma som uppräkningen av B, där B −A har tagits bort. Formellt (men inte mycket klarare), om vi låter b_{1}, b_{2}, … ange uppräkningen av B:s element, är

f: A → N, f(b_{i}) = |{b_{1}, …, b_{i−1}} ∩ A|.

Detta är väldefinierat eftersom varje element i A kan skrivas som b_{i} för något i. Surjektiviteten följer av att A är oändlig.

Exempel. Q är uppräknelig, vilket är minst lika kontraintuitivt som att Z är det (det finns ju oändligt många rationella tal mellan 3 och 4, och – mera skrämmande – oändligt många mellan varje par av rationella tal). Vi visar detta bara för de positiva rationella talen, Q_{+}. För att inse påståendet kan vi betrakta Q_{+} som delmängd av N^{2}. Helt formellt betraktar vi funktionen

Q_{+} → N^{2}, a/b ↦ (a, b),

som är en bijektion mellan Q_{+} och en delmängd av N^{2}. Denna är uppräknelig enligt påst. 12.

4.3. En datavetenskaplig tillämpning. En funktion f: N → {s, f} kan javaberäknas om det finns ett metod static boolean m(Integer i) skriven i Java så att m(i) = f(i) för alla i ∈ N.

Påstående 13. Det finns funktioner N → {s, f} som inte kan javaberäknas.

Bevis. Låt J ange mängden av javaprogram. Om Σ anger mängden av Unicodetecken har vi J ⊆ Σ^{∗}. Eftersom Σ^{∗} kan räknas, kan J också det.

Vi visar nu att boolan^{N} inte kan räknas. Antag motsatsen, att en uppräkning f_{0}, f_{1}, … finns. Konstruera funktionen

d: N → boolean, d(i) = ¬f_{i}(i).

Enligt antagandet måste d finnas någonstans i listan, dvs d = f_{j} för något j. Vi har d(i) = f_{j}(i) för alla i, speciellt gäller

d(j) = f_{j}(j),

i motstrid med definitionen av d.

Vi konkluderar med påst. 12 att boolean^{N} inte kan vara en delmängd av J.

Uppgifter.

1. En funktion g: B → A är vänsterinvers till f: A → B om g ∘ f = ι_{A}. En funktion

g: B → A är högerinvers till f: A → B om f ∘ g = ι_{B}. (a) Visa att om f är injektiv, så har f en vänsterinvers.

(b) Visa att om f är surjektiv, så har f en högerinvers.

4.4. Summor. Om l ≤ r skriver vi

∑_{i=l}^{r} a_{i}

för summan a_{l} + a_{l+1} + ⋯ + a_{r}.

Påstående 14. För n ≥ 1 gäller

∑_{i=1}^{n} i = \frac{1}{2}n(n + 1).

Bevis. Induktion efter n.

Bas: För n = 1 är påståendet 1 = \frac{1}{2}1(1 + 1) = 1, vilket är sant. Induktionssteg: Antag påståendet för något n ≥ 1. Då fås

∑_{i=1}^{n+1} i = n + 1 + ∑_{i=1}^{n} i = n + 1 + \frac{1}{2}n(n + 1) = \frac{1}{2}(n + 2)(n + 1),

där induktionshypotesen används för att omskriva summan.

Påstående 15. Om r ≠ 1 och n ≥ 0 gäller

∑_{j=0}^{n} ar^{j} = \frac{ar^{n+1} − a}{r − 1}.

Bevis. Per induktion efter n.

Bas: För n = 0 är påståendet

a = \frac{ar − a}{r − 1} = \frac{a(r − 1)}{r − 1},

vilket är sant.

Induktionssteg: Antag påståendet för något n ≥ 1. Vi har

∑_{j=0}^{n+1} ar^{j} = ar^{n+1} + ∑_{j=0}^{n} ar^{j} = ar^{n+1} + \frac{ar^{n+1} − a}{r − 1} = \frac{ar^{n+2} − a}{r − 1},

där induktionshypotesen används för att omskriva summan. Som ett nyttigt specialfall av resultatet ovan har vi

∑_{i=0}^{n} 2^{i} = 2^{n+1} − 1.

Definiera de harmoniska talen H_{k} enligt

H_{k} = ∑_{i=1}^{k} \frac{1}{i}.

Vi har

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & ⋯ & 10000 & ⋯ \\ H_{k} & 1 & \frac{3}{2} & \frac{11}{6} & \frac{25}{12} & \frac{137}{60} & \frac{49}{20} & ⋯ & 14,39272 … & ⋯ \end{matrix}

Påstående 16. För n ≥ 0 gäller

H_{2^{n}} ≥ 1 + \frac{1}{2}n.

Bevis. Per induktion efter n.

Bas: För n = 0 är påståendet H_{1} = 1, vilket är sant. Induktionssteg: Antag påståendet för något n ≥ 1. Vi har

H_{2^{n+1}} = ∑_{i=1}^{2^{n+1}} \frac{1}{i} = ∑_{i=1}^{2^{n}} \frac{1}{i} + ∑_{i=2^{n}+1}^{2^{n+1}} \frac{1}{i} = H_{2^{n}} + ∑_{i=2^{n}+1}^{2^{n+1}} \frac{1}{i} ≥

H_{2^{n}} + 2^{n} · \frac{1}{2^{n+1}} = H_{2^{n}} + \frac{1}{2}.

Enligt induktionshypotesen är detta högst (1 + \frac{1}{2}n) + \frac{1}{2} = 1 + \frac{1}{2}(n + 1), som önskat.

Sätter vi k = 2^{n} i detta resultat fås

H_{k} ≥ 1 + \frac{1}{2} log k, k = 1, 2, 4, 8, 16, ⋯,

så vi kan uppskatta H_{k} (det harmoniska talet) för alla tvåpotenser. Det kan visas att

lim_{n→∞}(H_{n} − ln n) = γ,

där γ = 0,57727156649 … är Eulers konstant.

Exempel.

1. Det är instruktivt att försöka att bevisa H_{k} ≥ 1 + \frac{1}{2} log k per induktion efter k (i stället för efter 2^{k} som vi gjorde).

2. En långsam men envis mask M startar i ena ändan av ett meterlångt gummiband och kryper 1 cm per minut mot andra ändan. En lika envis gummibandsansvarig G, vars enda uppgift i livet är att frustrera M, drar vid slutet av varje minut ut bandet ytterligare en meter. Alltså är M efter en minuts krypande 1 cm från starten och 99 cm från slutet, och sen drar G ut bandet 1 m. När bandet dras ut behåller M sin relativa position: 1% från start och 99% från mål; dvs M är nu 2 cm från start och 198 cm från mål. När M har krupit ytterligare en minut, är han 3 cm från start och 197 cm från mål; när G drar blir avstånden 4,5 och 295,5.

När G drar i bandet är M:s relativa avstånd det samma. Han kryper alltså 1/100 av bandet i första minut, 1/200 i andra, etc. Efter n minut har han krupit

\frac{1}{100} ( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n} ) = \frac{H_{n}}{100} .

Han är klar när H_{n} ≥ 100. Efter 287 · 10^{33} sekler når han bandets slut, som nu är 10^{27} ljusår långt. Triumf!

4.5. Funktioners tillväxt. I detta avsnitt är

f, g: N → R

eller

f, g: R → R.

En funktion f är mindre än g (vi skriver f ≤ g) om

f(n) ≤ g(n), ∀n.

En funktion f är försumbar i jämförelse med g eller lilla ordo av g (vi skriver f(n) är o(g(n)) eller f(n) = o(g(n))) om

lim_{n→∞} \frac{f(n)}{g(n)} = 0.

En funktion f är högst g:s ordning eller stora ordo av g (vi skriver f(n) är O(g(n)) eller f(n) = O(g(n))) om

∃C, k > 0: n ≥ k → |f(n)| ≤ C|g(n)|.

En funktion f är stora omega av g (vi skriver f(n) är Ω(g(n)) eller f(n) = Ω(g(n))) om

∃C, k > 0: n ≥ k → |f(n)| ≥ C|g(n)|.

En funktion f är stora theta av g (vi skriver f(n) är Θ(g(n)) eller f(n) = Θ(g(n))) om

f(n) = O(g(n)) och f(n) = Ω(g(n)).

Påstående 17. 1. f ≤ g medför f(n) = O(g(n)).

2. f(n) = o(g(n)) medför f(n) = O(g(n)).

3. f(n) = Ω(g(n)) då och endast då g(n) = O(f(n))

4. f(n) = Θ(g(n)) då och endast då

∃C_{1}, C_{2}, k > 0: C_{1}|g(x)| ≤ |f(x)| ≤ C_{2}|g(x)|.

Exempel.

1. Låt f(n) = n och g(n) = n + 1. Vi har f ≤ g. Men lim_{n→∞} n/(n + 1) = 1, så f är inte lilla ordo av g.

2. Låt f(n) = n och g(n) = n^{2}. Vi har f( \frac{1}{2} ) > g( \frac{1}{2} ) så f är inte mindre än g. Men lim_{n→∞} n/n^{2} = lim_{n→∞} n^{−1} = 0, så f är lilla ordo av g.

3.

∑_{i=1}^{n} i ≤ ∑_{i=1}^{n} n = n^{2} = O(n^{2}),

med C = 1 och k = 1 i definitionen av stora ordo. 4.

∑_{i=1}^{n} i ≥ ∑_{i=⌈n/2⌉}^{n} i ≥ ∑_{i=⌈n/2⌉}^{n}⌈n/2⌉ =

(n − ⌈n/2⌉ + 1)⌈n/2⌉ ≥ (n/2)(n/2) = n^{2}/4 = Ω(n^{2})

med C = \frac{1}{4} och k = 1 i definitionen av stora omega. Med föregående exempel har vi alltså ∑_{i=1}^{n} i = Θ(n^{2}). Jämnför påst. 14.

5.

log(n!) = ∑_{i=1}^{n} log i ≤ ∑_{i=1}^{n} log n ≤ n log n = O(n log n)

med C = 1 och k = 1 i definitionen av stora ordo.

Lemma 3 (Generaliserad triangelolikhet). Om b_{1}, …, b_{n} ∈ R, så

|∑_{i=1}^{n} b_{i}| ≤ ∑_{i=1}^{n} |b_{i}|

Bevis. Induktion efter n.

Bas: För n = 1 är påståendet |b_{1}| = |b_{1}|, vilket är sant.

Induktionssteg: Vi vill först visa olikheten (»triangelolikheten«)

|a + b| ≤ |a| + |b|, a, b ∈ R. (5)

För att inse detta observeras först

a + b ≤ |a| + |b|, eftersom a ≤ |a|, b ≤ |b|,
−(a + b) ≤ |a| + |b|, eftersom − a ≤ |a|, −b ≤ |b|.

Eftersom |a + b| är antingen a + b eller −(a + b) följer (5) i alla fall.

Antag nu påståendet för något n ≥ 1 och betrakta

|∑_{i=1}^{n+1} b_{i}| = |b_{n+1} + ∑_{i=1}^{n} b_{i}| ≤ |b_{n+1}| + |∑_{i=1}^{n} b_{i}| ≤ |b_{n+1}| + ∑_{i=1}^{n} |b_{i}| = ∑_{i=1}^{n+1} |b_{i}|,

där olikheterna använder respektive triangelolikheten och induktionshypotesen.

Påstående 18. Om a_{0}, …, a_{n} ∈ R, så

∑_{i=0}^{n} a_{i}x^{i} = O(x^{n}).

Bevis. För x > 1 har vi

|∑_{i=0}^{n} a_{i}x^{i}| ≤ ∑_{i=0}^{n} |a_{i}|x^{i} = x^{n} ∑_{i=0}^{n} |a_{i}|x^{i−n} ≤ x^{n} ∑_{i=0}^{n} |a_{i}|.

Detta visar påståendet med C = ∑_{i=0}^{n} |a_{i}| och k = 1 i definitionen av stora ordo.

Om f, g: A → R definieras funktionerna f + g och fg som

(f + g): A → R, (f + g)(x) = f(x) + g(x),
(f · g): A → R, (f · g)(x) = f(x) · g(x).

Påstående 19. Om f_{1}(n) = O(g_{1}(n)) och f_{2}(n) = O(g_{2}(n)), så gäller

1. (f_{1} + f_{2})(n) = O(g_{1}(n) + g_{2}(n)) = O(max{g_{1}(n), g_{2}(n)})

2. (f_{1} · f_{2})(n) = O(g_{1}(n) · g_{2}(n))

Bevis. [Rosen, Thm. 1.8.1, 1.8.2].

Uppgifter.

1. Om man kastar Kenny ut ur fönstret dör eller överlever han beroende på vilken våning han kastas från. Upp till och inklusive våning K (ett för oss okänd men fast tal, som vi kaller kennytalet), mår han fint; kastas kan från våning K + 1 eller högre, då dör han. Vi försöker att fastställa kennytalet.

Om vi bara har en Kenny till förfogande kastar vi honom från våning 1,2,3, etc. tills han dör. Vi behöver O(K) kast för detta. Har vi två Kennyr kan vi kasta den första från våning 1, 3, 5 etc. tills han dör och därefter bestämma det exakta kennytal med ett extra kast. Det tar bara ⌈(K + 1)/2⌉ + 1 kast vilket dock fortfarande är O(K). Det känns som om vi har slösat bort den andra Kennyn.

Hitta en metod för att bestämma kennytalet med två Kennyr och asymptotisk färre kast än O(K). Ledning: det går att göra i O(\sqrt{K}).

2. Ordna följande funktioner efter deras tillväxt, dvs skriv dem på en lista f_{1}(n), f_{2}(n), …, så att f_{i}(n) = O(f_{i+1}(n)):

10^{10}, n^{2}, log n, log log n, (log n)^{2}, \sqrt{log n}, n!, n^{n},

n^{2} log n, n log n log log n, n^{3/2}, 2^{n}, 2^{n^{2}}, 3^{n}, log(n^{2} + 1)

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

5. Kombinatorik

5.1. Summa- och produktprincipen. Produktprincipen säger att två oberoende händelser kan uppträda på lika många sätt som produkten av varje. I mängdnotation: |A × B| = |A| · |B|.

En annan, och mera generell, formulering är följande. Låt U_{1}, …, U_{m} vara en sekvens av uppgifter och antag att U_{i} kan göras på n_{i} sätt efter att U_{1}, …, U_{i−1} har gjorts. Då kan hela sekvensen av uppgifter göras på n_{1} ⋯ n_{m} sätt.

Exempel.

1. Om A är en ändlig mängd, så är |P (A)| = 2^{|A|}. För att räkna antal delmängder räknar vi antal olika sätt att välja en delmängd. En delmängd B av A kan väljas på följande sätt: för varje element x ∈ A väljer vi, om x skal tillhöra B eller ej. Vi har |A| val, varje val kan göras på två sätt. Produktprincipen ger att det finns 2^{|A|} sätt att välja B på.

2. |Σ^{k}| = |Σ|^{k}. En sträng σ_{1} ⋯ σ_{k} ∈ Σ^{k} kan skapas genom att välja först σ_{1}, sen σ_{2}, etc. Varje tecken kan väljas på |Σ| sätt.

3. |A^{k}| = |A|^{k}. En tuppel i A^{k} kan skapas genom att välja k värden från A.

4. |B^{A}| = |B|^{|A|}. En funktion f: A → B kan skapas på följande sätt: för varje element i definitionsmängden a ∈ A väljer vi värdet f(a) ∈ B. Det finns |A| val mellan |B| möjligheter.

5. Vi räknar de injektiva funktionerna från A till B. Om |A| > |B| finns det inga injektiva funktioner från A till B, så vi betraktar det intressantare fallet |A| ≤ |B|. Låt A = {a_{1}, …, a_{m}}. Vi vill välja f(a_{1}), f(a_{2}), … i tur och ordning. Det finns |B| möjligheter för att välja f(a_{1}). Eftersom f är injektiv finns måste f(a_{2}) väljas från B −f(a_{1}), det finns |B|−1 möjligheter för detta. Generellt kan vi välja f(a_{k}) på |B|−k +1 sätt. Enligt produktprincipen finns det |B|(|B|−1) ⋯ (|B|−|A|+1) injektiva funktioner.

Två händelser är ömsesidigt uteslutande om de inte kan uppträda samtidigt. Summaprincipen säger att någon av två ömsesidigt uteslutande händelser kan uppträda på lika många sätt som summan av varje. I mängdnotation: om A ∩ B = ∅ så |A ∪ B| = |A| + |B|.

En annan, och mera generell, formulering är följande: Låt U_{1}, …, U_{m} vara en sekvens av uppgifter och antag att U_{i} kan göras på n_{i} sätt. Då kan uppgiften »antingen U_{1} eller U_{2} eller ⋯ eller U_{m}« göras på n_{1} + ⋯ + n_{m} sätt.

Inkludering-exkluderingsprincipen är en utvidgning av summaprincipen. I mängdnotation: |A ∪ B| = |A| + |B| − |A ∩ B|.

Exempel.

1. Låt Σ^{≤m} ange mängden av strängar över Σ av längd högst m, dvs

Σ^{≤m} = ⋃_{i=0}^{m} Σ^{i}.

Vi vill visa att |Σ^{≤m}| = ∑_{i=0}^{m} |Σ|^{i}. En sträng i Σ^{≤m} har antingen längd 0 eller 1 eller ⋯ eller m. Vi kan välja en sträng av längd i på |Σ|^{i} sätt, som vi såg enligt produktregeln i exemplet ovan.

2. Låt S vara mängden av bitsträngar av längd 6 som börjar på 1 eller slutar på 00. För att beräkna |S| betraktar vi två relaterade mängder: A är mängden av längd-6-bitsträngar som börjar på 1, och B är mängden av längd-6-bitsträngar som slutar på 00. Produktprincipen ger |A| = 2^{5} och |B| = 2^{4}. Dessa mängder är inte disjunkta, och produktprincipen ger |A ∩ B| = 2^{3}. Inkludering-exkluderingsprincipen ger |S| = 2^{5} + 2^{4} − 2^{3} = 40.

5.2. Duvhålsprincipen. Om n+1 duvor fördelas på n hål måste ett hål innehålla minst två duvor.

Exempel.

1. I en grupp på 367 människor måste två ha samma födelsedag (födelsedagssatsen).

2. Om n + 1 tal väljes ur {1, 2, 3, …, 2n} så dividerar ett av talen ett annat. (Observera först att om vi bara väljer n tal, t ex {n+1, n+2, …, 2n}, behöver de inte dividera varann.) För att bevisa påståendet skriver vi varje tal som produkten av en tvåpotens och ett udda tal, t ex 40 = 2^{3} · 5, 1 = 2^{0} · 1, 14 = 2^{1} · 7, etc. Vi placerar talen i n lådor 1, 3, 5, …, 2n − 1 så att talet 2^{i} · l hamnar i låda l. Det finns n + 1 tal och bara n lådor, så en av lådorna måste innehålla två tal, kalla dem 2^{i} · l och 2^{j} · l (i < j). Vi har 2^{j} · l/(2^{i} · l) = 2^{j−i}.

3. Vi vill visa vänskapssatsen: i varje grupp av sex personer finns tre vänner (dvs varje par har redan träffats tidigare) eller tre främlingar (dvs ingen av de tre har träffats tidigare). Kalla personen Ett, Två, …, Sex. Vi kan indela Två till Sex i två mängder, V (Etts vänner) och F (främlingar för Ett). Enligt den utvidgade lådprincipen har en av mängderna minst ⌊(5 − 1)/2⌋ + 1 = 3 element. Det finns två fall. Om V har 3 element är de antingen främlingar för varann (då har vi en trio främlingar) eller minst två av dem är vänner och skapar därmed en trio vänner med Ett. Om F har 3 element är de antingen en trio vänner eller minst två av dem är främlingar (då har vi en trio främlingar med Ett). Vänskapssatsen är bevisad.

Observera att en grupp på 5 personer inte är nog. Om vi ritar vänner som ∘ ∘ och främlingar som ∘ ∘ då kan vi rita gruppen

[figure: ∘; ∘; ∘; ∘; ∘]

5.3. Permutationer och kombinationer. En r-permutation av en mängd S är ett ordnat arrangemang av r element från S. Om r = |S| kallas arrangemanget en permutation av S.

Sats 2. Antalet r-permutationer av en mängd med n element är

P (n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1) = \frac{n!}{(n − r)!}.

En r-kombination av en mängd S är en r-delmängd av S.

Sats 3. Antalet r-kombinationer av en mängd med n element är

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

Sats 4. För positivt heltal n gäller

(x + y)^{n} = ∑_{i=0}^{n} \binom{n}{i}x^{n−i}y^{i}.

Påstående 20. Låt 0 ≤ r ≤ n och r ≤ m. Då gäller 1.

\binom{n}{r} = \binom{n}{n − r}

2.

\binom{n + 1}{r} = \binom{n}{r − 1} + \binom{n}{r}.

3.

∑_{r=0}^{n} \binom{n}{r} = 2^{n}.

4.

\binom{n + m}{r} = ∑_{i=0}^{r} \binom{m}{r − i}\binom{n}{i}

5.4. Några uppskattningar. Binomialkoefficienterna är notoriskt svårtberäknade. Det är klart att 0 ≤ \binom{n}{k} < 2^{n}, och detta avsnitt etablerar några mer försiktiga uppskattningar, som är tillräckligt precisa i många fall.

För n ≥ k > 2 gäller

\frac{n}{k} ≤ \frac{n − 1}{k − 1} ≤ \frac{n}{2}.

Genom att upprepa detta argument fås

\frac{n}{k} · \frac{n}{k} ⋯ \frac{n}{k} ≤ \frac{n}{k} · \frac{n − 1}{k − 1} ⋯ \frac{n − k + 1}{1} ≤ \frac{n}{2} · \frac{n}{2} ⋯ \frac{n}{2},

vilket etablerar

(\frac{n}{k})^{k} ≤ \binom{n}{k} ≤ (\frac{n}{2})^{k}, (2 < k ≤ n). (6)

Man kan uppnå en något bättre övre gräns:

(\frac{n}{k})^{k} ≤ \binom{n}{k} ≤ (\frac{en}{k})^{k}, (1 ≤ k ≤ n), (7)

där e ≈ 22/7 är den naturliga logaritmens bas. Detta kräver ett lite längre argument.

Påstående 21. \binom{n}{k} < (\frac{en}{k})^{k}.

Bevis. För alla t ∈ R, t ≠ 0 gäller 1 + t < e^{t}. Detta inses antingen genom derivation eller genom att betrakta exponentialfunktionens Taylorutveckling. Från Binomialsatsen 4 får vi

e^{nt} = (e^{t})^{n} > (1 + t)^{n} = ∑_{i=0}^{n} \binom{n}{i}t^{i} > \binom{n}{k}t^{k}, 0 ≤ k ≤ n.

Låt t = k/n i ovanstående uttryck. Då fås

e^{k} > \binom{n}{k}(\frac{k}{n})^{k},

som önskat.

Uppgifter.

1. Låt S = {1, 2, 3, 4}. Lista följande mängder: (a) alla 2-tuppler av element från S (dvs mängden S × S)

(b) alla 2-permutationer av S

(c) alla 2-kombinationer av S.

Skissa svaret på samma fråga med 5-tuppler, -permutationer och -kombinationer.

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

6. Ändlig sannolikhetsteori

Ett (ändligt) utfallsrum är en (ändlig) mängd S av elementarhändelser. Ett sannolikhetsmått är en funktion

p: S → R

som uppfyller följande villkor: 1. 0 ≤ p(s) ≤ 1 för alla s ∈ S

2. ∑_{s∈S} p(s) = 1.

Exempel.

1. Låt T = { · , · · , ··· , ·· ·· , ·· · ·· , ··· ··· } vara utfallsrummet av kast med en tärning. Vi

definierar ett sannolikhetsmått p_{1} på T genom att ange värdet på varje utfall:

p_{1}( · ) = p_{1}( · ·) = ⋯ = p_{1}( ··· ···) = \frac{1}{6} ,

vilket vi kan uppfatta som kast med en symmetrisk tärning. Ett annat sannolikhetsmått är

p_{2}( · ) = p_{2}( · ·) = ⋯ = p_{2}( ·· · ··) = \frac{1}{7} , p_{2}( ··· ···) = \frac{2}{7}

vilket vi kan uppfatta som kast med en tärning som favoriserar ··· ···.

2. Låt T^{2} ange utfallsrummet av kast med två tärningar, T^{2} = { · · , ⋯, …, ··· ··· ··· ··· }.

Vi uppfattar dessa tärningar som olika, dvs att utfallen · · ··· och ··· · · är olika. Ett sannolikhetsmått på T^{2} är

p_{3}(t_{1}t_{2}) = \frac{1}{36} för alla t_{1}t_{2} ∈ T^{2}.

Ett annat mått är p_{4}( · · ) = p_{4}( ⋯) = ⋯ = p_{4}( ··· ··· ··· ···) = \frac{1}{6} , p_{4}(t_{1}t_{2}) = 0 annars.

6.1. Händelser. En händelse är en delmängd E ⊆ S. Sannolikheten av en händelse är

p(E) = ∑_{s∈E} p(s).

Exempel.

1. Händelsen »antal ögon udda« är delmängden U = { · , ··· , ·· · ·· }. Under måttet p_{1}

(symmetrisk tärning) är dess sannolikhet

p_{1}(U) = p_{1}( · ) + p_{1}( ···) + p_{1}( ·· · ··) = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{1}{2} .

Under måttet p_{2} (osymmetrisk tärning) är sannolikheten

p_{2}(U) = p_{2}( · ) + p_{2}( ···) + p_{2}( ·· · ··) = \frac{1}{7} + \frac{1}{7} + \frac{1}{7} = \frac{3}{7} .

2. Om alla elementarhändelser är lika sannolika, dvs

p(s) = \frac{1}{|S|} , för alla s ∈ S,

så fås för godtycklig händelse E ⊆ S

p(E) = ∑_{s∈E} p(s) = ∑_{s∈E} \frac{1}{|S|} = \frac{|E|}{|S|} .

I exemplet ovan är förvisso

p_{1}(U) = \frac{|U|}{|T |} = \frac{|\{ · , ··· , ·· · ·· \}|}{|\{ · , · · , ··· , ·· ·· , ·· · ·· , ··· ··· \}|} = \frac{1}{2} ,

men detta gäller inte för p_{2}.

3. Händelsen »dubblett« D = { · · , …, ··· ··· ··· ··· } ⊆ T^{2} har sannolikheterna p_{3}(D) = 6 · \frac{1}{36} = \frac{1}{6} och p_{4}(D) = 1 under olika sannolikhetsmått.

Påstående 22. Låt E, F ⊆ S vara händelser i ett ändligt utfallsrum. Då gäller

1. p(\overline{E}) = 1 − p(E)

2. p(E ∪ F) = p(E) + p(F) − p(E ∩ F)

Bevis. Vi har enligt definitionen av sannolighetsmåttet

1 = ∑_{s∈S} p(s) = ∑_{s∈E} p(s) + ∑_{s∈\overline{E}} p(s) = p(E) + p(\overline{E}),

vilket ger första påståendet.

För det andra påståendet har vi

p(E ∪ F) = ∑_{s∈E∪F} p(S) = ∑_{s∈E} p(S) + ∑_{s∈F} p(S) − ∑_{s∈E∩F} p(S) = p(E) + p(F) − p(E ∩ F),

som önskat.

6.2. Betingad sannolikhet. Den betingade sannolikheten för E givet F är

p(E | F) = \frac{p(E ∩ F)}{p(F)},

om p(F) > 0 (annars är p(E | F) odefinierad). Händelserna E och F är oberoende om

p(E ∩ F) = p(E)p(F).

Observera att om E och F är oberoende och p(F) > 0, så gäller

p(E | F) = \frac{p(E ∩ F)}{p(F)} = \frac{p(E)p(F)}{p(F)} = p(E).

Exempel.

1. Betrakta utfallsrummet T_{2} och händelserna

A = { · · , ⋯, …, · ··· ··· } och B = { · · , ⋯, …, ··· ··· · },

dvs första (resp andra) tärningen ger · . Observera att händelsen A ∩ B är { · · }.

Vi studerar först måttet p_{3}. Vi har p_{3}(A) = p_{3}(B) = 6 · \frac{1}{36} = \frac{1}{6} , så

p_{3}(A) · p_{3}(B) = \frac{1}{6} · \frac{1}{6} = \frac{1}{36} = p_{3}(A ∩ B),

dvs A och B är oberoende.

Betrakta nu p_{4}. Vi har p_{4}(A) = \frac{1}{6} och p_{4}(B) = \frac{1}{6} men också p_{4}(A ∩ B) = \frac{1}{6} , så A och B är inte oberoende. Observera speciellt at

p_{4}(A | B) = p_{4}(B | A) = 1.

6.3. Slumpvariabler och förväntning. En slumpvariabel är en funktion

X: S → R.

Förväntningen av en slumpvariabel är

E(X) = ∑_{s∈S} p(s)X(s).

Exempel.

1. Definiera

S: T^{2} → R

så att S(t_{1}t_{2}) är antal ögon, t ex S( ··· ·· ··) = 7.

Under sannolikhetsmåttet p_{5} fås

E(S) = \frac{1}{6} S( · · ) + \frac{1}{6} S( ⋯) + ⋯ + \frac{1}{6} S( ··· ··· ··· ···) + 0 · S( ⋯) + ⋯ =

\frac{1}{6} (2 + 4 + 6 + 8 + 10 + 12) = 7,

en summa av 36 termer, varav 30 har koefficient 0.

Under sannolikhetsmåttet p_{3} är förväntningen

E(S) = ∑_{t_{1}t_{2}∈T^{2}} p_{3}(s)S(t_{1}t_{2}) = \frac{1}{36} ((1 + 1) + (1 + 2) + ⋯ + (6 + 6)) = \frac{1}{36} · 282 = 7,

en summa av 36 termer.

Låt U vara ett utfallsrum, p en sannolikhet, och X en slumpvariabel. Slumpvariabler ger upphov till ett nytt utfallsrum där elementarhändelsen är av typen »X(s) = r« för alla r ∈ X(S) och sannolikheten är

p(X(s) = r) = ∑_{s∈S∧X(s)=r} p(s)

Oftast skrivs X = r för X(s) = r.

Påstående 23.

E(X) = ∑_{r∈X(S)} p(X = r)r.

Bevis.

E(X) = ∑_{s∈S} X(s)p(s) = ∑_{r∈X(S)} ∑_{s∈S∧X(s)=r} X(s)p(s) = ∑_{r∈X(S)} ∑_{s∈S∧X(s)=r} rp(s) =

∑_{r∈X(S)} r ∑_{s∈S∧X(s)=r} p(s) = ∑_{r∈X(S)} rp(X = r).

Exempel.

1. För S som i exemplet ovan är utfallsrummet

{S = 2, S = 3, …, S = 12}.

När vi väljer en sannolikhet (för T^{2}) har vi också en sannolikhet för detta rum. T ex för p_{3}:

p_{3}(S = 4) = p_{3}( · ···) + p_{3}( ⋯) + p_{3}( ··· · ) = \frac{3}{36} = \frac{1}{12}

Vi beräknar E(S) med påståendet ovan:

E(S) = 2·p_{3}(S = 2)+3·p_{3}(S = 3)+4·p_{3}(S = 4)+⋯+12·p_{3}(S = 12) = \frac{2}{36} + \frac{3}{18} + \frac{4}{12} +⋯+ \frac{12}{12} = 7,

en summa av bara 11 termer.

Observera att E(S) under p_{4} är även enklare:

E(S) = \frac{2}{6} + \frac{4}{6} + \frac{6}{6} + \frac{8}{6} + \frac{10}{6} + \frac{42}{6} = 7.

Påstående 24. Om X och Y är slumpvariabler på samma utfallsrum, så gäller

1. E(X + Y) = E(X) + E(Y)

2. E(aX + b) = aE(X) + b, där a, b ∈ R.

Exempel. Låt de slumpvariablerna S_{1} och S_{2} ange antal ögon på första och andra tärningen, dvs S_{1}( · ·· · ··) = 1. Betraka sannolikheten p_{4} och observera

E(S_{1}) = E(S_{2}) = \frac{1}{6} (1 + 2 + 3 + 4 + 5 + 6) = \frac{7}{2} .

Vi har med resultatet ovan

E(S) = E(S_{1} + S_{2}) = \frac{14}{2} = 7.

Två slumpvariabler X och Y är oberoende om

p(X = x ∧ Y = y) = p(X = x)p(Y = y), för alla r ∈ R.

Exempel.

1. Betrakta S_{1} och S_{2} under sannolikheten p_{4}. Vi har t ex

p_{4}(S_{1} = 3 ∧ S_{2} = 2) = p_{4}( ··· · ·) = 0,

men också

p_{4}(S_{1} = 3) = p_{4}( ··· ···) = \frac{1}{6} , och p_{4}(S_{2} = 2) = p_{4}( ⋯) = \frac{1}{6} .

så p_{4}(S_{1} = 3)p_{4}(S_{2} = 2) = \frac{1}{36} . Därför är S_{1} och S_{2} inte oberoende under p_{4}.

2. Betrakta nu S_{1} och S_{2} under p_{3}. Vi vill visa oberoendehet, dvs

p_{3}(S_{1} = i ∧ S_{2} = j) = p_{3}(S_{1} = i)p_{3}(S_{2} = j)

för alla reella i, j. Om i, j ∉ {1, 2, 3, ⋯, 6} är sannolikheterna på båda sidorna 0. Annars är

p_{3}(S_{1} = i ∧ S_{2} = j) = \frac{1}{36} ,

eftersom det bara finns en händelse med detta resultat (nämligen där första tärning har i ögon och andra tärning j ögon), och denna händelse inträffar med sannolikhet \frac{1}{36} under p_{3}. Motsvarende är

p_{3}(S_{1} = i) = \frac{1}{36} + \frac{1}{36} + ⋯ + \frac{1}{36} = \frac{1}{6}

eftersom det finns 6 händelser som ger värdet i till S_{1}.

Sats 5. Om X och Y är oberoende slumpvariabler gäller

E(XY) = E(X)E(Y).

Exempel. Vi definierar slumpvariabeln P på T^{2} som produkten av ögonen; P ( ··· ·· · ··) = 15. Betrakta p_{4} och observera

E(P) = \frac{1}{6} (1 · 1 + 2 · 2 + 3 · 3 + 4 · 4 + 5 · 5 + 6 · 6) = \frac{91}{6} .

Detta är inte det samma som

E(S_{1})E(S_{2}) = \frac{7}{2} ⋯ \frac{7}{2} = \frac{49}{4} .

Under p_{3} är S_{1} och S_{2} oberoende, så vi kan skriva

E(P) = E(S_{1}S_{2}) = E(S_{1})E(S_{2}) = \frac{49}{4} ,

vilket kan verifieras – och uppskattas! – genom att beräkna E(P) utifrån definitionen.

6.4. Bernoulliförsök. Betrakta ett experiment med två utfall, det lyckas med sannolikhet p, eller misslyckas med sannolikhet q = 1 − p.

Ett experiment med två utfall, succe och misslyckande kallas ett bernoulliförsök.

Påstående 25. Sannolikheten för att exakt k utav n oberoende bernoulliförsök lyckas är

b(k; n, p) = \binom{n}{k}p^{k}(1 − p)^{n−k}.

Exempel.

1. En (symmetrisk) mynt kastas n gånger. Sannolikheten för exakt k utfall »krona« är b(k; n, \frac{1}{2} ). Det är överraskande hur skarpt detta är koncentrerat kring hälften. För n = 1000 kan man beräkna

b(500; 1000, \frac{1}{2} ) = 0,025225 …

och

b(900; 1000, \frac{1}{2} ) < 0,59 · 10^{−161}.

2. Låt X ange slumpvariabeln som räknar antal lyckade av n bernoulliförsök.

Observera att elementarhändelserna i utfallsrummet nu är resultaten av alla n försök, dvs tuppler med n element där varje element kan vara »lyckades« eller »misslyckades«. Här är några elementarhändelser för n = 3: {(l, l, m), (l, m, l), (m, m, l), … }, och X(l, l, m) = 2.

Förväntningen av X kan beräknas som i exempel [R: 4.5.14]. Alternativt kan X_{i} definieras och beräknas som i exempel [R: 4.5.16]

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

7. Rekursionsekvationer och genererande funktioner (supplement) Det kan visas att om C och D är olika, så gäller

\frac{Ax + B}{(1 − Cx)(1 − Dx)} = \frac{a}{1 − Cx} + \frac{b}{1 − Dx}

för konstanter a och b. Om D, E och F är olika, gäller

\frac{Ax^{2} + Bx + C}{(1 − Dx)(1 − Ex)(1 − F x)} = \frac{a}{1 − Dx} + \frac{b}{1 − Ex} + \frac{c}{1 − F x}

för konstanter a, b och c.

Exempel.

1. Betrakta rekursionsekvationen

a_{0} = 1,
a_{1} = 4,
a_{k} = a_{k−1} + 6a_{k−2}.

Låt G(x) = ∑_{k=0}^{∞} a_{k}x^{k} och observera

xG(x) = ∑_{k=0}^{∞} a_{k}x^{k+1},
6x^{2}G(x) = ∑_{k=0}^{∞} 6a_{k}x^{k+2},

vilket vi behöver i följande beräkning:

G(x) − xG(x) − 6x^{2}G(x) = ∑_{k=0}^{∞} a_{k}x^{k} − ∑_{k=0}^{∞} a_{k}x^{k+1} − ∑_{k=0}^{∞} 6a_{k}x^{k+2} =

a_{0} + (a_{1} − a_{1})x + ∑_{k=2}^{∞}(a_{k} − a_{k−1} − 6a_{k−2})x^{k} = a_{0} + (a_{1} − a_{0})x = 1 + 3x.

Vi får

G(x) = \frac{1 + 3x}{1 − x − 6x^{2}} = \frac{1 + 3x}{(1 − 3x)(1 + 2x)} = \frac{1}{5} ( \frac{6}{1 − 3x} − \frac{1}{1 + 2x} ) =

\frac{1}{5} (∑_{k=0}^{∞} 3^{i}x^{i} − ∑_{k=0}^{∞}(−2)^{k}x^{k}),

varav a_{k} = \frac{6}{5} 3^{k} − \frac{1}{5} (−2)^{k}.

2. I stället för att gissa de rätta funktionerna som xG(x) och 6x^{2}G(x) i exemplet ovan kan man tillämpa följande strategi: (i) Multiplicera båda sidorna i rekursionsekvationen med x^{k}, (ii) summera över alla k där ekvationen är sann, i vårt fall från 2 till ∞. I exemplet fås

a_{k} = a_{k−1} + 6a_{k−2},
a_{k}x^{k} = a_{k−1}x^{k} + 6a_{k−2}x^{k},
∑_{k=2}^{∞} a_{k}x^{k} = ∑_{k=2}^{∞} a_{k−1}x^{k} + ∑_{k=2}^{∞} 6a_{k−2}x^{k}.

7. REKURSIONSEKVATIONER OCH GENERERANDE FUNKTIONER (SUPPLEMENT) 33

Nu gäller det att rekonstruera summor av formen ∑_{k=0}^{∞} a_{k}x^{k} i detta uttryck. Vänsterledet är nästan klart:

∑_{k=2}^{∞} a_{k}x^{k} = ∑_{k=0}^{∞} a_{k}x^{k} − a_{0} − a_{1}x = ∑_{k=0}^{∞} a_{k}x^{k} − 1 − 4x.

Högerledet kräver flera manipulationer,

∑_{k=2}^{∞} a_{k−1}x^{k} + ∑_{k=2}^{∞} 6a_{k−2}x^{k} = x ∑_{k=2}^{∞} a_{k−1}x^{k−1} + 6x^{2} ∑_{k=2}^{∞} a_{k−2}x^{k−2} =

x ∑_{k=1}^{∞} a_{k}x^{k}+6x^{2} ∑_{k=0}^{∞} a_{k}x^{k} = x(∑_{k=0}^{∞} a_{k}x^{k}−a_{0})+6x^{2} ∑_{k=0}^{∞} a_{k}x^{k} = x ∑_{k=0}^{∞} a_{k}x^{k}−6x^{2} ∑_{k=0}^{∞} a_{k}x^{k}−x.

Om vi skriver G(x) för ∑_{k=0}^{∞} a_{k}x^{k} har vi igen

G(x) − 1 − 4x = xG(x) − 6x^{2}G(x) − x

som i exempel 1.

3. Betrakta

a_{0} = 9
a_{k} = 8a_{k−1} + 10^{k−1}, (k ≥ 1).

(Rosens exempel [R:5.4.17] är liknande men hans sekvens börjar i a_{1} i stället, vilket behöver ytterligare ett trick.)

Vi multiplicerar båda sidorna med x^{k} och summerar från 1:

∑_{k=1}^{∞} a_{k}x^{k} = 8 ∑_{k=1}^{∞} a_{k−1}x^{k} + ∑_{k=1}^{∞} 10^{k−1}x^{k}

Sätts G(x) = ∑_{k=0}^{∞} a_{k}x^{k}, blir vänsterledet G(x) − a_{0}, och högerledet blir

8 ∑_{k=0}^{∞} a_{k}x^{k+1} + ∑_{k=0}^{∞} 10^{k}x^{k+1} = 8xG(x) + \frac{x}{1 − 10x}

enligt tabel [R:5.4.1]. Härav fås

G(x) = \frac{9 − 89x}{(1 − 10x)(1 − 8x)} = \frac{1}{2} \frac{1}{1 − 10x} + \frac{17}{2} \frac{1}{1 − 8x} = \frac{1}{2} ∑_{k=0}^{∞} 10^{k}x^{k} + \frac{17}{2} ∑_{k=0}^{∞} 8^{k}x^{k}.

Vi konkluderar att a_{k} = \frac{1}{2} 10^{k} + \frac{17}{2} 8^{k}.

4. Om rekursionsekvationen inte definierar a_{0}, som ju behövs för över huvud taget att kunne skriva ∑_{k=0}^{∞} a_{k}x^{k}, måste man konstruera ett värde för a_{0}. Exempel [R:5.4.17] betraktar

a_{1} = 9
a_{k} = 8a_{k−1} + 10^{k−1}, (k ≥ 2),

vars sekvens börjar som

\begin{matrix}a_{1} & a_{2} & a_{3} & ⋯ \\ 9 & 82 & 756 & ⋯ \end{matrix}

Rosen sätter nu a_{0} = 1. Detta är konsistent med ekvationen, och i princip betraktar han

a_{0} = 1
a_{k} = 8a_{k−1} + 10^{k−1}, (k ≥ 1),

vars sekvens börjar

\begin{matrix}a_{0} & a_{1} & a_{2} & a_{3} & ⋯ \\ 1 & 9 & 82 & 756 & ⋯ \end{matrix}

Alternativet är att betrakta samma sekvens, men upfatta den som börjande i a_{0}:

\begin{matrix}a′_{0} & a′_{1} & a′_{2} & ⋯ \\ 9 & 82 & 756 & ⋯ \end{matrix}

Rekursionsekvationen för denna är

a′_{0} = 9,
a′_{k} = 8a′_{k−1} + 10^{k},

som kan lösas som vanligt. Helt formellt har vi introducerat en ny sekvens a′_{k} där a′_{k} = a_{k−1}.

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

8. Grafer

En (oriktad, enkel) graf är en tuppel G = (V, E) där E ⊆ \binom{V}{2}. Mängden V kallas grafens hörn, mängden E kallas grafens kanter. Ibland skrivs kanten {u, v} som uv eller vu.

En riktad graf är en tuppel G = (V, E) där E ⊆ V^{2}. Mängden V kallas grafens noder, mängden E kallas grafens bågar. Ibland skrivs bågen (u, v) som uv. Observera att uv ≠ uv i motsättning til (oriktade) grafer.

En (oriktad) multigraf är en tuppel G = (V, E) och en funktion

f: E → \binom{V}{2},

dvs grafen har multipla kanter: två kanter e_{1}, e_{2} ∈ E med f(e_{1}) = f(e_{2}). En (oriktad) pseudograf är en multigraf där

f: E → \binom{V}{2} ∪ V,

dvs grafen har multipla kanter och öglor f(e) = {v, v}.

Exempel. Terminologien antyder att vi inte brukar uppfatta en graf som en tuppel av delmängder. Till exempel kan grafen ({1, 2, 3, 4, 5, 6, 7, 8}, {12, 23, 34, 41, 56, 67, 78, 85, 15, 26, 37, 48}) ritas som

[figure: ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; eller; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘]

figuren till vänster motiverar även begreppen »hörn« och »kant«. Observera att det finns många sätt att rita samma graf.

Ibland är hörnens namn vigtiga. Till exempel är G_{1} = ({1, 2, 3}, {12, 23}) och G_{1} = {1, 2, 3}, {13, 23}) inte samma graf, även om både kan ritas som

[figure: ∘; ∘; ∘]

Man kan då ytterligare dekorera sina ritningar med hörnnamn

G_{1} = [figure: ∘; 1; ∘; 2; ∘; 3] G_{2} = [figure: 1; 3; 2]

Bågarna i en riktad graf ritas som pilar. Här är två ritningar av ({1, 2, 3}, (1, 2), (2, 3), (3, 2)}):

[figure: ∘; ∘; ∘; ∘; ∘; ∘]

Om kanten uv finns i grafen kallas u och v för grannar. Hörnen u och v är endpunkter för kanten uv, och kallas incidenta till u och v. Ett hörns grad

deg(w) = |{ w ∈ W | {v, w} ∈ W }|

är dess antal grannar. I en riktad graf definieras ingrad och utgrad som

deg^{−}(v) = |{ w ∈ W | (v, w) ∈ E }|
deg^{+}(v) = |{ w ∈ W | (w, v) ∈ E }|.

Exempel.

1. Betrakta en oriktad graf. För varje hörn, räkna kanterna incidenta till hörnet. Härmed räknas varje kant i grafen exakt två gånger (en gång från varje endpunkt), dvs

∑_{v∈V} deg(v) = 2|E|.

Speciellt är gradsummen jämn. Denna observation kallas handskakningslemmat, och visar att det ved varje fest finns ett jämnt antal handskakningar.

2. Finns det en graf med 5 noder med udda grad? Vi kan indela hörnmängden i V = U ∪ J, hörnen med udda och jämn grad. Vi har

∑_{v∈V} deg(v) = ∑_{v∈U} deg(v) + ∑_{v∈J} deg(v),

dvs att ∑_{v∈J} deg(v) kan skrivas som differensen av två jämna tal och är då själv jämn. Eftersom summen av ett udda antal udda tal är udda måste |J| vara jämn. Konklusionen är att en graf alltid har en jämnt antal noder med udda grad.

En graf (V, E) är en väg om

V = {x_{0}, x_{1}, …, x_{k}}, E = {x_{0}x_{1}, x_{1}x_{2}, …, x_{k−1}x_{k}},

där alla x_{i} är olika. Vägens längd är k, antalet av kanter. Vi låter P_{k} beteckna vägen av längd k. Vi kan ange en väg genom att ange dess hörn i ordning.

Om (V, E) med V = {x_{0}, …, x_{k−1}} och k ≥ 3 är en väg så kallas grafen (V, E ∪ {x_{k}x_{0}}) en cykel av längd k och betecknas C_{k}. Ofta kallas C_{3} även för triangeln och C_{5} pentagonen. En cyklisk graf är en graf som innehåller en cykel.

En graf är en klick om E = \binom{V}{2}; vi låter K_{n} beteckna klicken med n hörn. En graf är oberoende om E = ∅; vi låter I_{n} beteckna n oberoende hörn (‘I’ för independent).

Exempel.

K_{4} = [figure: ∘; ∘; ∘; ∘] = [figure: ∘; ∘; ∘; ∘] P_{3} = ∘  ∘ ∘ ∘  C_{4} = ∘  ∘ ∘ ∘

Om G = (V, E) och G′ = (V′, E′) med V′ ⊆ V och E′ ⊆ E säjer vi att G är en delgraf av G′ och att G′ innehåller G.

En graf är sammanhängande om varje par av noder har en väg mellan sig.

8.1. Träd. En skog är en graf utan cykler, och ett (fritt) träd är en sammanhängande skog.

Påstående 26. En graf G = (V, E) är ett träd om och endast om det finns en unik väg mellan varje par av hörn.

Bevis. Antag G är ett träd och betrakta u, v ∈ V. Eftersom G är sammanhängande finns det en väg från u till v. Antag nu att det finns två väger från u till v, kallad x_{1}, …, x_{k} och y_{1}, … y_{r} (där x_{1} = y_{1} = u och x_{k} = y_{r} = v). Betrakta det minsta i så att x_{i} ≠ y_{i} och de minsta j > i, k > i så att x_{j} = y_{k}. Då är x_{i}x_{i+1} … x_{j}y_{k−1}y_{k−2}y_{i+1} en cykel, i motstrid med att G är ett träd.

Antag nu att G har en unik väk mellan varje par av hörn. Speciellt är G sammanhängande. För att inse att G är utan cykler observera att hörnen på en cykel är förbundna med minst två vägar.

Lemma 4. Ett träd G = (V, E) med |V | > 1 har ett hörn v ∈ V med deg(v) = 1, kallad ett löv.

Bevis. Antag i stället att alla hörn har grad minst 2. Vi vill visa att då måste G innehålla en cykel.

Låt v_{1} vara att hörn i G. Eftersom deg(v_{1}) ≥ 1 har den en granne v_{2} av grad minst 2, som därför själv måste ha en ny granne v_{3} ≠ v_{1}. Vi har konstruerat en väg v_{1}v_{2}v_{3}. Generellt, efter k ≥ 3 steg, har vi konstruerat en väg v_{1}v_{2} ⋯ v_{k}. Eftersom deg(v_{k}) ≥ 2 har v_{k} en granne v_{k+1} ≠ v_{k−1}. Om v_{k+1} ∈ {v_{1}, …, v_{k−1}} har vi hittat en cykel (och är färdiga), annars är v_{1}v_{2} ⋯ v_{k+1} en väg. När k = n kan processen inte fortsätta (vägen innehåller då alla hörn), så vi måste hitta en cykel.

Påstående 27. En graf G = (V, E) är ett träd om och endast om G är sammanhängande och |V | = |E| + 1.

Bevis. (rightarrow) Antag att G är ett träd. Det är klart att G är sammanhängande. Vi användar induktion efter n = |V | till att visa att |V | = |E| + 1. För n = 1 består G av bara ett hörn och inga kanter, så |V | = 1 = 0 + 1 = |E| + 1. Betrakta ett träd med n + 1 hörn. Välg ett löv v med deg(v) = 1, detta finns enligt lemmat ovan. Ta bort v och dess incidenta kant e. Grafen G′ som är kvar är ett träd: den är klart acyklisk (G var acyklisk, och borttagningen av v kan inte skapa en cykel), och den är sammanhängande, eftersom två hörn u, w som var förbundna i G inte kan ha användt v på vägen (v var ett löv). Eftersom G′ är ett träd med n hörn måste den ha n − 1 kanter per induktion, så G har n − 1 + 1 kanter.

(←) Antag att G är en sammanhängande graf med n hörn och n − 1 kanter. Vi vill visa att den är acyklisk. . . ..

Ett m-ärt träd är antingen

1. tomt eller

2. ett hörn (kallad roten) med som är förbunden till roten i d disjunkta m-ära

träd (0 ≤ d ≤ m), kallad underträd. Om d = m i definitionen fås ett fullt m-ärt träd. Fallet m = 2 kallas ibland binärt träd. Varning: I många böcker är binärt träd det samma som fullt binärt träd.

Påstående 28. Ett m-ärt träd är ett träd.

Bevis. Vi vill visa att ett m-ärt träd T (enligt den rekursiva definitionen) är minimalt sammanhängande, vilket etablerar påståendet med Påst. 26. Detta göras ved induktion efter antalet hörn i det m-ära trädet.

Bas: Det tomma trädet är sammanhängande (trivialt) och minimalt.

Steg: (Sammanhang:) Underträden är sammanhängande per induktion, och eftersom roten är kopplad till varje underträd blir T sammanhängande. (Minimalitet:) Ta bort en kant från T. Tas den från något underträd blir detta osammanhängande per induktion. Annars måste kanten ha kopplat ett underträd till roten, så borttagningen gör T osammanhängande.

8.2. Ramseyteori. Vi säger att en graf G = (V, E) innehåller I_{k} om det finns en oberoende k-delmängd U ⊆ V, dvs

{ uv | u ∈ U, v ∈ U } ∩ E = ∅.

(Detta brukar kallas ‘innehåller I_{k} som inducerad delgraf’.)

Låt R(s, t) ange det minsta n så att en graf på n hörn måste innehålla antingen K_{s} eller I_{t}.

Exempel.

1. R(s, 2) = R(2, s) = s för alla s ≥ 2.

2. R(s, t) = R(t, s): Betrakta G = (V, \overline{E}).

3. Vi har redan sett att R(3, 3) = 6, vänskapssatsen.

4. R(3, 4) ≤ 10: Betrakta hörn v. Antag först att v har minst 4 grannar, kalla dem N. Om N innehåller en kant uw, så är uvw en triangel (färdig). Annars är R en oberoende 4-mängd (färdig). Antag nu att v har 6 icke-grannar; kalla dem M. Vi vet att R(3, 3) = 6, så antingen har M en triangel (färdig) eller en oberoende mängd {u, w, x}, som skapar en oberoende 4-mängd med v.

5. R(3, 4) ≤ 9: Vi försöker använda samma argument som ovan. Nu är det möjligt att v har precis 3 grannar och 5 icke-grannar (i alla andra fall kan vi återanvända beviset ovan). Om detta vore sant för alla val av v hade vi ett problem. Men så kan det inte vara pga handskakningslemmat.

6. R(3, 4) = 9: Det kvarstår att etablera existensen av en graf med 8 hörn som varken innehåller K_{3} eller I_{4}:

[figure: ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘]

7. R(4, 4) = 18: Välj v i en graf med 18 hörn. Antag att v har 9 grannar N. Vi vet att R(3, 4) = 9, så N innehåller antingen K_{3} (som ger K_{4} med v) eller I_{4}. Andra fallet är symmetrisk, eftersom R(s, t) = R(t, s): om v har 9 icke-grannar M, så måste M innehålla K_{4} eller I_{3}, som ger I_{4} med v. Vi har visat R(4, 4) ≤ 18.

Läsaren är välkommen att inspicera följande 17-noders graf utan varken K_{4} eller I_{4} för att inse K(4, 4) > 17. Varje nod har 8 grannar, placerat som på ritningen med avstånd 1, 2, 4, 8, 9, 13, 15, och 16 runt cirkeln. Vi ritar grannarna till endast en nod i bilden till vänster, och hela grafen till höger.

[figure: ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘]

Sats 6. Antag s, t ≥ 2. R(s, t) är ändligt, och

R(s, t) ≤ R(s − 1, t) + R(s, t − 1), för s, t > 2.

Bevis. Antag att R(s − 1, t) och R(s, t − 1) är ändliga och låt n = R(s − 1, t) + R(s, t−1). Betrakta en graf med n hörn och låt v vara ett av dessa. Det finns n−1 andra hörn, så antingen har v minst R(s−1, t) grannar eller R(s, t−1) icke-grannar (duvhålsprincipen). I första fall innehåller grannarna antingen K_{s−1} (som skapar K_{s} med v) eller I_{t}, som önskat. I andra fallet innehåller icke-grannarna antingen K_{s} eller I_{t−1} (som skapar I_{t} med v), som önskat.

Påstående 29. För s, t > 2,

R(s, t) ≤ \binom{s + t − 2}{s − 1}.

Bevis. Induktion över s + t. För s = 2 och t = 2 gäller uttrycket (med likhet), se exempel 1. Antag nu att uttrycket gäller för varje s′, t′ med 2 ≤ s′ + t′ ≤ s + t. Teoremet ovan ger

R(s, t) ≤ R(s − 1, t) + R(s, t − 1) ≤ \binom{s + t − 3}{s − 2} + \binom{s + t − 3}{s − 1} = \binom{s + t − 2}{s − 1}.

Av speciellt intresse är de diagonala Ramseytalen R(s) = (s, s). Vi har beräknat R(3, 3) och R(4, 4) i exemplen ovan, och det är anmärkningsvärt, att ingen känner R(5, 5) bättre än 43 ≤ R(5, 5) ≤ 49. Vi ser från resultatet ovan att

R(s) ≤ \binom{2(s − 1)}{s − 1} ≤ \frac{2^{2s−2}}{\sqrt{s}} .

∗LU datavetenskap, dat 401 DM, VT 2002. Thore Husfeldt. 19 september 2002.

9. Slumpgrafer

En p-slumpgraf med n noder är resultatet av följande proces: Börja med en tom graf med n noder. För varje nodpar {u, v}, inkludera kanten uv med sannolikhet p, oberoende av tidigare val. Resultatet av denna process skrivs ofta G(n, p). Ett viktikt specialfall är p = \frac{1}{2}, där varje kant in- eller exkluderas med samma sannolikhet.

Vi låter G_{n} beteckna mängden av grafer med n hörn. Till exempel

G_{4} = { ∘ ∘ ∘ ∘, ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘,

[figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘],

[figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘],
[figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], ∘ ∘ ∘ ∘, [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘],

[figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘],

[figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘], [figure: ∘; ∘; ∘; ∘]}.

Exempel.

1. För p = 0 är resultatet av processen ovan alltid den tomma grafen. Dvs att G(n, 0) är ({1, …, n}, ∅) med sannolikhet 1:

p(G(n, 0) = ({1, …, n}, ∅)) = 1

2. För p = 1 är resultatet av processen ovan alltid den fullständiga grafen.

Betrakta p = \frac{1}{2}. För godtycklig graf G ∈ G_{n} gäller

p(G(n, \frac{1}{2}) = G) = 2^{−n(n−1)/2}

Detta är samma sannolikhet som resultatet av följande process: Välj slumpmässigt en av de 2^{n(n−1)/2} grafer i G_{n}, alla med samma sannolikhet 2^{−n(n−1)}. Ibland är det mera naturligt att betrakta denna konstruktion är definitionen.

Påstående 30. Sannolikheten för att G(n, p) innehåller en k-klick är högst

\binom{n}{k}p^{\binom{k}{2}} = \binom{n}{k}p^{k(k−1)/2}

Bevis. Betrakta en konkret k-delmängd U av V. Denna är en klick precis när alla \binom{k}{2} kanter i U finns, vilket händer med sannolikhet p^{\binom{k}{2}}. Det finns \binom{n}{k} möjliga k-delmängder.

Bevis (lång version). Låt K beteckna händelsen ‘det finns en k-klick i G(n, p)’. Vi vill beräkna p(K). Låt U vara en k-delmängd av V och låt K_{U} beteckna händelsen ‘U är en k-klick’. Observera att K är unionen av K_{U} över alla k-delmängder U, i symboler

K = ⋃_{U} K_{U},

och därför

p(K) = p(⋃_{U} K_{U}) ≤ ∑_{U} p(K_{U}),

där summationen är över alla k-delmängder U av V, total \binom{n}{k} termer.

Det återstår att beräckna p(K_{U}). För att U skal vara en klick måste alla \binom{k}{2} kanter mellan Us hörn finns, vilket händer med sannolikhet

p(K_{U}) = p^{\binom{k}{2}}.

Vi konkluderar

p(K) ≤ ∑_{U} p^{\binom{k}{2}} = \binom{n}{k}p^{\binom{k}{2}},

som önskat.

9.1. Några slumpvariabler. Slumpgrafer är en rik källa för interessanta slumpvariabler.

Antal kanter. Den första är antalet av kanter M. Det är klart att M är minst 0 och högst \binom{n}{2}. Förväntningen är

E[M] = \begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ i=0 \end{matrix} i · p(M = i).

För att beräkna p(M = i) betraktar vi slumpgrafsprocessen som r = \binom{n}{2} Bernoulliförsök, så sannolikheten för precis i kanter är

p(M = i) = \binom{r}{i}p^{i}(1 − p)^{r−i}.

Vi har nu

E[M] = ∑_{i=0}^{r}[i · \binom{r}{i}p^{i}(1 − p)^{r−i}], där r = \binom{n}{2},

som inte omedelbart kan förenklas.

Vi kan däremot begagna förväntningens linearitet (påst. 24) till et mycket enklare argument. Introducera m nya slumpvariabler M_{uv}, en för varje nodpar. M_{uv} skall räkna antalet kanter mellan u och v; det ses lätt att M_{uv} ∈ {0, 1} och att

E[M_{uv}] = 0 · p(M_{uv} = 0) + 1 · p(M_{uv} = 1) = p(M_{uv} = 1) = p.

M_{uv} är ett exempel på en indikatorvariabel (vars värde alltid är 0 eller 1), deras förväntning är alltid precis sannoliketen för utfallet ‘1’, som ofta är lättberäknelig.

Det är också klart att

M = ∑_{u,v∈V} M_{uv},

så

E(M) = ∑_{u,v∈V} E(M_{uv}) = ∑_{u,v∈V} p = p\binom{n}{2}.

Antal triangler. Låt T ange antalet av triangler i grafen. För varje 3-mängd av noder {u, v, w} introduceras indikatorvariabeln T_{uvw} som är 1 när {u, v, w} är en triangel och 0 annars. Sannolikheten för triangeln T_{uvw} är p^{3}. T är summan av alla dessa, så

E(T) = ∑_{\{u,v,w\}∈V} E[T_{uvw}] = ∑_{\{u,v,w\}∈V} p^{3} = \binom{n}{3}p^{3}.

Det är viktikt att observera att variabel T_{uvw} inte är oberoende, men att detta heller inte är nödvändigt för att kunna använda påst. 24. Betrakta till exempel G(4, \frac{1}{2}) med hörn 1, 2, 3 och 4. Sannolikheten för T_{123} är \frac{1}{8}, och det samma gäller för T_{234}. Sannolikheten för T_{123} givet T_{123} är däremot

p(T_{123} | T_{234}) = \frac{1}{4},

så de är inte oberoende.

Slumpmetoden. Slumpmetoden är en bevismetod för att etablera existensen av konstruktioner utan att konstruera dem. Metoden är överraskande enkel. Här är en av dess första tillämpningar, av Erdös (1947):

Sats 7. R(k) > 2^{k/2}.

Bevis. Antag att n ≤ 2^{k/2}. Låt K beteckna händelsen ‘G(n, \frac{1}{2}) innehåller er k-klick’ och låt I beteckna händelsen ‘G(n, \frac{1}{2}) innehåller en oberoende k-mängd’. Vi visade i påst. 30 att

p(K) ≤ \binom{n}{k}2^{−\binom{k}{2}}

På samma sätt kan vi beräkna

p(I) ≤ \binom{n}{k}2^{−\binom{k}{2}}.

Vi har

p(I ∨ K) ≤ 2\binom{n}{k}2^{−\binom{k}{2}}.

Eftersom \binom{n}{k} ≤ n^{k}/2^{k} (se (6) på s. 25), kan vi skriva

p(I ∨ K) ≤ 2\frac{(2^{k/2})^{k}}{2^{k}} 2^{−k(k−1)/2} = 2^{−k/2+1} < 1.

Speciellt,

p(\overline{I} ∧ \overline{K}) = p(\overline{I ∨ K}) = 1 − p(I ∨ K) > 0.

Konklusionen är att sådana grafer finns.

Uppgifter.

1. Givet G ∈ G_{n} med m kanter. Beräckna p(G(n, p) = G).

2. Beräckna det förväntade antal 4-cykler i G(n, p).

3. Beräckna det förväntade antal k-klickar i G(n, p).

APPENDIX A Notation

Notationen i dessa anteckningar är konsistent med [Rosen]. Vill man läsa ytterligare litteratur måste man känna till alternativer.

1. Symboler

Symbol  betydelse  alternativ
¬p  negationen av p  \overline{p}
p → q  p medför q  p ⇒ q
p ↔ q  biimplikation mellan p och q p ⇔ q
p ⇔ q p är ekvivalent med q p ≡ q, p = q
{ x | P (x) } mängdkonstruktion  { x: P (x) }
∅  tomma mängden  { }, ∅
A − B  mängddifferens  A \ B
|A|  kardinalitet  #A
P (S)  potensmängd  2^{A}, PA
uv  sammanfogning  u · v, u ∘ v
λ  tomma strängen  Λ, ϵ, 1

Applikationen av funktioner har så många olika notationer att det fortjäner ett eget avsnitt. Här är fyra vanliga sätt att ange den funktionen, som kvadrerer ett tal

x ↦ x^{2},
x ↷ x^{2},
f(x) = x^{2},
y = x^{2},

men inte x → x^{2}.

2. Alternativ svensk terminologi

domän  definitionsmängd
kodomän  målmängd
funktion  avbildning
hörn  nod
kant  båge
klik  fullständig graf
slumpvariabel stokastisk variabel
förväntning  väntevärde