Kombinatorik < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:03 Do 05.05.2005 | | Autor: | squeezer |
Hallo
Ich hab folgende Aufgabe zu bearbeiten:
Gegeben sei eine Menge M und eine Zerlegung:
M = [mm] \bigcup_{j=1}^{n} M_{j} [/mm] von M.
Es sei [mm] m_{j} [/mm] := [mm] |M_{j}|. [/mm] WIe viele Teilmengen von T von M gibt es, die aus jedem [mm] M_{j} [/mm] ein Element (vieleicht aber auch keines) enthalten.
Ich weiss leider nicht genau wie ich die Sachen angehen soll. Ich habe mir 2 3-elementige Beispielmengen ausgesucht aber ich kriegs irgendwie nicht gebacken... Geschweige denn für beliebige Mengen. Zudem weiss ich nicht genau was es mit der Angabe "vieleicht aber auch keines" auf sich hat.
Vielen Dank für eure Hilfe
Marc
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:40 Do 05.05.2005 | | Autor: | Hanno |
Hallo Squeezer!
Soll gemeint sein: man finde die Anzahl aller Teilmengen $T$ von $M$, die für alle [mm] $j\in\IN, 1\leq j\leq [/mm] n$ höchstens ein Element mit [mm] $M_j$ [/mm] gemeinsam haben?
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:04 Do 05.05.2005 | | Autor: | Hanno |
Hallo nochmals!
Wenn [mm] $|T\cap M_j|\leq [/mm] 1, [mm] 1\leq j\leq [/mm] n$ sein soll, dann gibt es genau [mm] $\produkt_{j=1}^{n}|m_j+1|$ [/mm] solcher Teilmengen. Dies kann wie folgt eingesehen werden: du wählst aus jeder der [disjunkten] Mengen [mm] $M_j,1\leq j\leq [/mm] n$ entweder genau eines oder kein Element. Insgesamt hast du also für die Menge [mm] $M_j$ [/mm] genau [mm] $|M_j|+1=m_j+1$ [/mm] Auswahlmöglichkeiten. Dies führt direkt zu obigem Ergebnis. Ein Spezialfall, der sich ja mit der Formel auch behandeln lassen muss (eine Art Kontrolle also), ist [mm] $M:=\{a_1,a_2,...,a_n\}$ [/mm] mit der Partition [mm] $M_j:=\{a_j\}, 1\leq j\leq [/mm] n$. Jede Teilmenge von $M$ beinhaltet entweder ein oder kein Element aus jeder der [mm] $M_j$, [/mm] d.h. jede Teilmenge muss in obiger Zählung mitgezählt worden sein. Da es genau [mm] $2^n$ [/mm] Teilmengen von $M$ gibt, muss demnach auch die gefundene Formel [mm] $2^n$ [/mm] als Ergebnis ausgeben - dies trifft wegen [mm] $m_j=1, 1\leq j\leq [/mm] n$ zu.
Liebe Grüße,
Hanno
|
|
|
|
