Discrete Wiskunde 1 (WB010B)

---

Voorjaarssemester 2009

Nieuw: De resultaten van het tentamen op 8 april 2009 zijn hier te vinden.

Onderwerpen van Discrete Wiskunde 1

• tellen
• deelverzamelingen, partities, permutaties
• recurrentie, voortbrengende functies
• inclusie/exclusie
• grafen
• enumeratie onder groeps actie

Literatuur

Op de webpagina van de auteur is er een lijst met misprints in het boek. Deze lijkt echter betrekking op een andere uitgave van het boek te hebben.

Een aanvulling hierop is de volgende lijst:

• p.27: het derde element in de vierde rij van de driehoek van Pascal moet "3" zijn i.p.v. "1".
• p.36, line 7: "for any x,y in R" moet luiden "for any x,y in X".
• p.55, l.-13 (regel 13 van beneden): "and it vanishes for n > r" heeft nog steeds betrekking op het feit dat r een positief geheel getal is.
• p.58, l.15: "f(1) = 1 = d(1)" moet luiden "f(1) = 0 = d(1)"
• sectie 4.5: De definitie van Catalan getallen wijkt af van de gebruikelijke definitie: Het n-de Catalan getal C_n is het aantal mogelijkheden om bij een som van n+1 getallen haakjes te plaatsen.
  Het getal C_n bij Cameron heet dus in de rest van de literatuur C_n-1.
• p.70, opgave 13: l.-6: "1 < k < n" moet luiden "1 ≤ k < n"
  l.-3: in de machtreeksen F(t) en G(t) ontbreekt de tⁿ
• p.82, proposition 5.3.5: Als de index j van 0 i.p.v. 1 loopt, geldt de formule ook voor n = 0 (met de conventie dat S(0,0) = 1).
• p.82, l.-5: "s(n,k)" moet "S(n,k)" luiden.
• p.85, opgave 6: Als de index k van 0 i.p.v. 1 loopt, geldt de formule ook voor n = 0 (merk op dat b_n = 1).
• p.169, l.13: "or 2m - n - 1" moet "or 2m = n - 1" luiden.
• p.186, opgave 13: in STEP 2 moet de verwijzing naar Section 11.12 luiden (niet 11.11).
• p.252, l.20: in de formule voor Z(S_n) moet er tussen de haakjes "1" i.p.v. "n!" in de teller staan, want de hele som wordt door n! gedeeld.
• p.253, l.2: de laatste term "6s₂s⁴" moet "6s₂s₄" luiden.

• Behandelde stof week 1:
• inductie (2.2)
• dubbel tellen (2.5)
• deelverzamelingen en binomiaalcoefficienten (3.1 t/m 3.3)
• Behandelde stof week 2:
• binomiaalcoefficienten mod p (3.4)
• kiezen van k elementen uit n (3.7)
• permutaties (3.5)
• equivalentierelaties en partities (3.8)
• Bell getallen (3.11)
• lees zelf 3.12 over het voortbrengen van combinatorische objecten
• Behandelde stof week 3:
• recursie en voortbrengende functies (4.1 t/m 4.3)
• Catalan getallen (4.5, let op de definitie!)
• Behandelde stof week 4:
• Exponentiele voortbrengende functies (4.5)
• Principe van inclusie/exclusie (5.1)
• Stirling getallen (5.3, 5.4)
• Behandelde stof week 5:
• definities grafen (11.1)
• Eulersche en Hamiltonsche grafen (11.4, 11.5)
• Behandelde stof week 6:
• bomen en bossen (11.2)
• minimale opspannende bomen (11.3)
• Travelling salesman (11.7)
• Behandelde stof week 7:
• Lemma van Burnside (15.1, 15.2)
• Polya's theorie van aftellen, cykel index (15.3, 15.4)
• Hoofdstelling van de Polya theorie:
  Zij G een groep die op een verzameling X met n objecten werkt en zij Z(G; x₁, x₂, ..., x_n) de cykel index voor deze werking van G. Zij A = (a₁, a₂, ..., a_m) een stelsel van kleuren/labels.
  Dan is de coefficient van Π a_i^d_i in Z(G; Σ_{a ∈ A} a, Σ_{a ∈ A} a², ..., Σ_{a ∈ A} aⁿ) (d.w.z. x_i is vervangen door Σ_{a ∈ A} aⁱ) gelijk aan het aantal banen van G op de kleuringen van X, waarin d_i objecten de kleur a_i hebben.
• Behandelde stof week 8:
• Polya theorie (vervolg, 15.3, 15.4)

Werkcollege

Huiswerkopgaven week 1 (pdf, ps)

Huiswerkopgaven week 2 (pdf, ps)
Magma voorbeelden week 2: magma2.m

Huiswerkopgaven week 3 (pdf, ps)

Huiswerkopgaven week 4 (pdf, ps)

Huiswerkopgaven week 5 (pdf, ps)

Huiswerkopgaven week 6 (pdf, ps)
Merk op: Voor opgaven 4 en 5 van week 6 heb je twee weken de tijd.
Hier is een Magma-bestand met de afstanden tussen 25 Nederlandse steden voor opgave 5.
Magma voorbeelden week 6: magma6.m

Huiswerkopgaven week 7 (pdf, ps)

Het is heel erg aanbevolen, aandacht aan de sommetjes te besteden,
want dit is de beste manier om de stof te herhalen en vertrouwd met de methodes te worden.

Om het gebruik van Magma te vergemakkelijken zullen hier kleine voorbeeldbestanden beschikbaar gesteld worden.

Magma voorbeelden week 2: magma2.m
faculteit, binomiaalcoefficienten, deelverzamelingen, partities (i.h.b. algoritmen 3.12.2, 3.12.3, 3.13.2 in Cameron).

Magma voorbeelden week 6: magma6.m
samenhangscomponenten van een graaf, gretig algoritme, Travelling salesman input

Verder staat hier een zeer nuttige inleiding in het gebruik van Magma (door W. Bosma).

Tentaminering

De resultaten van het tentamen (pdf, ps). op 8 april 2009 zijn hier te vinden.