Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis der Anzahl der k-elementigen Teilmengen

Beweis der Anzahl der k-elementigen Teilmengen

Universität / Fachhochschule

Tags: Induktion, Menge, Teilmenge

Janalp aktiv_icon

13:05 Uhr, 15.10.2017

Hallo zusammen,

ich habe gerade ein Problem, das es gut hier erklärt:

www.onlinemathe.de/forum/Beweis-von-n-ueber-k

Eine Teilmenge hat

(n

über

k)

Möglichkeiten und die andere hat

(n

über

k - 1)

Möglichkeiten. Das ist völlig klar aber ich verstehe nicht, wieso müssen wir am Ende die beiden addieren? Ich sehe es so, dass beide verschiedene Fälle sind und wir können nicht beide Fälle gleichzeitig betrachten.

So wir haben eine Teilmenge

A,

die nicht das neue Element

{c}

enthält und sie ist dann eine Teilmenge von einer Menge, die nur

n

Elemente hat deswegen gibt es per IV

n

über

k

Möglichkeiten.

Dann haben wir den Fall, indem die Teilmenge

A {c}

enthält aber es gibt eine Teilmenge

B

von

A,

die nicht

{c}

enthält und hat dann

n

über

k - 1

Möglichkeiten.

Beide Fälle haben nicht betrachtet, wie das mit dem neuen Element ist. Ich verstehe noch nicht, wieso wir beide Möglichkeiten addieren, wenn sie nichts miteinander zu tun haben.

Wie wäre es, wenn wir der zweite Fall betrachten so:

A = B u {c}

und wir addieren die Möglichkeit für

B

und für das einzelne

{c}

Element?

tobit aktiv_icon

07:21 Uhr, 16.10.2017

Hallo Janalp!

Ich beginne einmal mit einer Analogie:

Wenn ich in der linken Hand 5 Murmeln und in der rechten Hand 3 Murmeln halte, habe ich in beiden Händen zusammen

5 + 3

Murmeln, obwohl "die Murmeln in der linken Hand nichts mit den Murmeln in der rechten Hand zu tun haben".

Zurück zur eigentlichen Frage:

Im eigentlichen Beweis soll die Anzahl der k-elementigen Teilmengen der Menge

M := {1, 2, \dots, n + 1}

ermittelt werden.

Dazu wird die Anzahl der k-elementigen Teilmengen A von M mit

n + 1 \in A

(diese Teilmengen entsprechen den Murmeln in der linken Hand) mit der Anzahl der k-elementigen Teilmengen A von M mit

n + 1 \notin A

(diese Teilmengen entsprechen den Murmeln in der rechten Hand) addiert, um die Anzahl ALLER k-elementigen Teilmengen von M (diese Teilmengen entsprechen den Murmeln in beiden Händen) zu erhalten.

Viele Grüße
Tobias

Bummerang

09:49 Uhr, 18.10.2017

Hallo,

Du hast Deine "alte" Menge

M_{n}

mit den

n

Elementen

{1, 2, ..., n}

um das Element

(n + 1)

erweitert und hast nun eine "neue" Menge

M_{n + 1}

mit den

n + 1

Elementen

{1, 2, ..., n, (n + 1)}

Jetzt entnimmst Du der Menge

M_{n + 1}

eine k-elemntige Teilmenge

A_{k}

. Für diese Teilmenge gibt es zwei Möglichkeiten, die sich gegenseitig ausschließen:

Möglichkeit

1 : A_{k}

enthält

(n + 1)

nicht, also

(n + 1) \notin A_{k}

Möglichkeit

2 : A_{k}

enthält

(n + 1),

also

(n + 1) \in A_{k}

Eine dritte Möglichkeit gibt es offensichtlich nicht.

Wie viele verschiedene Anzahlen von Teilmengen gibt es nun in beiden Möglichkeiten?

Möglichkeit

1 : (n + 1) \notin A_{k}

Das bedeutet doch, dass alle Elemente aus

A_{k}

aus der Menge

M_{n}

zusammengestellt werden, denn sie können nur aus den Zahlen von 1 bis

n

bestehen. Die Anzahl der verschiedenen k-elementigen Teilmengen von

M_{n}

ist aber bekannt nach Ind.-vor. als

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

.

Möglichkeit

2 : (n + 1) \in A_{k}

Jetzt betrachte ich die Menge

B_{k - 1} := A_{k} \ {n + 1}

. Dann ist

B_{k - 1}

eine (k-1)-elementige Teilmenge von

M_{n},

von denen es

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

verschiedene Teilmengen gibt. Jetzt betrachte ich die Abbildung

φ : f (A_{k}) \to B_{k - 1}

mit

B_{k - 1} = A_{k} \ {n + 1}

Offensichtlich ordnet sie jeder Menge

A_{k}

genau eine Menge

B_{k - 1}

zu und umgekehrt ordnet

A_{k} = B_{k - 1} \cup {(n + 1)}

ebenfalls eindeutig allen Teilmengen

B_{k - 1}

genau eine Teilmenge

A_{k}

zu. Demzufolge ist

φ

eine Bijektion. Das bedeutet, dass die Anzahl solcher verschiedenen Mengen

B_{k - 1}

und

A_{k}

gleich ist. Also haben wir genau

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

k-elemntige Teilmengen dem Element

(n + 1)

Da die beiden Möglichkeiten disjunkt sind, eine Menge

A_{k}

kann nur zur einen oder der anderen Möglichkeit gehören, kann man für die Gesamtzahl, beide Anzahlen einfach addieren, also

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

Und das ergibt die Ind.-beh.

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

Janalp aktiv_icon

18:45 Uhr, 19.10.2017

Danke! Jetzt ist es verständlich.

1391342

1390434

	Status: nicht eingeloggt	Noch nicht registriert?