Diskrete Mathe < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:02 Fr 28.04.2006 | | Autor: | Sunny85 |
| Aufgabe | | Prüfe, dass die Anzahl der Teilmengen von [n], das eine ungerade Anzahl an Elementen hat, [mm] 2^{n-1} [/mm] ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Wie kann ich das am besten zeigen? Ich hatte bereits eine ähnliche Aufgabe, da war die bedeingung, dass je zwei Teilmengen von [n] mindestens ein Element gemeinsam haben. Dabei war die Antwort auch [mm] 2^{n-1} [/mm] und es wurde damit argumentiert, dass man für ungerade n alle Teilmengen mit Mächtigkeit [mm] \ge [/mm] n+1/2 auswählt. kann ich diese Option hierbeiauch verwenden?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:43 Fr 28.04.2006 | | Autor: | DirkG |
Dieselbe Anzahl heißt nicht dieselbe Argumentation... 
Wir spalten von unserer Menge [mm] $M_n=\{1,2,\cdots,n\}$ [/mm] einfach mal ein Element ab, d.h. [mm] $M_n=M_{n-1}\cup\{n\}$, [/mm] und betrachten jetzt alle ungeradzahligen Teilmengen $T$ von [mm] $M_n$. [/mm] Da gibt es zwei Fälle:
1.Fall [mm] $n\in [/mm] T$: Dann ist [mm] $T\cap M_{n-1}$ [/mm] eine geradanzahlige Teilmenge von [mm] $M_{n-1}$.
[/mm]
2.Fall [mm] $n\not\in [/mm] T$: Dann ist [mm] $T\cap M_{n-1}=T$ [/mm] eine ungeradanzahlige Teilmenge von [mm] $M_{n-1}$.
[/mm]
Beide Fälle zusammengenommen entspricht dann die Anzahl solcher $T$ genau der Anzahl aller Teilmengen von [mm] $M_{n-1}$, [/mm] und das sind ja [mm] $2^{n-1}$.
[/mm]
|
|
|
|
