Bewijs met Venn diagrammen

Beste Wisfaq,

Ik moet het volgende bewijzen:

(n boven r) · (n boven k) = (n boven n-k)· (n boven r-k).

met behulp van het 'Counting Principle' en aan de hand van een figuur.

Gegeven is verder dat n $\in$ $\mathbf{N}$ en r,k$\in\mathbf{N}$₀

Verder is A de set met n elementen, B een subset van A met r elementen en C een subset van B met k elementen.

Allereerst word gevraagd om een venndiagram te maken dat laat zien dat het paar (B,C) uniek is bepaald door het paar (A\C, A\B). Dit lukt me nog wel:

I-----------------------I
I           A           I
I    I--------------I   I
I    I       B      I   I
I    I   I-------I  I   I
I    I   I   C   I  I   I
I    I   I       I  I   I
I    I   I-------I  I   I
I    I              I   I
I    I--------------I   I
I                       I
I-----------------------I 

(in woorden, voor het geval deze figuur niet goed word weergegeven: drie concentrische cirkels, waarbij de binnenste cirkel het C is, de cirkel daaromheen B en de cirkel daar weer omheen A).

Uitgaande van dit Venndiagram heb ik voor (B,C) de gebieden B en C gearceerd en voor (A\C, A\B) alles wat ik niet bij (B,C) gearceerd heb (dus het buitenste omhulsel).

Er volgt dat (B,C) uniek is bepaald door (A\C, A\B) doordat als het aantal elementen in (A\C, A\B) vast staat, automatisch ook het aantal elementen in (B,C) vast staat en dus is (B,C) dan uniek bepaald.

Echter hoe lang ik ook naar deze figuren kijk, ik zie maar niet hoe hetgeen ik moet bewijzen volgt uit deze figuren.

Verder voor het bewijzen met het counting principle:

Ik dacht:

De linker kant (n boven r) telt het aantal manieren waarop je r elementen uit n kunt pakken. Dan telt (r boven k) het aantal manieren waarop je k elementen uit r kunt pakken. De vermenigvuldiging geeft dus als het ware het aantal manieren waarop je k elementen uit n kunt pakken.

De rechterzijde telt het aantal manieren waarop je (n-k) elementen uit n kunt pakken en daarna hoe je uit (n-k) elementen (r-k) elementen kunt pakken. Echter hoe dit gebruikt kan worden bij het bewijs zie ik niet. Ik hoop dat jullie me kunnen helpen.

Vriendelijke groet

Bas

Bas Fr
Student universiteit - woensdag 18 oktober 2006

Antwoord

Om te beginnen: lees je vraag altijd even door voor je hem verstuurd. De formule die je wil bewijzen klopt niet met je uitleg onderaan, na `Ik dacht:'. Uit je uitleg leid ik af dat je het volgende moet bewijzen: (n-boven-r)·(r-boven-k) = (n-boven-n-k)·(n-k-boven-k-r).
Je was er bijna: de linkerkant telt het aantal paren (B,C) deelverzamelingen van A met C$\prod$B, B heeft r elementen en C heeft k elementen (dat is niet hetzelfde als alleen maar k uit n pakken). De rechterkant telt het aantal paren (D,E) met D$\prod$E, E heeft n-k elementen en D heeft r-k elementen.
De twee verzamelingen paren zijn even groot: door middel van (B,C) $\to$ (A-min-C,B-min-C) maak je een een-een-correspondentie.

kphart
vrijdag 20 oktober 2006

©2001-2024 WisFaq