Mächtigkeit einer Menge < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:35 So 22.11.2009 | | Autor: | Suika |
| Aufgabe | Es sei M [mm] \neq \emptyset [/mm] und m die Kardinalität der Menge M. Bestimme die Kardinalität der Menge Q.
Q := [mm] \{ (C,D) \in P(M) \times P(M) | C \cap D = \emptyset \} [/mm] |
Hi,
Durch Probieren komme ich auf die Lösung [mm] 3^m.
[/mm]
Ich wüsste gern wie man die Lösung begründen könnte.
Grüße,
S.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:56 So 22.11.2009 | | Autor: | Marc |
Hallo Suika,
> Es sei M [mm]\neq \emptyset[/mm] und m die Kardinalität der Menge
> M. Bestimme die Kardinalität der Menge Q.
>
> Q := [mm]\{ (C,D) \in P(M) \times P(M) | C \cap D = \emptyset \}[/mm]
>
> Hi,
>
> Durch Probieren komme ich auf die Lösung [mm]3^m.[/mm]
> Ich wüsste gern wie man die Lösung begründen könnte.
Man kann die Paare von Mengen, also die Elemente von $Q$, einfach abzählen:
Zum Beispiel gibt es folgende Anzahl von Paaren $(C,D)$ mit $|C|=k$:
Für die Menge $C$ gibt es ${m [mm] \choose [/mm] k}$ Möglichkeiten, da es so viele k-elementige Teilmengen von $M$ gibt.
Damit $C$ und $D$ disjunkt sind, muss $D$ eine Teilmenge von [mm] $M\setminus [/mm] C$ sein. Nun gilt aber [mm] $|M\setminus [/mm] C|=m-k$, also gibt es [mm] $2^{m-k}$ [/mm] Teilmengen von [mm] $M\setminus [/mm] C$, die man alle für $D$ nehmen kann. Insgesamt gibt es also
[mm] ${m\choose k}*2^{m-k}$
[/mm]
Paare $(C,D)$ mit $|C|=k$.
Nun noch alle Anzahlen für [mm] $k=0,\ldots,m$ [/mm] summieren, Gleichung aufstellen und mit vollständiger Induktion zeigen.
Viele Grüße,
Marc
|
|
|
|
