Teilmengen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a) Zeige, dass n/2 die durchschnittliche Zahl der Elemente einer Teilmenge von {1, . . . , n} ist.
b) Zeige, dass
[mm] \sum_{k=0}^{n} [/mm] k [mm] {n \choose k} [/mm] = [mm] n2^{n-1}
[/mm]
mit Hilfe von (a). (Mit anderen Worten, in der Interpretation von (a) ist diese Gleichung
offensichtlich.)
c) Nutze zum Beweis von (b) die Gleichung
k [mm] {n \choose k} [/mm] = n [mm] {n-1 \choose k-1}[/mm]
(Diese sollte natürlich vorher bewiesen sein.) |
Hi erstmal,
hab mich an die Aufgabe ran gesetzt und und kam für a auf folgende Lsg.
a) M sei eine Menge mit n Elementen, P(M) die Potenzmenge von M
Habe als erstes eine bijektive Abbildung gebildet
f : P(M) [mm] \rightarrow [/mm] P(M)
A [mm] \rightarrow M\setminus [/mm] A
So das die bijektiv ist ist schnell zu zeigen.
Dann hab ich mir gedacht ich bilde alle Paare (A ; f(A)), die Vereinigung der Paare haben ja immer die Mächtigkeit n.
Von diesem Paare gibt es [mm] 2^n [/mm] , jedoch reicht es die Hälfte der Paare zu betrachten, da zu jeden (A ; f(A)) ex. (B ; f(B)) mit B = f(A) und f(B)= A, und ich ja jede Teilmenge aus M nur einmal betrachten will.
Also habe ich [mm] 2^{n-1} [/mm] Paare mit n Elementen.
So da die Potenzmenge aber [mm] 2^n [/mm] Elemente hat
Rechne ich [mm] \frac{2^{n-1} * n}{2^n} [/mm] = [mm] \frac{n}{2}
[/mm]
Sollte man doch so machen können oder?
Das Prob was jetzt auftritt ist wie kann ich daraus die Formel für b) herleiten?
c) sollte kein Problem sein
Mfg Yuu
Ich habe diese Frage in keinem Anderem Forum gestellt!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:53 Fr 12.11.2010 | | Autor: | moudi |
> a) Zeige, dass n/2 die durchschnittliche Zahl der Elemente
> einer Teilmenge von {1, . . . , n} ist.
>
> b) Zeige, dass
>
> [mm]\sum_{k=0}^{n}[/mm] k [mm]{n \choose k}[/mm] = [mm]n2^{n-1}[/mm]
>
> mit Hilfe von (a). (Mit anderen Worten, in der
> Interpretation von (a) ist diese Gleichung
> offensichtlich.)
>
> c) Nutze zum Beweis von (b) die Gleichung
>
> k [mm]{n \choose k}[/mm] = n [mm]{n-1 \choose k-1}[/mm]
>
> (Diese sollte natürlich vorher bewiesen sein.)
> Hi erstmal,
> hab mich an die Aufgabe ran gesetzt und und kam für a auf
> folgende Lsg.
>
> a) M sei eine Menge mit n Elementen, P(M) die Potenzmenge
> von M
> Habe als erstes eine bijektive Abbildung gebildet
> f : P(M) [mm]\rightarrow[/mm] P(M)
> A [mm]\rightarrow M\setminus[/mm] A
> So das die bijektiv ist ist schnell zu zeigen.
> Dann hab ich mir gedacht ich bilde alle Paare (A ; f(A)),
> die Vereinigung der Paare haben ja immer die Mächtigkeit
> n.
> Von diesem Paare gibt es [mm]2^n[/mm] , jedoch reicht es die Hälfte
> der Paare zu betrachten, da zu jeden (A ; f(A)) ex. (B ;
> f(B)) mit B = f(A) und f(B)= A, und ich ja jede Teilmenge
> aus M nur einmal betrachten will.
> Also habe ich [mm]2^{n-1}[/mm] Paare mit n Elementen.
> So da die Potenzmenge aber [mm]2^n[/mm] Elemente hat
> Rechne ich [mm]\frac{2^{n-1} * n}{2^n}[/mm] = [mm]\frac{n}{2}[/mm]
>
> Sollte man doch so machen können oder?
Ja ich verstehe das Argument.
>
> Das Prob was jetzt auftritt ist wie kann ich daraus die
> Formel für b) herleiten?
Die Idee ist folgender Zufallsversuch: [mm] $\Omega$ [/mm] ist die Menge aller Teilmengen von {1,2,...,n}. Jede Teilmenge werde mit der gleichen Wahrscheinlich gezogen (also [mm] $2^{-n}$). [/mm] Sei X die Zufallsvariable, die jeder gezogenen Teilmenge die Elementenzahl zu ordnet, also $X(A)=|A|$.
Was ist jetzt der Erwartungswert E(X) von $X$? (Antwort: Die durchschnittliche Elementenzahl einer zufaellig gezogenen Menge.)
Was ist die Wahrscheinlichkeitsverteilung von $X$? (Dazu muss man fuer jeden moeglichen Wert k von X die Wahrscheinlichkeit berechnen, dass X=k ist: P(X=k).)
Der Erwartungswert ist dann [mm] $E(X)=\sum_{k}k\cdot [/mm] P(X=k)$.)
Eineseits weiss man, was E(X) ist (Antwort A), andrerseit kann man die Wahrscheinlichkeiten P(X=k) leicht angeben. Die Formel fuer den Erwartungswert (noch leicht umgestell) ist dann die Formel b).
>
> c) sollte kein Problem sein
>
> Mfg Yuu
>
> Ich habe diese Frage in keinem Anderem Forum gestellt!
>
mfG Moudi
|
|
|
| |
|
Hey,
danke für die Antwort.
Jetzt ist mir klar wie ich es machen soll
mfg Yuu
|
|
|
|
