Binomialkoeefizient < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:16 Fr 20.12.2013 | | Autor: | MaxHBB |
| Aufgabe | | Beweisen Sie, dass der Binomialkoeefizient [mm] \pmat{ n \\ k } [/mm] mit und die Anzahl der k-elementigen Teilmegen einer n-elementigen Menge ist. |
Ist der Beweis korrekt?
Vollständige Induktion über n.
Induktionsanfang:
für
Dies ist wahr, da eine einelementige Menge genau eine einelementige Teilmenge hat.
Induktionsschritt:
Iv.: Die Aussage gelte für .
Zu zeigen: Dann gilt sie auch für .
[mm] \vektor{n + 1 \\ k} [/mm] = [mm] \bruch{(n+1)!}{k!(n+1-k)!} [/mm] = [mm] \bruch{n!}{k!(n-k)!} \bruch{n+1}{n+1-k} [/mm] = [mm] \bruch{n!}{k!(n-k)!} [/mm] + [mm] \bruch{n!}{(k-1)!(n-k+1)!}
[/mm]
Nach der Iv. ist der letzte Summand die Anzahl der neuen Permutationen.
Die Umformung folgt mit
.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:36 Sa 21.12.2013 | | Autor: | Sax |
Hi,
der Beweis ist im Prinzip korrekt, zwar sehr kompliziert aber dafür selbst gemacht.
Jedoch :
Die Struktur ist ein wenig undurchsichtig. Bei manchen Gleichheitszeichen weiß man nicht sofort, weshalb sie gültig sind.
Der Beweis enthält viel zu wenig Text. Insbesondere
> Nach der Iv. ist der letzte Summand die Anzahl der neuen
> Permutationen.
muss genauer begründet werden. (Außerdem heißt es "Teilmengen", nicht "Permutationen".)
Im letzten Teil sind zwei Schreibfehler bzgl des Fakultätszeichens (eins zu viel, eins zu wenig).
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:44 Sa 21.12.2013 | | Autor: | MaxHBB |
Danke für die schnelle Rückmeldung, die Fehler im letzten Teil habe ich gefunden! Ja, ich muss mir endlich mal angewöhnen, etwas mehr Text zu schreiben bei meinen Beweisen ;).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:54 Sa 21.12.2013 | | Autor: | Teufel |
Hi!
Ich würde auch noch die Fälle für $k=0$ oder $n=0$ in den Induktionsanfang aufnehmen. Aber das ist ja auch schnell begründet, warum es da auch gilt.
Ansonsten ist es gut so!
|
|
|
| |
|
> Beweisen Sie, dass der Binomialkoeefizient [mm]\pmat{ n \\ k }[/mm]
> mit und die Anzahl der k-elementigen
> Teilmegen einer n-elementigen Menge ist.
> Ist der Beweis korrekt?
>
> Vollständige Induktion über n.
>
> Induktionsanfang:
>
>
>
> für
>
> Dies ist wahr, da eine einelementige Menge genau eine
> einelementige Teilmenge hat.
>
> Induktionsschritt:
>
> Iv.: Die Aussage gelte für .
> Zu zeigen: Dann gilt sie auch für .
>
> [mm]\vektor{n + 1 \\ k}[/mm] = [mm]\bruch{(n+1)!}{k!(n+1-k)!}[/mm] =
> [mm]\bruch{n!}{k!(n-k)!} \bruch{n+1}{n+1-k}[/mm] =
> [mm]\bruch{n!}{k!(n-k)!}[/mm] + [mm]\bruch{n!}{(k-1)!(n-k+1)!}[/mm]
> Nach der Iv. ist der letzte Summand die Anzahl der neuen
> Permutationen.
>
> Die Umformung folgt mit
>
> .
Hallo Max,
du gibst hier als "Beweis" ziemlich komplexe Rechnungen
mit Fakultäten an.
So wie ich die Aufgabenstellung verstehe, ist dies aber
möglicherweise gar nicht gefragt.
Zuallererst müsste ich aber zur Aufgabenstellung selbst
noch eine Frage stellen. Da steht:
Beweisen Sie, dass der Binomialkoeffizient [mm]\pmat{ n \\ k }[/mm]
mit und die Anzahl der k-elementigen
Teilmegen einer n-elementigen Menge ist.
Nur wenn man zusätzlich noch wüsste, auf welche
Definition des Begriffes "Binomialkoeffizient" man sich
dabei stützen soll, ist die Aufgabe klar gestellt. Damit
auch klar wird, was ich damit sagen will, gebe ich drei
mögliche Definitionen an:
(1) [mm] $\pmat{ n \\ k }\ [/mm] :=\ $ Anzahl der k-elementigen Teilmengen einer
n-elementigen Menge (siehe ![[]](/images/popup.gif) Wikibooks)
(2) [mm] $\pmat{ n \\ k }\ [/mm] :=$ Koeffizient von [mm] x^k [/mm] im Polynom [mm] (1+x)^n [/mm]
(3) [mm] $\pmat{ n \\ k }\ [/mm] :=\ \ [mm] \frac{n\,!}{k\,!\ (n-k)\,!}$
[/mm]
Stützt man sich auf Definition (1.) , so ist gar nichts
weiter zu beweisen.
Stützt man sich auf (2.), muss man sich etwas näher
mit dem Ausmultiplizieren des Terms [mm] (1+x)^n [/mm] auseinander-
setzen und zeigen, wie man da eine gewisse Menge aus
n Elementen sowie ihre Teilmengen ins Spiel bringen kann.
Erst wenn man von Definition (3) ausgeht, bekommt man
es überhaupt mit Fakultäten zu tun. Ich denke aber, dass
auch dieser Beweis nicht nur aus einer Rechnerei besteht.
Insbesondere müssten darin Überlegungen wie diese eine
zentrale Rolle spielen: Wenn wir wissen, wieviele
k-elementige Teilmengen eine gegebene Menge mit insge-
samt n Elementen hat, wie kommen wir von dieser Anzahl
zur Anzahl der k-elementigen Teilmengen einer Menge
mit (n+1) Elementen ?
Zu deinem Beweis:
Du schreibst an einer Stelle:
> Nach der Iv. ist der letzte Summand die Anzahl der
> neuen Permutationen Teilmengen.
Ich finde, dass genau an dieser Stelle eine ganz
wichtige Überlegung, nämlich genau die "Brücke" von
den Fakultätenrechnungen zur inhaltlichen Bedeutung
bei den Mengen und Teilmengen, fehlt. Es genügt nicht,
einfach auf die "neuen Teilmengen" hinzuweisen,
sondern es wäre zu zeigen, wie man diese Teilmengen
etwa in einem geeigneten Modell darstellen und ihre
Anzahl beschreiben kann.
Und noch eine letzte Bemerkung: Die Werte von
n und k sollten wohl nicht auf positive Werte beschränkt
werden. Sowohl n=0 als auch k=0 machen durchaus
ebenfalls Sinn. Gerade in solchen Zusammenhängen
finde ich es schlimm, dass heutzutage offenbar bei
der Verwendung des Symbols [mm] \IN [/mm] ein Chaos existiert:
Für manche gehört die Null dazu, für andere nicht.
In einem zentralen Gebiet der Mathematik ist dieser
Zustand eigentlich katastrophal.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:05 Sa 21.12.2013 | | Autor: | MaxHBB |
Hallo Al-Chwarizimi,
zunächst einmal stimme ich dir zu deiner Aussage über das Chaos bei den natürlichen Zahlen zu. Ich finde es äußerst merkwürdig, dass man sich noch nicht darüber einig geworden ist, ob die 0 nun dazugehört oder nicht. Ich habe für meinen Teil entschieden, dass ich die 0 nicht dazuzähle, weil das zum Beispiel bei Folgen einiges vereinfacht. Wenn man nämlich eine Folge [mm] $a_{n(n \in \IN)}$ [/mm] hat, dann ist beispielsweise das sechste Folgenglied auch das mit dem Index 6 und nicht mit dem Index 5. Bei dem Beweis ist es jedoch etwas störend, die 0 nicht dazuzuzählen, weil der Binomialkoeffizient ja uch mit der 0 funktioniert. Vielleicht sollte ich mir diese Konsequenz abgewöhnen und von Fall zu Fall unterscheiden, ob ich die 0 nun dazuzähle oder nicht.
Definition (3) ist gemeint.
Bei deiner Kritik an dem Beweis stimme ich dir zu, bei dem Induktionsschritt mangelt es an Anschaulichkeit. Das ganze ist so gemeint:
[mm]\bruch{n!}{k!(n-k)!}[/mm] + [mm]\bruch{n!}{(k-1)!(n-k+1)!}[/mm] ist die Anzahl der k-elementigen Teilmengen einer n+1-elementigen Menge, da
- der erste Summand die Anzahl aller k-elementigen Teilmengen einer n-elementigen Menge ist, bezogen auf unsere n+1-elementige Menge also alle k-elementigen Teilmengen, die das n+1-ste Element noch nicht enthalten
- der zweite Summand die Anzahl der k-elementigen Teilmengen unserer n+1-elementigen Menge ist, die das n+1-ste Element schon enthalten. Diese Anzahl entspricht dabei genau der Anzahl k-1-elementiger Teilmengen einer n-elementigen Menge, da wenn man dann das n+1-ste Element dazunimmt genau die Anzahl der k-elementigen Teilmengen der n+1-elementigen Menge, die das n+1-ste Element enthalten, herauskommt.
Viele Grüße,
Max
|
|
|
| |
|
> Hallo Al-Chwarizimi,
>
> zunächst einmal stimme ich dir zu deiner Aussage über das
> Chaos bei den natürlichen Zahlen zu. Ich finde es
> äußerst merkwürdig, dass man sich noch nicht darüber
> einig geworden ist, ob die 0 nun dazugehört oder nicht.
Ja, es hat sich da ein gewisser Wandel abgespielt.
Früher war die Definition [mm] $\IN\ [/mm] =\ [mm] \{\,1,\,2,\,3,\,4,\,5\ ......\,\}$ [/mm] die
übliche. Wollte man die Null auch dazunehmen, schrieb
man für diese neue Menge [mm] \IN_0 [/mm] . Damit bin ich aufge-
wachsen.
Seit etwa 20 Jahren hat sich aber offenbar eher die
andere Konvention mit [mm] $\IN\ [/mm] =\ [mm] \{\,0,\,1,\,2,\,3,\,4,\,5\ ......\,\}$ [/mm] durch-
gesetzt. Meint man dann aber trotzdem nur die Menge
der natürlichen Zahlen ohne die Null, soll man dafür
dann [mm] $\mbox{\large{\mathb{IN}^{\ast}}} [/mm] schreiben.
Dazu gibt es sogar, wie ich vor einiger Zeit erfahren
habe, seit 1992 sogar eine DIN - Norm !
Diese DIN-Norm Nr. 5473 und ein paar weitere, die sich
auf mathematische Notationen beziehen, sind hübsch
eingebettet zwischen
DIN 5472: .... Keilwellen- und Keilnaben-Profile ....
DIN 5480: Zahnwellen-Verbindungen mit Evolventenflanken
> Ich habe für meinen Teil entschieden, dass ich die 0 nicht
> dazuzähle, weil das zum Beispiel bei Folgen einiges
> vereinfacht. Wenn man nämlich eine Folge [mm]a_{n(n \in \IN)}[/mm]
> hat, dann ist beispielsweise das sechste Folgenglied auch
> das mit dem Index 6 und nicht mit dem Index 5. Bei dem
> Beweis ist es jedoch etwas störend, die 0 nicht
> dazuzuzählen, weil der Binomialkoeffizient ja auch mit der
> 0 funktioniert. Vielleicht sollte ich mir diese Konsequenz
> abgewöhnen und von Fall zu Fall unterscheiden, ob ich die
> 0 nun dazuzähle oder nicht.
>
> Definition (3) ist gemeint.
>
> Bei deiner Kritik an dem Beweis stimme ich dir zu, bei dem
> Induktionsschritt mangelt es an Anschaulichkeit. Das ganze
> ist so gemeint:
> [mm]\bruch{n!}{k!(n-k)!}[/mm] + [mm]\bruch{n!}{(k-1)!(n-k+1)!}[/mm] ist die
> Anzahl der k-elementigen Teilmengen einer n+1-elementigen
> Menge, da
> - der erste Summand die Anzahl aller k-elementigen
> Teilmengen einer n-elementigen Menge ist, bezogen auf
> unsere n+1-elementige Menge also alle k-elementigen
> Teilmengen, die das n+1-ste Element noch nicht enthalten
> - der zweite Summand die Anzahl der k-elementigen
> Teilmengen unserer n+1-elementigen Menge ist, die das
> n+1-ste Element schon enthalten. Diese Anzahl entspricht
> dabei genau der Anzahl k-1-elementiger Teilmengen einer
> n-elementigen Menge, da wenn man dann das n+1-ste Element
> dazunimmt genau die Anzahl der k-elementigen Teilmengen der
> n+1-elementigen Menge, die das n+1-ste Element enthalten,
> herauskommt.
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
Ja, exakt eine solche Argumentation hat vorher noch gefehlt.
LG , Al-Chw.
|
|
|
|
