WisFaq!

Aantal deelverzameling van een verzameling

Het aantal deelverzamelingen van W₃={$\omega$₁,$\omega$₂,$\omega$₃}, is gegeven door $\pi$(W₃)=2³=8
Als W_n={$\omega$₁,$\omega$₂,...$\omega$_n} (met n$\geq$1), dan is: $\pi$(W_n)=2ⁿ.

Hoe bewijs je dit?

Mark Schoenaker
7-1-2004

Antwoord

Hoi,

Je maakt een deelverzameling van W_n door voor elk van de n elementen w_i te bepalen of je het wel of niet in die deelverzameling stopt. Het geheel van die n ja/nee-beslissingen bepaalt uniek een deelverzameling. In totaal kan je dus n keer uit 2 mogelijkheden (ja/nee) kiezen. Dit kan op 2ⁿ manieren.

Je kan het ook met inductie formuleren. Stel dat W_n-1 n-1 elementen bevat waarmee er 2^n-1 deelverzamelingen mogelijk zijn. W_n bevat één element meer: w_n. De 2^n-1 deelverzamelingen van W_n-1 zijn ook deelverzamelingen van W_n. Wanneer we aan elk van die deelverzamelingen w_n toevoegen, dan krijgen we nog eens 2^n-1 deelverzamelingen van W_n. In totaal dus 2.2^n-1=2ⁿ deelverzamelingen.

Nog anders kan je ook de deelverzamelingen tellen van 0 elementen, die van 1 element, ... tot aan die van n elementen. In de combinatieleer zien we dat er nCi deelverzamelingen zijn van i elementen. Samengeteld zijn dit er dan ånCi=2ⁿ.

Groetjes,
Johan

andros
7-1-2004