Potenzmenge binimialkoeffizient kombinatorik

Question

ich soll die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge B bestimmen und folgern, dass die die Potenzmenge P(B) einer n-elementigen Menge B genau 2^n Elemente hat.

Answer 1

Zum Beweis:

Man kann sich eine binäre Tabelle aufstellen für die Mengen in der Potenzmenge, z.B. wenn die Potenzmenge von M = {1,2,a} gebildet werden soll, kann man sich solch eine Tabelle aufstellen:

1 2 a

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Dabei gibt 1 immer an, dass das Element in der Menge enthalten ist und 0, dass es nicht enthalten ist.

Also wäre

0 0 0 die leere Menge,

0 0 1 wäre { a },

1 1 0 wäre { 1, 2 },

1 1 1 wäre { 1, 2, a } usw.

Insgesamt kommen also alle Mengen vor, die in der Potenzmenge enthalten sind. Dabei gibt es für das erste Element 2 Möglichkeiten, für das zweite Element 2 Möglichkeiten, ... also insgesamt 2^n Möglichkeiten bei n Elementen.

Das musst du nur noch formalisieren.