Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Teilmengen

Teilmengen

Universität / Fachhochschule

angewandte lineare Algebra

Tags: Angewandte Lineare Algebra

Goone aktiv_icon

20:42 Uhr, 22.11.2011

Hallo Leute,

habe folgende Aufgabe:

Beweisen Sie, dass für eine nichtleere endlichen Menge die Anzahl der Teilmengen mit gerader Anzahl gleich der Anzahl der Teilmengen mit ungerader Anzahl ist.

Ich wüsste gar nicht, wie ich da konkret beginnen sollte, bräuchte etwas Hilfe.

Danke schonmal.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

20:51 Uhr, 22.11.2011

Hallo,

sei

A

eine

n

-elementige Menge. Wie viele Elemente hat denn dann

P (A)

, die Potenzmenge von

A

?
Kennst du einen Term für die Anzahl aller

k

-elementigen Teilmengen von

A

?
Die beiden zusammen, dann vollständige Induktion!

Für ungeradzahlige

n

geht es natürlich auch einfacher, indem man eine geeignete Bijektion zwischen der Menge aller ungeradzahlig-elementigen Teilmengen und der Menge aller geradzahlig-elementigen Teilmengen angibt.
Bei geradzahligem

n

fällt mir so eine Bijektion jedenfalls nicht sofort ein.

Mfg MIchael

Goone aktiv_icon

21:03 Uhr, 22.11.2011

Also, die Potenzmenge hat eben

2^{| n |}

Elemente.

Einen Term für die Anzahl aller k-elementigen Teilmengen kenne ich nicht, wie sieht der aus?

Ich verstehe aber noch nicht ganz, wie ich das gerade bzw. ungerade mit einfließen lassen kann. Gerade heißt ja ansich, dass eine 2 davor steht oder?

michaL aktiv_icon

21:09 Uhr, 22.11.2011

Hallo,

ja:

∣ A ∣ = n \overset{}{\Rightarrow} ∣ P (A) ∣ = 2^{n}

So, jetzt zu

P_{k} (A) := {X \subseteq A ∣ ∣ X ∣ = k}

.
Wenn

A

n

Elemente hat, auf wie viele unterschiedliche Weisen kann ich denn

k

Elemente daraus "auswählen"?

Ansonsten googlen! (Menge Teilmenge Anzahl) Da findet sich auch eine Skizze für einen Beweis!

> Ich verstehe aber noch nicht ganz, wie ich das gerade bzw. ungerade mit einfließen lassen kann.

Wobei?

Mfg Michael

Goone aktiv_icon

21:25 Uhr, 22.11.2011

Das kommt mir von der Stochastik aus der Schule bekannt vor, nehme an, es gilt

(\begin{matrix} n \\ k \end{matrix})

.

Ich möchte nochmal deine Schreibweise kurz verstehen:

| A | = n \Rightarrow | P (A) | = 2^{n}

Das heißt soviel wie die Kardinalität der Menge A ist die Abbildung von

n

auf

2^{n}

P_{k} (A) := {X \subseteq A | | X | = k}

Und das bezieht sich auf die Teilmengen, sprich, ich setze

z . B

. für

k = 1,

dann weiß ich, dass die Teilmengen von

A,

also

P_{1} (A)

ein Element enthält, sprich

X

enthält ein Element, richtig?

michaL aktiv_icon

21:33 Uhr, 22.11.2011

Hallo,

genau das! Die Anzahl der

k

-elementigen Teilmengen einer

n

-elementigen Menge

A

ist

(\binom{n}{k})

.

Damit müsstest du allgemein beweisen:

\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0

Das ginge mit Induktion. Wie gesagt, für ungerade

n

erhält man dieses Ergebnis auch ohne. Dazu könnte man die Symmetrie

(\binom{n}{k}) = (\binom{n}{n - k})

verwenden.
Alternativ wäre

X \mapsto A \ X

eine Bijektion zwischen der Der Menge aller Teilmengen mit geradzahlig vielen Elementen und der Menge aller Teilmengen mit ungeradzahlig vielen Teilmengen.

∣ A ∣ = n \overset{}{\Rightarrow} ∣ P (A) ∣ = 2^{n}

heißt übrigens nichts anderes, als dass ein

n

-elementigen Menge genau

2^{n}

Teilmengen hat. (Ich weiß nicht, was ich sonst auf deine Frage antworten sollte.)

Bei der zweiten Frage glaube ich mit "ja" antworten zu können.

P_{k} (A)

soll die Menge aller

k

-elementigen Teilmengen sein. Und ja, ist

k = 1

, so sind damit die einelementigen Teilmengen gemeint.

Mfg Michael

Goone aktiv_icon

21:51 Uhr, 22.11.2011

Die

n

über

k

verstehe ich, aber warum

{(- 1)}^{k}

?

Bzw. warum muss das 0 sein?

michaL aktiv_icon

22:02 Uhr, 22.11.2011

Hallo,

ok, scheint zu schwierig zu sein.

Du müsstest beweisen:

(\binom{2 m}{0}) + (\binom{2 m}{2}) + \dots + (\binom{2 m}{2 m}) = (\binom{2 m}{1}) + (\binom{2 m}{3}) + \dots + (\binom{2 m}{2 m - 1})

bzw.

(\binom{2 m + 1}{0}) + (\binom{2 m + 1}{2}) + \dots + (\binom{2 m + 1}{2 m}) = (\binom{2 m + 1}{1}) + (\binom{2 m + 1}{3}) + \dots + (\binom{2 m + 1}{2 m + 1})

Wenn du die beiden auf eine Seite bringst, für

2 m

bzw.

2 m + 1

eben

n

schreibst, dann...

Klar?

Mfg Michael

Goone aktiv_icon

22:15 Uhr, 22.11.2011

Achso, verstehe, die

{(- 1)}^{k}

ensteht dadurch, dass ich die deine Seite durch Subtraktion rüber bringe und deswegen auch gleich 0. Verstehe, danke für deine Hilfe.

Goone aktiv_icon

22:52 Uhr, 22.11.2011

Moment, eine Sache verstehe ich doch noch nicht und zwar, wenn ich eben statt den

2 m

einfach

n

schreibe, dann passt das doch nicht mehr oder?

(\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + ... (\begin{matrix} n \\ n \end{matrix}) = (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) + ... + (\begin{matrix} n \\ n - 1 \end{matrix})

Wenn ich jetzt

z . B

n = 7

nehme, habe ich:

(\begin{matrix} 7 \\ 0 \end{matrix}) + (\begin{matrix} 7 \\ 2 \end{matrix}) + (\begin{matrix} 7 \\ 4 \end{matrix}) + (\begin{matrix} 7 \\ 6 \end{matrix}) = (\begin{matrix} 7 \\ 1 \end{matrix}) + (\begin{matrix} 7 \\ 3 \end{matrix}) + (\begin{matrix} 7 \\ 5 \end{matrix}) + (\begin{matrix} 7 \\ 6 \end{matrix})

Dann wäre bei

(\begin{matrix} n \\ n - 1 \end{matrix})

unten eine 6 und die ist ja gerade. Ich mache da sicherlich wieder was falsch, sehe es aber nicht.

michaL aktiv_icon

22:58 Uhr, 22.11.2011

Hallo,

hm, ich weiß nicht, was da noch unklar ist. Es gibt nur eine einzige Schwierigkeit: ich weiß von

n

nicht, ob es selbst gerade oder ungerade ist. Daher habe ich zwei Varianten aufgeschrieben: eine für ungerade

n

, eine für gerade.

Mach doch ein Beispiel:

n = 5

Zu zeigen:

(\binom{5}{0}) + (\binom{5}{2}) + (\binom{5}{4}) = (\binom{5}{1}) + (\binom{5}{3}) + (\binom{5}{5})

Oder

n = 8

(\binom{8}{0}) + (\binom{8}{2}) + (\binom{8}{4}) + (\binom{8}{6}) + (\binom{8}{8}) = (\binom{8}{1}) + (\binom{8}{3}) + (\binom{8}{5}) + (\binom{8}{7})

Bring alles auf eine Seite. Erkenne, dass der Reihe nach ALLE Binomialkoeffizienten vorkommen, nur eben mit abwechselndem Vorzeichen.
Verzifiziere, dass das durch die Formel

\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0

dargestellt werden kann.

Dann beweise die Formel z.b. per Induktion!

Mfg Michael

Goone aktiv_icon

23:20 Uhr, 22.11.2011

Ich meinte eigentlich nur von der Schreibweise her, aber stimmt, für ein gerades

n

gilt das ganze so:

(\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + ... (\begin{matrix} n \\ n \end{matrix}) = (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) + ... + (\begin{matrix} n \\ n - 1 \end{matrix})

Und für ein ungerades eben:

(\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + ... (\begin{matrix} n \\ n - 1 \end{matrix}) = (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) + ... + (\begin{matrix} n \\ n \end{matrix})

Ging mir nur um die Vorüberlegung, die ich für die Aufgabe reinschreiben möchte.

Aber ok, nun habe ich eben

n = 1

bewiesen.

Für

n + 1

gilt ja dies:

Nochmal die Frage:

\sum_{k = 0}^{n + 1} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) = \sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) + ({(- 1)}^{n + 1} (\begin{matrix} n \\ n + 1 \end{matrix}))

Die Summe ist wieder richtig zerlegt oder?

hagman aktiv_icon

23:42 Uhr, 22.11.2011

Für eine endliche Menge

M

sei

G (M)

die Menge aller gerad-mächtigen Teilmengen von

M

und

U (M)

die der ungeraden.
Ist

m \in M

ein Element und

N := M \ {m},

so ist die Abbildung

G (M) \to P (N), X \mapsto X \ {m}

eine Bijektion (warum?)
Ebenso ist übrigens

G (M) \to P (N), X \mapsto X \ {m}

eine Bijektion.
Es folgt

| G (M) | = | U (M) | = | P (N) | = 2^{| M | - 1}

Alternativ kann man auch (nach Auswahl eines Elementes

m \in M,

was ja geht, wenn

M \neq \emptyset)

direkt eine Bijektion

f : G (M) \to U (M)

angeben, nämlich

X \mapsto (X \ {m}) \cup ({m} \ X)

Goone aktiv_icon

19:40 Uhr, 23.11.2011

Danke für den Hinweis, will aber dennoch mit Induktion beweisen, habe aber ein Problem und zwar habe ich nun:

\sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) + ({(- 1)}^{n + 1} (\begin{matrix} n \\ n + 1 \end{matrix})) = 0

Wenn ich nun die Annahme einsetze, erhalte ich:

0 + ({(- 1)}^{n + 1} (\begin{matrix} n \\ n + 1 \end{matrix})) = 0

{(- 1)}^{n + 1} (\begin{matrix} n \\ n + 1 \end{matrix}) = 0

Das kann aber nicht sein, wo ist mein Fehler?

dapso aktiv_icon

21:22 Uhr, 23.11.2011

Der Fehler ist im Induktionsschritt. Es müsste heißen:

\sum_{k = 0}^{n + 1} (- 1)^{k} (\binom{n + 1}{k})

. Dadurch wird es schwieriger die Vorraussetzung anwenden zu können.
Allerdings kann man die Formel sehr schnell ohne Induktion zeigen und zwar mit dem Binomischen Lehrsatz: