| Autor |
Beitrag |
    
Michael (Maw)
| | Veröffentlicht am Donnerstag, den 16. November, 2000 - 18:56: | 
|
Moin erstmal
Seien A,B endliche Mengen.
(a)Beweise die Rechenregel #(AxB)=#A*#B
(b)Sei #A=n,neNund sei M als Teilmenge von POT(A)xPOT(A)definiert durch
M:={(X,Y)|X,YTeilmenge vonA mit XUY=Ø}
Zeige:#M=3n
e ist das Zeichen für Element
U ist das Zeichen für Vereinigungsmenge(gibt es hier nicht oder???)
so das war die Aufgabe wäre nett wenn mir jemand helfen könnte.
Vielen Dank
|
Michael (Maw)
| | Veröffentlicht am Freitag, den 17. November, 2000 - 15:37: |
|
so sorry erstmal bei U handelt es sich um die Schnittmenge von X und Y und die ist die leere Menge.
Danke für die hilfe
|
Zaph (Zaph)
| | Veröffentlicht am Sonntag, den 19. November, 2000 - 12:51: |
|
Hi Michael, zunächst einmal: das Blinken nervt ziemlich! Hier trotzdem die Lösung.
Für 0 <= k <= n gibt es (n über k) Teilmengen X von A mit k Elementen. Für jedes dieser X gibt es 2n-k Teilmengen Y von A mit X n Y = Ø. (n = Schnittmenge).
Also
#M = Sn k=0 #{(X,Y) | #X = k und X n Y = Ø}
= Sn k=0 S X: #X = k #{Y | X n Y = Ø}
= Sn k=0 S X: #X = k 2n-k
= Sn k=0 (n über k) 2n-k
= Sn k=0 (n über k) 2n-k 1k
= (2 + 1)n (Binomischer Leersatz)
= 3n
Andere Begründung:
Jedes Element x von A kann entweder in X enthalten sein, es kann in Y liegen oder weder in X noch in Y liegen. Für jedes x gibt es also 3 Möglichkeiten. Da A n Elemente hat, gibt es also 3n Möglichkeiten für Teilmengen X und Y von A mit X n Y = Ø. |
|
