Binominalkoeffizient < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:54 Mo 27.10.2008 | | Autor: | Johie |
| Aufgabe | [mm] \lambda [/mm] sei eine Menge mit n [mm] \in \IN [/mm] Elementen. Für k= 0, 1, ..., n sei [mm] \partial_{k} (\lambda) [/mm] = {A [mm] \subset \lambda [/mm] |#A =k} die Menge aller k-elementigen Teilmengen von [mm] \lambda. [/mm]
Zeige, dass die Anzahl der Elemente von [mm] \partial_{k} (\lambda) [/mm] durch den folgenden Binominalkoeffizienten gegeben ist:
[mm] #\partial_{k} (\lambda) [/mm] = [mm] \vektor{n \\ k} [/mm] = [mm] \bruch{n!}{k! * (n-k)!}
[/mm]
Per Def.: 0! = 1 |
Ich bräuchte einen Ansatz, meine Idee wäre die Induktion, allerdings weiß ich nicht, wie ich das machen soll...
Wäre schön, wenn mir jemand helfen könnte.
|
|
| |
|
Aus der Definition von n über k ergibt sich
[mm]{n \choose k}[/mm] = [mm] \bruch{n*(n-1) * ... * (n-k+1)}{k!}
[/mm]
Ein Schritt weiter. Der Zähler wird erweitert...
n * (n-1) * ... * (n-k+1) * (n-k) * ... * 2 * 1
Jetzt muss das was im Zähler "zuviel" ist wieder wegdividiert werden! Daher (n-k)! im Nenner.
Im Zähler steht also n!
Hoffe der Rest ist soweit klar...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:20 Mo 27.10.2008 | | Autor: | statler |
Mahlzeit Johanna!
> [mm]\lambda[/mm] sei eine Menge mit n [mm]\in \IN[/mm] Elementen. Für k= 0,
> 1, ..., n sei [mm]\partial_{k} (\lambda)[/mm] = [mm]\{ A \subset \lambda |#A = k \}[/mm] die Menge aller k-elementigen Teilmengen von
> [mm]\lambda.[/mm]
> Zeige, dass die Anzahl der Elemente von [mm]\partial_{k} (\lambda)[/mm]
> durch den folgenden Binominalkoeffizienten gegeben ist:
> [mm]#\partial_{k} (\lambda)[/mm] = [mm]\vektor{n \\ k}[/mm] = [mm]\bruch{n!}{k! * (n-k)!}[/mm]
Weißt du denn, wie du die k-Tupel mit verschiedenen Elementen aus [mm] \lambda [/mm] zählst? Du hast für die 1. Stelle n Möglichkeiten, für die 2. n-1 usw., für die k-te n-k+1, also insgesamt das Produkt [mm]n*(n-1)* \dotfill *(n-k+1)[/mm]. Das ist aber genau [mm] \bruch{n!}{(n-k)!} [/mm] Jetzt kommt allerdings jede k-elementige Teilmenge mehrmals vor, und zwar genau k!-mal. So viele verschiedene Anordnungen gibt es nämlich.
(Kennst du die Geschichte von dem Schäfer, der abends seine Schafe zählt. Er kann direkt die Köpfe zählen, wenn er die Übersicht hat. Oder er zählt die Beine und teilt durch 4. Du hast hier erstmal die Beine gezählt.)
Also mußt du noch die Anzahl der k-Tupel (Anzahl aller Beine) durch k! (Anzahl der Beine pro Schaf) teilen. Fertig.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:43 Mo 27.10.2008 | | Autor: | luis52 |
Moin Johanna,
1) Zeige, dass die Aussage fuer $n=1$ zutrifft.
2) Nimm an, dass sie fuer $n$ gilt.
3) Betrachte eine Menge [mm] $\lambda$ [/mm] mit $n+1$ Elementen. Sei [mm] $a\in\lambda$.
[/mm]
Wieviel Teilmengen [mm] $\kappa$ [/mm] von [mm] $\lambda$ [/mm] mit [mm] $a\in\kappa$ [/mm] bzw.
[mm] $a\not\in\kappa$ [/mm] gibt es nach Induktionsvoraussetzung?
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:08 Mo 27.10.2008 | | Autor: | Johie |
Also muss ich zunächst zeigen, dass n=0 ist (Induktionsamfang):
Das wäre doch dann folgendes, wenn man das Zählen der k-Tupel berücksichtigt oder versteh ich das falsch?
[mm] \vektor{n \\ 0} [/mm] = [mm] \bruch{n!}{0! * (n-0)!} [/mm] = [mm] \bruch{n!}{1-n!} [/mm] = 1
(da 0! = 1)
Ist der Anfang so richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:14 Mo 27.10.2008 | | Autor: | luis52 |
Nein, du faengst an mit $n=1$ und betrachtest $k=0$ und $k=1$ ...
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:20 Mo 27.10.2008 | | Autor: | Johie |
[mm] \vektor{n \\ 1} [/mm] ?
Ne, habe einen Fehler gemacht... Wenn n=1 ist und k=0, dann müsste es [mm] \vektor{1 \\ 0} [/mm] sein?!
Dann würde da aber doch 1 rauskommen oder nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:16 Mo 27.10.2008 | | Autor: | luis52 |
> [mm]\vektor{n \\ 1}[/mm] ?
>
> Ne, habe einen Fehler gemacht... Wenn n=1 ist und k=0, dann
> müsste es [mm]\vektor{1 \\ 0}[/mm] sein?!
> Dann würde da aber doch 1 rauskommen oder nicht?
Na, das ist doch prima: Es ist [mm] $\emptyset$ [/mm] eine Teilmenge mit $k=0$ Elementen.
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:37 Mo 27.10.2008 | | Autor: | Johie |
Also jetzt habe ich noch mal eine Frage zu [mm] \vektor{1 \\ 0}: [/mm] Ich verstehe nicht ganz, wieso es jetzt eine leere Menge ist... ?
Ich habe das jetzt mit Hilfe eines anderen Beitrages hier im Forum weiter gemacht, wie folgt:
Induktionsschluss:
[mm] \vektor{n \\ k} [/mm] = [mm] \bruch{n!}{k! * (n-k)!}
[/mm]
[mm] \vektor{n \\ k} [/mm] = [mm] \bruch{n * (n-1) * ... * (n-k+1)}{1*2*...*k} [/mm] * [mm] \bruch{(n-k)!}{(n-k)!} [/mm]
= [mm] \bruch{n*(n-1)*(n-2)*...*(n-k+1) * (n-k)!}{k! * (n-k)!} [/mm]
= [mm] \bruch{(n*(n-1)*(n-2)*...*(n-k+1))(1*2*3*...*(n-k-2)*(n-k-1))(n-k)}{k! * (n-k)!}
[/mm]
Ich sehe hier allerdings nicht, wie sich das zu n! zusammensetzt? Oder habe ich das falsch gemacht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:06 Mo 27.10.2008 | | Autor: | luis52 |
> Also jetzt habe ich noch mal eine Frage zu [mm]\vektor{1 \\ 0}:[/mm]
> Ich verstehe nicht ganz, wieso es jetzt eine leere Menge
> ist... ?
Hallo Johie,
du solltest den Induktionsanfang nicht so stiefmuetterlich behandeln.
Die Aufgabe lautet wie folgt:
Zeige, dass jede n-elementige Menge [mm] $\binom{n}{k}$ [/mm] k-elementige
Teilmenge gibt, [mm] $k=0,1,2,\dots,n$.
[/mm]
Induktionsanfang: Jede einelementige Mengen [mm] $A_1$ [/mm] besitzt
[mm] $\binom{1}{0}=1$ [/mm] Teilmengen mit $k=0$ Elementen und [mm] $\binom{1}{1}=1$
[/mm]
Teilmengen mit $k=1$ Elementen. In der Tat, die leere Menge (eine
Teilmenge von [mm] $A_1$) [/mm] hat $k=0$ Elemente und [mm] $A_1$ [/mm] (ebenfalls eine
Teilmenge von [mm] $A_1$) [/mm] hat $k=1$ Elemente. Da es keine weiteren
Teilmengen von [mm] $A_1$ [/mm] gibt, ist der Induktionsanfang erledigt.
Induktionsvoraussetzung: *Jede* Menge [mm] $A_n$ [/mm] mit n Elementen hat
[mm] $\binom{n}{k}$ [/mm] k-elementige Teilmengen [mm] $k=0,1,2,\dots,n$.
[/mm]
Induktionsbehauptung: Eine Menge [mm] $A_{n+1}$ [/mm] mit $n+1$ Elementen hat
[mm] $\binom{n+1}{k}$ [/mm] k-elementige Teilmengen [mm] $k=0,1,2,\dots,n,n+1$. [/mm]
>
> Ich habe das jetzt mit Hilfe eines anderen Beitrages hier
> im Forum weiter gemacht, wie folgt:
> Induktionsschluss:
> [mm]\vektor{n \\ k}[/mm] = [mm]\bruch{n!}{k! * (n-k)!}[/mm]
>
> [mm]\vektor{n \\ k}[/mm] = [mm]\bruch{n * (n-1) * ... * (n-k+1)}{1*2*...*k}[/mm]
> * [mm]\bruch{(n-k)!}{(n-k)!}[/mm]
> = [mm]\bruch{n*(n-1)*(n-2)*...*(n-k+1) * (n-k)!}{k! * (n-k)!}[/mm]
> =
> [mm]\bruch{(n*(n-1)*(n-2)*...*(n-k+1))(1*2*3*...*(n-k-2)*(n-k-1))(n-k)}{k! * (n-k)!}[/mm]
>
> Ich sehe hier allerdings nicht, wie sich das zu n!
> zusammensetzt? Oder habe ich das falsch gemacht?
Tu das nicht! Versuche nicht fremder Leute Gedanken zu recyclen ...
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:39 Mo 27.10.2008 | | Autor: | Johie |
Schade, dabei sah das so schön... Na ja, aber den Induktionsanfang habe ich jetzt zumindest verstanden :)
[mm] \vektor{n+1 \\ k} [/mm]
= [mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
= [mm] \bruch{n!}{(k-1)! * (n-(k-1))!} [/mm] + [mm] \bruch{n!}{k! * (n-k)!}
[/mm]
= [mm] \bruch{n! * (k-1)! * (n- (k-1))! + n! * k! * (n-k)!}{k! * (n-k)! * (k-1)! * (n - (k-1))!}
[/mm]
So, hier habe ich jetzt Probleme, ich denke, dass man das aus- bzw. einklammern muss... Aber bekomme das nicht hin :(
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:41 Mo 27.10.2008 | | Autor: | Johie |
[mm] \vektor{n+1 \\ k} [/mm]
= [mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
= [mm] \bruch{n!}{(k-1)! * (n-(k-1))!} [/mm] + [mm] \bruch{n!}{k! * (n-k)!}
[/mm]
= [mm] \bruch{n! *k}{k! * (n-(k+1))!} [/mm] + [mm] \bruch{n! * (n-k+1)}{k! * (n-(k+1))!}
[/mm]
= [mm] \bruch{n! * (k+n-k+1)}{k! * (n-(k+1))!}
[/mm]
= [mm] \bruch{n! * (n+1)}{k! * (n-(k+1))!}
[/mm]
= [mm] \bruch{(n+1)!}{k! * (n-(k+1))!}
[/mm]
Und jetzt? Jetzt weiß ich nicht mehr weiter... Was mache ich damit denn jetzt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:51 Mo 27.10.2008 | | Autor: | luis52 |
Prima, du hast gezeigt:
$ [mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k-1} [/mm] $ + $ [mm] \vektor{n \\ k} [/mm] $
Nutze das und meinen Hinweis von 13.43 Uhr aus, um die
Induktionsbehauptung zu beweisen.
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:07 Mo 27.10.2008 | | Autor: | Johie |
Mhh, ich weiß ehrlich gesagt, trotzdem nicht, wie ich weiter machen muss, denn ich habe (dachte ich eigentlich) die Induktionsbehauptung aufgegriffen... Ich weiß auch, dass ich sie noch nicht bewiesen habe... Das Problem ist, dass ich gerade nicht weiß, wo ich hinkommen will...
Ich muss doch mit meinem Ende noch weiter arbeiten oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:26 Mo 27.10.2008 | | Autor: | luis52 |
Moin Johie,
du weisst es zwar noch nicht, aber du moechtest die Induktionsbehauptung
beweisen (nicht aufgreifen).
Na dann woll'n wir mal: Wir betrachten eine Menge [mm] $A_{n+1}$ [/mm] mit $n+1$
Elementen. Sei $k$ eine der Zahlen [mm] $0,1,2,\dots,n,n+1$. [/mm] Wir wollen
zeigen, dass [mm] $A_{n+1}$ [/mm] insgesamt [mm] $\binom{n+1}{k}$ [/mm] Teilmengen gibt mit k
Elementen. Ist $k=0$ oder ist $n+1$, so gibt es jeweils
[mm] $\binom{n+1}{0}=\binom{n+1}{n+1}=1$ [/mm] Teilmenge mit k Elementen, naemlich
[mm] $\emptyset$ [/mm] und [mm] $A_{n+1}$. [/mm] Wir koennen also annehmen, dass k eine der
Zahlen [mm] $1,2,\dots,n$ [/mm] ist.
Sei [mm] $x\in A_{n+1}$ [/mm] ein festes, aber beliebiges Element. Die
Menge [mm] $B=A_{n+1}\setminus\{x\}$ [/mm] besitzt $n$ Elemente. Betrachte
alle Teilmengen [mm] $C\subset A_{n+1}$ [/mm] mit k Elementen. Es koennen 2 Faelle
auftreten:
1) [mm] $x\in [/mm] C$. Dann weist $C$ neben x noch $k-1$ weitere Elemente aus B
auf. Nach Induktionsvoraussetzung haben wir [mm] $\binom{n}{k-1}$
[/mm]
Moeglichkeiten, Teilmengen aus B zu bilden mit $k-1$ Elementen.
2) [mm] $x\not\in [/mm] C$. Dann weist C k Elemente auf, die aus B stammen. Nach
Induktionsvoraussetzung haben wir hierfuer [mm] $\binom{n}{k}$ [/mm] Moeglichkeiten.
Mithin weist [mm] $A_{n+1}$ [/mm] insgesamt
[mm] $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$
[/mm]
Teilmengen mit $k$ Elementen auf.
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:37 Mo 27.10.2008 | | Autor: | Johie |
Sorry, aber jetzt weiß ich gerade gar nicht mehr, was ich machen muss, wie geh ich denn da jetzt vor, weil [mm] A_{n+1} [/mm] habe ich da doch gezeigt... Oder nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:42 Mo 27.10.2008 | | Autor: | luis52 |
> Sorry, aber jetzt weiß ich gerade gar nicht mehr, was ich
> machen muss,
Gar nichts mehr. Der Beweis ist erbracht.
vg uis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:07 Mo 27.10.2008 | | Autor: | Johie |
Es tut mir Leid, aber wahrscheinlich habe ich gerade ein riesen Brett vor dem Kopf... Ich verstehe das gerade nicht richtig, da du um 18:51 noch geschrieben hast, dass ich anhand der Gleichung und dem früheren Beitrag, dass jetzt noch beweisen muss...
Oder ist das durch die beiden Fälle [mm] x\in [/mm] C und [mm] x\not\in [/mm] C bewiesen und die daraus zusammen gesetzte Gleichung, die ich im vorigen bewiesen habe?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:34 Mo 27.10.2008 | | Autor: | luis52 |
> Oder ist das durch die beiden Fälle [mm]x\in[/mm] C und [mm]x\not\in[/mm] C
> bewiesen und die daraus zusammen gesetzte Gleichung, die
> ich im vorigen bewiesen habe?
So ist es.
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:24 Di 28.10.2008 | | Autor: | Johie |
Ich habe noch mal ein Frage, habe mir das ganze nun noch mal angeschaut und bin es Schritt für Schritt durchgegangen, aber ich weiß jetzt nicht genau, wo das B = [mm] A_{n+1} [/mm] / {x} herkommt? Das ist ja eigentlich nur noch mal eine Menge mit den Eigenschaften, die wir vorher bewiesen haben oder nicht (weiß nicht, ob das so richtig ausgedrückt ist)?Und das C ist, denke ich mal, eine gewählte Teilmenge aus [mm] A_{n+1}, [/mm] da wir uns auf alle Teilmengen beziehen müssen oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:23 Di 28.10.2008 | | Autor: | luis52 |
> ich weiß jetzt nicht genau, wo das B =
> [mm] $A_{n+1}\setminus\{x\}$ [/mm] herkommt? Das ist ja eigentlich nur noch mal
> eine Menge mit den Eigenschaften, die wir vorher bewiesen
> haben oder nicht (weiß nicht, ob das so richtig ausgedrückt
> ist)?
Ja, so eine Menge brauche ich, damit ich die Induktionsvoraussetzung (IV)
ausnutzen kann.
> Und das C ist, denke ich mal, eine gewählte Teilmenge
> aus [mm]A_{n+1},[/mm] da wir uns auf alle Teilmengen beziehen müssen
> oder?
Das C ist eine der Teilmengen mit $k$ Elementen, wobei behauptet wird,
dass es davon [mm] $\binom{n+1}{k}$ [/mm] gibt. Ich zaehle also, wieviele Mengen C
es gibt mit [mm] $x\in [/mm] C$ (nach IV [mm] $\binom{n}{k-1}$) [/mm] und wieviele Mengen C
es gibt mit [mm] $x\not \in [/mm] C$ (nach IV [mm] $\binom{n}{k}$).
[/mm]
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:35 Mi 29.10.2008 | | Autor: | Johie |
Ich habe hier noch mal eine Frage zum Formalen. Frage mich nämlich gerade, wie ich das am besten aufschreibe, wenn man zeigen will:
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
Meine Abfolge (18:41) finde ich nämlich nicht so gelungen... Ich würde das wohl so in meine Aufgabe schreiben:
Zu zeigen: [mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
Und anfangen werde ich dann mit:
[mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k} [/mm] = ... = [mm] \vektor{n+1 \\ k}
[/mm]
Kann man das so machen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:43 Mi 29.10.2008 | | Autor: | M.Rex |
Hallo
Das kann man so machen. Das ist generell der bessere Weg, eine (Un)Gleichungskette zu erstellen, als irgendwelche Äquivalenzumformungen zu machen.
Denn Gleichungsumformungen sind meistens leichter nachzuvollziehen.
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:11 Mi 29.10.2008 | | Autor: | Johie |
Danke für die schnelle Antwort, dann denke ich, dass ich die Aufgabe soweit erstmal verstanden habe :)
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
Bis hierher okay!
![[notok]](/images/smileys/notok.gif "[notok]"){kind=small}
Betrachte Dir beide Brüche genau. Der Hauptnenner dieser beiden lautet:
