| Autor |
Beitrag |
    
sabrina
| | Veröffentlicht am Mittwoch, den 10. Oktober, 2001 - 12:46: | 
|
Hallo Leute,
ich hoffe ihr könnt mir helfen, denn ich steh furchtbar an. Und zwar brauche ich einen Beweis für folgendes Problem:
Sei M eine endliche Menge mit |M|=n dann gilt:
|{(A,B) e P(M) x P(M) | A < B < M}|=3^n
zu meier Schreibweise:
P(M) .. Potenzmenge von M
e ... mein Elementzeichen ;-)
< ... mein Zeichen für Teilmenge A < B --> A ist Teilmenge von B
ich hoffe meine Frage ist so einigermaßen verständlich und ihr könnt mir helfen ...
liebe grüße
sabrina |
Matroid (Matroid)
| | Veröffentlicht am Mittwoch, den 10. Oktober, 2001 - 17:21: |
|
Ok, also Induktion.
Induktionsanfang. Sei n:=|M|=0
M ist die leere Menge und die einzige
Teilmenge von M ist die leere Menge.
=> {(A,B)eP(M)xP(M) | A<B<M} = {({},{}) }
=> |{(A,B)eP(M)xP(M) | A<B<M}| = 1
Und 30 ist auch 1. Der Induktionsanfang stimmt.
Induktionsschritt:
Sei |M|=n+1
Sei a ein beliebiges, aber für die weitere Überlegung fest gewähltes Element aus M.
Die Teilmengen von M kann man nun disjunkt aufteilen, in solche, die a enthalten und solche, die a nicht enthalten.
Und die geordneten Tupel (A,B) kann man nun
unterteilen in:
I) B enthält a und A enthält a
II) B enthält a und A enthält a nicht
III) Weder B noch A enthält a.
Im Fall I betrachte B-{a} und A-{a}.
Das Tupel (A-{a},B-{a}) ist aus der Menge
X := {(A,B)eP(M-{a})xP(M-{a}) | A<B<M-{a}}
M-{a} hat n Elemente, darum kann die Induktionsvoraussetzung angewendet werden.
=> |X| = 3n
Wenn man zu jedem Tupel in X das Element a in beiden Teilmengen hinzufügt, erhält man alle Tupel für M im Fall I.
In ähnlicher Weise muß man die Fälle II und III
auf Tupelmengen von M-{a} zurückführen.
Jedesmal ergibt sich 3n
und insgesamt ist die Summe aller 3 Fälle
3 * 3n = 3n+1.
Weil diese Aufgabe wirklich nicht leicht aufzuschreiben ist, hoffe ich, ich konnte
Dir genug sagen.
Gruß
Matroid |
sabrina
| | Veröffentlicht am Donnerstag, den 11. Oktober, 2001 - 07:50: |
|
hallo matroid
vielen dank für die wirklich schnelle hilfe. ich denke jetzt werde ich die folgeaufgaben vielleicht auch besser verstehen können.
vielen lieben dank
sabrina |
sabrina
| | Veröffentlicht am Donnerstag, den 11. Oktober, 2001 - 09:27: |
|
hallo nochmal,
ich dachte eigentlich schon, dass ich es verstanden habe jedoch tut sich bei mir eine frage auf, die ich mir selbst nicht erklären kann!
nach deiner erklärung matroid gibt es ja noch ein Fall IV mit:
B enthält a nicht und A enthält a
dann kommt zum Schluss jedoch nicht 3*3^n sondern 4*3^n raus
4*3^n ist ungleich 3^(n+1)
vielleicht denke ich da falsch! wäre nett wenn du mich nochmal aufklären würdest!
lg.
sabrina |
maria
| | Veröffentlicht am Donnerstag, den 11. Oktober, 2001 - 12:12: |
|
hallo,
ich versteh auch nicht wie das gehen soll. ich hab mir da mal ein beispiel für M={a}, |M|=1 durchgedacht:
P(M) = {{}, {a}}.
P(M)xP(M) = {({},{}),({},{a}),({a},{}),({a},{a})}
A kann folgende Teilmengen annehmen: A ={} oder A={a}
B kann die gleichen Teilmengen annehmen: B={} oder B={a}
somit ergibt sich Z = {(A,B) e P(M)xP(M) | A < B < M} = {({},{}),({},{a}),({a},{}),({a},{a})}
und |Z| = 4
lt. Formel sollte es aber 3^1 = 3 sein
kann da mal bitte jemand für aufklärung sorgen? bitte!!
lg
maria |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 11. Oktober, 2001 - 12:48: |
|
Aber den Fall
B enthält a nicht und A enthält a
kann es nicht geben, denn A<B<M
Wenn also a nicht in B ist, dann kann es auch nicht in einer Teilmenge von B sein. |
sabrina
| | Veröffentlicht am Donnerstag, den 11. Oktober, 2001 - 13:08: |
|
sorry ich hab da einen totalen aussetzer gehabt. natürlich hast du recht.
danke nochmal
sabrina |
|
