Discrete Wiskunde
Samenvatting
Vrije Universiteit Brussel
2025 - 2026
1
,Inhoudsopgave
1 Inleidende begrippen 3
2 Eenvoudige principes van discrete wiskunde 3
3 Gehele getallen 5
4 Inleiding tot de grafentheorie 10
5 Genererende functies 20
6 Recurrentievergelijkingen 21
2
, 1 Inleidende begrippen
Definitie 1. Een functie f : A −→ B heet injectief indien elk element van
B hoogstens één keer voorkomt als tweede component van een koppel in f .
Definitie 2. Een functie f : A −→ B is surjectief indien Im f = B.
Eigenschap 1. De samenstelling van functies is associatief: voor elke drie
functies
f g h
A −→ B −→ C −→ D
geldt
h ◦ (g ◦ f ) = (h ◦ g) ◦ f
Definitie 3. Zij f : A → B een functie. Indien een functie g : B → A
voldoet aan
f ◦ g = 1B en g ◦ f = 1A
dan heet g een invers voor f . We zeggen dan ook dat f inverteerbaar is.
Stelling 1. Enkel bijectieve functies hebben een invers.
Eigenschap 2. Een functie heeft hoogstens één invers.
2 Eenvoudige principes van discrete wiskunde
Stelling 2 (Principe van de duiventil). Als we n identieke objecten verdelen
over k dozen met n > k, dan is er minstens één doos met minstens twee
objecten.
Bekijk de rij 7, 77, 777, 7777, . . . van natuurlijke getallen die enkel het
cijfer 7 bevatten. Is één van die getallen deelbaar door 2013? We gaan
bewijzen dat het antwoord ja is. Sterker zelfs:
Gevolg 1. In de eerste 2013 elementen van bovenstaande rij zit minstens
één veelvoud van 2013.
Definitie 4. Een verzameling A heeft n ∈ N elementen indien er een bijectie
bestaat van [n] naar A. Deze bepaalt een ordening of nummering van A.
Stelling 3. Voor elke eindige verzameling X geldt
|P(X)| = 2|X|
Stelling 4 (Somprincipe). Zijn A1 , A2 , . . . , Ak twee aan twee disjuncte ein-
dige verzamelingen. Dan geldt:
|A1 ∪ A2 ∪ . . . ∪ Ak | = |A1 | + |A2 | + . . . + |Ak |.
3
Samenvatting
Vrije Universiteit Brussel
2025 - 2026
1
,Inhoudsopgave
1 Inleidende begrippen 3
2 Eenvoudige principes van discrete wiskunde 3
3 Gehele getallen 5
4 Inleiding tot de grafentheorie 10
5 Genererende functies 20
6 Recurrentievergelijkingen 21
2
, 1 Inleidende begrippen
Definitie 1. Een functie f : A −→ B heet injectief indien elk element van
B hoogstens één keer voorkomt als tweede component van een koppel in f .
Definitie 2. Een functie f : A −→ B is surjectief indien Im f = B.
Eigenschap 1. De samenstelling van functies is associatief: voor elke drie
functies
f g h
A −→ B −→ C −→ D
geldt
h ◦ (g ◦ f ) = (h ◦ g) ◦ f
Definitie 3. Zij f : A → B een functie. Indien een functie g : B → A
voldoet aan
f ◦ g = 1B en g ◦ f = 1A
dan heet g een invers voor f . We zeggen dan ook dat f inverteerbaar is.
Stelling 1. Enkel bijectieve functies hebben een invers.
Eigenschap 2. Een functie heeft hoogstens één invers.
2 Eenvoudige principes van discrete wiskunde
Stelling 2 (Principe van de duiventil). Als we n identieke objecten verdelen
over k dozen met n > k, dan is er minstens één doos met minstens twee
objecten.
Bekijk de rij 7, 77, 777, 7777, . . . van natuurlijke getallen die enkel het
cijfer 7 bevatten. Is één van die getallen deelbaar door 2013? We gaan
bewijzen dat het antwoord ja is. Sterker zelfs:
Gevolg 1. In de eerste 2013 elementen van bovenstaande rij zit minstens
één veelvoud van 2013.
Definitie 4. Een verzameling A heeft n ∈ N elementen indien er een bijectie
bestaat van [n] naar A. Deze bepaalt een ordening of nummering van A.
Stelling 3. Voor elke eindige verzameling X geldt
|P(X)| = 2|X|
Stelling 4 (Somprincipe). Zijn A1 , A2 , . . . , Ak twee aan twee disjuncte ein-
dige verzamelingen. Dan geldt:
|A1 ∪ A2 ∪ . . . ∪ Ak | = |A1 | + |A2 | + . . . + |Ak |.
3
