Teilmengen

07.12.2004, 23:40

Bier

Teilmengen

Also, eine endliche Menge mit n hat ja angeblich $\begin{eqnarray*} 2^n\ Teilmengen \end{eqnarray*}$
Und man kann aber auch sagen sie hat $\begin{eqnarray*} \begin{pmatrix} n \\ 0\ \end{pmatrix} \end{eqnarray*}$ + $\begin{eqnarray*} \begin{pmatrix} n \\ 1\ \end{pmatrix} \end{eqnarray*}$ +...+ $\begin{eqnarray*} \begin{pmatrix} n \\ n\ \end{pmatrix} \end{eqnarray*}$ Teilmengen. Wie kann man aus dem einen das andere zeigen, oder es sich zumindest klar machen?

Bier

08.12.2004, 01:18

murray

Auf diesen Beitrag antworten »

RE: Teilmengen
Es gibt einen Beweis (Vollständige Induktion), der diese Analogie zwischen 2^{n} und Binomialfunktion zeigt! Wie weit bist du denn gekommen?

mfg

08.12.2004, 08:20

Auf diesen Beitrag antworten »

RE: Teilmengen
Kommt ganz drauf an, was du an Kenntnissen voraussetzen darfst. Wenn z.B. die binomische Formel für die Entwicklung von

$\begin{eqnarray*} (a+b)^n \end{eqnarray*}$

dabei ist, dann ist der Nachweis ziemlich kurz... Augenzwinkern

08.12.2004, 14:18

Tobias

Auf diesen Beitrag antworten »

Um sich die Formel mal anschaulich klarzumachen:

Der Binomialkoeffizient $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ ist kombinatorisch interpretiert "die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge".

Hat man eine Menge mit n Elementen, so existieren n! viele n-Tupel über dieser Menge. Also n! Möglichkeiten, die Elemente anzuordnen. Will ich nun nur k <= n Objekte anordnen, so habe ich für das erste Obejkt n Möglichkeiten, für das zweite n-1, etc. Die Gesamtzahl der k-Tupel über der n-elementigen Menge ist somit:

$\begin{eqnarray*} n \cdot (n-1) \cdots (n-k+1) = \frac{n!}{(n-k)!} \end{eqnarray*}$

Nun haben wir aber unterschiedliche Reihenfolgen mitgezählt. Bei Mengen existiert aber keine Reihenfolge der Elemente. Da jedes k-Tupel in k! vielen Anordnungen vorkommt, dividieren wir auch noch durch k!:

$\begin{eqnarray*} \frac{n!}{k!(n-k)!} \end{eqnarray*}$

Das ist genau der Binomialkoeffizient.

Addiere ich nun die Anzahl der 0-elementigen Teilmengen (leere Menge) mit der Anzahl der 1-elementigen Teilmengen [...] mit der Anzahl der n-elementigen Teilmengen, so erhalte ich alle möglichen Teilmengen.

08.12.2004, 14:28

Bier

Auf diesen Beitrag antworten »

RE: Teilmengen

Zitat:

Original von Arthur Dent
Kommt ganz drauf an, was du an Kenntnissen voraussetzen darfst. Wenn z.B. die binomische Formel für die Entwicklung von

$\begin{eqnarray*} (a+b)^n \end{eqnarray*}$

dabei ist, dann ist der Nachweis ziemlich kurz... Augenzwinkern

Ja und wie?

08.12.2004, 14:34

Tobias

Auf diesen Beitrag antworten »

Indem man a und b auf 1 setzt. Augenzwinkern

08.12.2004, 14:54

bier

Auf diesen Beitrag antworten »

Zitat:

Original von Tobias
Indem man a und b auf 1 setzt. Augenzwinkern

dann steht da 2^n
Und wie schlägt man dann wieder die Brücke zum Binomialkoeffizient?

Ich glaub ich steh grad wieder aufm schlauch...

08.12.2004, 14:57

Auf diesen Beitrag antworten »

Die binomische Formel für (a+b)^n lautet

$\begin{eqnarray*} (a+b)^n={n\choose 0}a^nb^0+{n\choose 1}a^{n-1}b^1+{n\choose 2}a^{n-2}b^2+\ldots+{n\choose n-1}a^1b^{n-1}+{n\choose n}a^0b^n \end{eqnarray*}$

a=b=1 ergibt auf der linken Seite 2^n, richtig. Und auf der rechten Seite...

08.12.2004, 21:34

bier

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Die binomische Formel für (a+b)^n lautet

$\begin{eqnarray*} (a+b)^n={n\choose 0}a^nb^0+{n\choose 1}a^{n-1}b^1+{n\choose 2}a^{n-2}b^2+\ldots+{n\choose n-1}a^1b^{n-1}+{n\choose n}a^0b^n \end{eqnarray*}$

a=b=1 ergibt auf der linken Seite 2^n, richtig. Und auf der rechten Seite...

ah echt trickreich. Kann man das auch ohne die binomische Formel anschaulich machen oder ist das der einzige Weg? (Induktion zählt für mich nicht als "anschaulich machen", dafür ist sie mir einfach ein bissel zu suspekt...)

08.12.2004, 21:39

Auf diesen Beitrag antworten »

Es geht auch über vollständige Induktion unter Benutzung von

$\begin{eqnarray*} {n\choose k}={n-1\choose k-1}+{n-1\choose k} \end{eqnarray*}$

(das ist das Bildungsgesetz des PASCALschen Dreiecks) .

Neue Frage »

Antworten »

Teilmengen

Verwandte Themen