Hfdst2. Discrete Wiskunde 1BA Theorie

Definitie: partiële orderelatie

Een relatie die reflexief, anti-symmetrisch en transitief is.

Definitie: totale orderelatie

Een orderelatie R ⊂ A² is totaal als voor elke twee verschillende elementen ‘x’ en ‘y’ uit A, het koppel (x,y) of (y,x) tot R behoort.

Definitie: benedengrens

Een benedengrens b ∈ A van verzameling X ⊂ A, is een getal dat kleiner of gelijk is aan alle elementen van X.

Definitie: kleinste element

Het kleinste element van een verzameling is een benedengrens die tot die verzameling behoort.

Axioma van de goede ordening/het well-ordeningsaxioma

Een niet-ledige deelverzameling van een verzameling met een ondergrens, bezit een kleinste element.

Formuleer en Bewijs: principe van het kleinste tegenvoorbeeld.

p19

Formuleer en bewijs: inductieprincipe

p19

Leg uit in eigen woorden: laden/duivenhokprincipe

Veronderstel dat we m objecten willen verdelen over m-1 laden, dan is het onmiddellijk duidelijk dat, indien er meer objecten zijn dan laden, er ten minste 1 lade zal zijn die meer dan 1 object bevat.

Aftelbare verzameling

Een oneindige relatie X is aftelbaar als er een bijectie bestaat van N naar X.

Bewijs: De verzameling van de gehele getallen is aftelbaar

p23

Bewijs: De verzameling van de rationale getallen is aftelbaar

p24

Bewijs: De verzameling van de reële getallen is niet aftelbaar

p24-25

Definitie: Variatie

Een variatie van k elementen uit n elementen is een geordend k-tal van k verschillende elementen gekozen uit een gegeven verzameling van n elementen. (n >= k en k, n ∈ N)

Bewijs: P(n,k) = n(n-1)…(n-(k-1))

p30

Definitie: Permutatie

Een variatie van ‘n’ elementen uit ‘n’ elementen.

Definitie: Combinatie

Een combinatie van k elementen uit n elementen is een deelverzameling met k elementen uit een gegeven verzameling van n elementen. (n >= k en k, n ∈ N)

Bewijs: P(n,k) = C(n,k) * k!

p32

Eigenschap: C(n,k) = …

p33

Eigenschap + bewijs: C(n, k+1) = …

p33

Eigenschap + bewijs: formule van Stifel-Pascal

p33

Definitie: Herhalingsvariatie

Een herhalingsvariatie van k elementen uit n elementen is een geordend k-tal elementen uit een verzameling van n elementen. (n >= k en k, n ∈ N)

Bewijs:

p34

Definitie: Herhalingscombinatie

Een herhalingscombinatie van k elementen uit n elementen is een niet-geordend k-tal elementen, gekozen uit een verzameling van n elementen. (n >= k en k, n ∈ N)

Bewijs:

p35

Formuleer en bewijs: binomiaalstelling

Formuleer en bewijs: veralgemeend inclusie-exclusie principe / zeefprincipe

Definitie: Wanorde

Een permutatie zonder fixelementen (bijectie waarbij geen enkel element beeld is van zichzelf)

Formule wanorde: niet recursief

p40

Formule wanorde: recursief met beginvoorwaarden

d1 = 0, d2 = 1

Bewijs:

p45

Formuleer en bewijs: multinomiaalstelling

p46