Kombinationen von Teilmengen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:16 Sa 30.04.2011 | | Autor: | janisE |
| Aufgabe | Beweisen Sie:
Für [mm]n \geq 1[/mm] gilt: [mm]\#\{(A,B) | A \subseteq B \subseteq \{1,\cdots,n\}\} = 3^n[/mm] |
Hallo!
Die Aufgeabe bereitet mir einiges Kopfzerbrechen. Was ich momentan habe:
Wenn ich eine Menge B mit i Elementen festsetze, gibt es [mm]\sum\limits_{j = 0}^i \binom i j[/mm] Möglichkeiten eine Teilmenge A zu bilden.
Für die Teilmenge A gib es wiederum [mm]\sum\limits_{k = 0}^n \binom n k[/mm] Möglichkeiten. Also gibt es insgesamt [mm]\sum\limits_{k = 0}^n \left( \binom n k \cdot \sum\limits_{i = 0}^k \binom k i \right)[/mm] Möglichkeiten.
Als Tipp haben wir gesagt bekommen, dass wir den binomischen Lehrsatz verwenden sollen. Jedoch finde ich keinen Weg, wie ich mein Ergebnis in die Form des Lehrsatzes, also
[mm]x+y)^n = \binom n0 x^n + \binom n1 x^{n-1} y + \ldots + \binom n{n-1} x y^{n-1} + \binom nn y^n = \sum_{k=0}^n \binom n k x^{n-k} y^{k}[/mm]
bringen soll.
Könnt ihr mir da bitte weiterhelfen?
Danke im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:25 Sa 30.04.2011 | | Autor: | rainerS |
Hallo!
> Beweisen Sie:
>
> Für [mm]n \geq 1[/mm] gilt: [mm]\#\{(A,B) | A \subseteq B \subseteq \{1,\cdots,n\}\} = 3^n[/mm]
>
> Hallo!
>
> Die Aufgeabe bereitet mir einiges Kopfzerbrechen. Was ich
> momentan habe:
>
> Wenn ich eine Menge B mit i Elementen festsetze, gibt es
> [mm]\sum\limits_{j = 0}^i \binom i j[/mm] Möglichkeiten eine
> Teilmenge A zu bilden.
>
> Für die Teilmenge A gib es wiederum [mm]\sum\limits_{k = 0}^n \binom n k[/mm]
> Möglichkeiten. Also gibt es insgesamt [mm]\sum\limits_{k = 0}^n \left( \binom n k \cdot \sum\limits_{i = 0}^k \binom k i \right)[/mm]
> Möglichkeiten.
>
> Als Tipp haben wir gesagt bekommen, dass wir den
> binomischen Lehrsatz verwenden sollen. Jedoch finde ich
> keinen Weg, wie ich mein Ergebnis in die Form des
> Lehrsatzes, also
> [mm]x+y)^n = \binom n0 x^n + \binom n1 x^{n-1} y + \ldots + \binom n{n-1} x y^{n-1} + \binom nn y^n = \sum_{k=0}^n \binom n k x^{n-k} y^{k}[/mm]
>
> bringen soll.
Tipp: [mm] \summe_{i = 0}^k \binom k i \right) = \summe_{i = 0}^k \binom k i \right)1^i*1^{k-i} = 2^k [/mm] .
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:29 Sa 30.04.2011 | | Autor: | janisE |
> Hallo!
>
> > Beweisen Sie:
> >
> > Für [mm]n \geq 1[/mm] gilt: [mm]\#\{(A,B) | A \subseteq B \subseteq \{1,\cdots,n\}\} = 3^n[/mm]
>
> Tipp: [mm]\summe_{i = 0}^k \binom k i \right) = \summe_{i = 0}^k \binom k i \right)1^i*1^{k-i} = 2^k[/mm]
Hallo Rainer,
danke für den Tipp! Mein Problem ist, dass ich nicht weiß, wie ich mit der inneren Summe, die ja von der Äußeren abhängig ist, umgehen soll.
[mm]\sum\limits_{k = 0}^n \left( \binom n k \cdot \sum\limits_{i = 0}^k \binom k i \right) = 2^k * ?[/mm]
Kannst du mir diesbezüglich noch bitte einen Tipp geben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:42 Sa 30.04.2011 | | Autor: | dlns |
Hi,
versuch das doch mal von der anderen Seite aufzurollen und [mm]3^n = (1+2)^n[/mm] zu zerlegen. Danach dann den Satz benutzen.
Viele Grüße
D.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:53 So 01.05.2011 | | Autor: | janisE |
So hat es funktioniert - vielen Dank!!
|
|
|
|
