| Autor |
Beitrag |
    
Bernd
| | Veröffentlicht am Freitag, den 05. Oktober, 2001 - 21:46: | 
|
Hallo,
könnte mir bitte jemand bei folgenden Beispielen helfen?
1) Wieviele Teilmengen einer Menge von n Elementen gibt es (die ganze Menge und die leere Meinge mit eingerechnet)?
2) Wieviele 3-elementige Teilmengen einer Menge von n Elementen gibt es?
3) Wieviele k-elementige Teilmengen einer Menge von n Elementen gibt es? Für welches k wird diese Zahl maximal?
Vielen Dank im voraus,
Bernd |
Matroid (Matroid)
| | Veröffentlicht am Freitag, den 05. Oktober, 2001 - 22:23: |
|
Hi Bernd,
hier die 1.
Erstmal muß man eine Formel raten oder vermuten.
Solange ich die Formel für die Anzahl der Teilmengen einer n-elementigen Menge nicht kenne, nenne ich diese Anzahl a(n).
Sei M eine Menge mit n+1 Elementen gegeben. Die Anzahl der Teilmengen ist a(n+1) [noch nicht bekannt aber hat schon einen Namen!].
Ich werde nun eine Rekursionsformel für a(n+1) zeigen, nämlich: a(n+1) = 2*a(n). Das bedeutet dann, daß die Anzahl der Teilmengen einer n+1 elementigen Menge doppelt so groß ist wie bei einer n elementigen Menge.
Das zeige ich so:
Betrachte (im Geiste) alle Teilmengen der Menge (mit n+1 Elementen).
Wähle nun von den n+1 Elementen ein einzelnes aus. Dieses nenne ich a.
Dann gilt:
Man kann die Teilmenge von M aufteilen in solche, die a enthalten und solche die a nicht enthalten.
Die Aufteilung ist disjunkt (d.h. keine Teilmenge wird doppelt vorkommen).
Wieviele Teilmengen von M gibt es, die a enthalten?
Nun, man kann aus allen diesen Teilmengen das a entfernen und erkennt, daß man
genau die Teilmengen einer n-elementigen Menge vor sich hat.
Also, die Anzahl der Teilmengen von M, die a enthalten ist a(n).
Wieviele Teilmengen von M gibt es, die a nicht enthalten?
Das sind auch a(n), denn weil alle diese Teilmengen a nicht enthalten, sind es zugleich
auch die Teilmengen der Mengen M-{a}. M-{a} ist eine Menge mit n Elementen.
Insgesamt:
Die Anzahl der Teilmengen von M ist a(n)+a(n) = 2 * a(n).
Wir wissen jetzt: a(n+1) = 2*a(n)
Außerdem überlege ich mir nun noch, was a(0).
a(0) ist die Anzahl der Teilmengen einer Menge mit 0 Elementen. Eine Menge mit 0 Elementen ist die leere Menge. Die leere Menge hat nur eine einzige Teilmenge, nämlich die leere Menge. Folglich ist a(0) = 1.
Wenn a(0)=1 ist, dann sagt die Rekursionsformel, daß a(1) = 2, a(2) = 4 usw.
Da sieht man dann leicht, daß allgemein a(n) = 2n ist.
Ergebnis: Die Anzahl der Teilmengen einer n elementigen Menge ist 2n.
Ist die Erklärung ausreichend?
Viele Grüße
Matroid |
JPJ (Tyll)
| | Veröffentlicht am Sonntag, den 07. Oktober, 2001 - 01:02: |
|
Gute Antwort Matroid!
Kombinatorischer Ansatz:
Ich habe in M m Elemente, m>=n.
3a) Bildung einer Teilmenge von k<=n Elementen.
Für das erste Element gibt es n Möglichkeiten der Auswahl, für das zweite n-1, u.s.w. für das vorletzte n-k+2 und das letzte n-k+1 Möglichkeiten. Macht insgesamt n*(n-1)*...*(n-k+1) = n!/(n-k)!
Das erste Element kann an k Stellen, das zweite an k-1 Stellen, u.s.w. und das letzte an einer Stelle positioniert werden. Damit ergeben sich k*(k-1)*...*2*1 verschiedene Möglichkeiten, die aber in einer Menge nicht unterschieden werden können. Deswegen müssen diese Möglichkeiten noch rausgerechnet werden, also ist Zahl der Möglichkeiten, eine k elementige Teilmenge einer n elementigen Menge zu bilden
n!/[(n-k)!*k!] = (n über k)
{0!=1 nach Defnition}
2) ist dann der Spezialfall von 3a) mit k=3.
1) ist die Summe von k=0,...,n von n über k.
Fleißiges Rechnen ergibt die Lösung von Matroid.
3b) (n über k) ist maximal <=> n!/[(n-k)!*k!] ist maximal <=> (n-k)!*k! minimal ist.
Angenommen, 2|n. Setze g(n,k)=(n-k)!*k!
Dann gilt f.a. i=0,...,n/2 :
g(n,n/2+i) = (n-n/2-i)!*(n/2+i)! = (n/2-i)!*(n/2+i)! = g(n,n/2-i)
Also ist g(n,k) symmetrisch zu n/2.
Außerdem gilt für alle k=1,...,n-1 :
g(n,k)/g(n,k+1) = [(n-k)!*k!]/[(n-k-1)!*(k+1)!] = (n-k)/(k+1). {Steigung von k zu k+1}
Daraus folgt: g(n,k+1) = g(n,k)*(n-k)/(k+1)
(n-k)/(k+1) ist offenichtlich monoton streng fallend und es gilt {k=n/2-1}:
(n-n/2-1)/(n/2+1) = (n/2+1)/(n/2) > 1
Also ist g(n,k+1) < g(n,k) für alle k=0,...,n/2-1,
folglich ist g(n,k) monoton fallend für k=0,...,n/2-1.
Wegen der Symmetrie von g(n,k) ist dann n/2 Tiefpunkt von g(n,k), also ist (n-k)!*k! in n/2 minimal und somit (n über k) maximal in n/2.
{Das war jetzt eine Kurvendiskussion der anderen Art, weil man Fakultäten so schlecht ableiten kann.}
Ist 2 kein Teiler von n, so gibt es zwei Hochpunkte von (n über k), nämlich die beiden ganzen Zahlen i<n/2 und j>n/2, die am dichtesten an n/2 liegen.
Gruß
Tyll |
|
