Delmengder

[henrik2706]

Oppgaven bør i og for seg være enkel, og jeg finner svaret ved å ramse opp alle muligheter. Men det må da finnes en enklere måte å finne ut av dette uten å ramse opp alle muligheter?


(a) Hvor mange delmengder har mengden {1, 2, 3, 4}?
(b) Hvor mange delmengder har mengden {1, 2, 3, 4, 5}?

Tusen takk for svar!

[Vektormannen]

Husker du (fra vgs) at antall utvalg av m elementer fra n elementer, når vi ikke bryr oss om rekkefølgen, er gitt ved [tex]{n} \choose {m}[/tex]? Når du skal finne antall delemengder av en mengde så kan du tenke at du først finner hvor mange delmengder som har null elementer (det er bare én), så hvor mange delmengder som har ett element, og så videre. I hvert av tilfellene vil dette være gitt ved [tex]{n} \choose {m}[/tex], der n er antall elementer i mengden og m er hvor mange det er i den etterspurte delmengden.

Det du vil ende opp med da er [tex]{n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n}[/tex]. Er du med på det? Denne summen kan skrives på en annen måte, nemlig som [tex]2^n[/tex] (dette kan du for eksempel bevise ved hjelp av binomialteoremet hvis du lar a = 1 og b = 1.)

(Et sidesprang: Mengden av alle delmengder til en gitt mengde A kalles potensmengden til A og skrives ofte [tex]\mathcal{P}(A)[/tex]. Det vi har her er altså at hvis A er en mengde med n elementer, så er [tex]|\mathcal{P}(A)| = 2^n[/tex]).