Delmängder av mängder, matematik 5.

Hur många delmängder innehåller följande mängder?

{2, 3, 6, 11, 17}

Antar att jag ska köra någon formel från kombinatoriken, men vilken? tycker inte multiplikationsprincipen passar då det är olika storlekar på alla mängder.. (finns ju delmängder med ändast 1 element upp till 5 element).

Tack på förhand!

Det finns en delmängd med noll element också. Men det du ska använda är en sats som säger att om m är antal element i M så är antalet delmängder till M lika med 2^m.

Varför det blir så kan man väl i princip bevisa från binomialkoefficienterna. Låt säga att vi har en mängd med n element, hur många delmängder finns med 0 element? Jo, C(n, 0) = 1 (läses "n stycken, välj 0), detta är tomma mängden. Delmängder med 1 element? På samma sätt C(n, 1) = n och så vidare. Antalet delmängder blir alltså:

C(n, 0) + C(n, 1) + ... + C(n, n) = ∑_{0, n} C(n, k)

För att få detta på sluten form kan vi använda binomialsatsen, vilket ger med ett trick:

∑_{0, n} C(n, k) = ∑_{0, n} C(n, k) 1^(n - k)·1^k = (1 + 1)^n = 2^n

Lärt dig vad fakultet är?
Borde gå väldigt enkelt om du fattat det.

Låt N vara en delmängd till M. Då gäller att för varje element x i M, så antingen tillhör x N, eller så tillhör x inte N. Vi har alltså n = |M| (antalet element i M) val med två möjligheter, så antalet möjliga utfall är enligt multiplikationsprinicpen 2^n.

Okej, alltså finns det 32 delmängder, (2^5=32). Inte sett den varianten på multiplikationsprincipen förut. Ja vet hur man räknar fakultet men inte begripit användningsområden fullt ut än! Tack för snabba svar!