Binomialkoeff. Urnenmodell < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:40 Mo 23.11.2020 | | Autor: | TS85 |
| Aufgabe | Der Satz formuliert 2 Gleichungen für den Binomialkoeffizienten, die durch Einsetzen und Ausrechnen bewiesen werden, nämlich:
[mm] \vektor{n+1 \\ k}=\vektor{n \\ k-1}+\vektor{n \\ k}
[/mm]
und [mm] \vektor{n \\ k}=\vektor{n \\ n-k}
[/mm]
[mm] \forall [/mm] n,k [mm] \in \IN_0 [/mm] ( in dieser Aufgabe nur [mm] \IN_0).
[/mm]
Der Binomialkoeffizient hat aber auch eine kombinatorische Bedeutung in Gestalt des dritten Urnenmodells [mm] \Omega_{III}. [/mm] Begründen sie die beiden Gleichungen durch Interpretation im Urnenmodell: Was bedeuten die Gleichungen und wieso sind sie offensichtlich richtig? |
Hallo,
da die Aufgabe (für mich) etwas ungewöhnlich ist (Argumentativ anhand von Modell zu beweisen), möchte ich hier nach Meinungen/Korrekturen zu meinem Lösungsansatz fragen.
Allgemein zuerst: Modell [mm] \Omega_{III} [/mm] basiert auf nicht Zurücklegen ohne Reihenfolge, d.h. die in einem Durchgang gezogenen Kugeln aus der Urne werden nicht zurückgelegt, sodass keine doppelten Werte in einer Paarung auftreten können. Im Zusammenhang mit ohne Reihenfolge bedeutet das, dass in diesem Fall nur Mengen betrachtet werden [mm] (\{1,2\}=\{2,1\}).
[/mm]
(Binomialkoeffizient=|k-Potenzmenge|)
1. Gleichung:
Es gibt gleichviele Kombinationsmöglichkeiten bei n+1 Kugeln
mit Ziehen von k Kugeln (i) wie bei n Kugeln mit (k-1)xZiehen plus n Kugeln mit (k)x Ziehen (ii).
Nun gilt folgendes: Bei (i) wird die k-Potenzmenge aus n+1 Kugeln gezogen. Das gleiche geschieht bei (ii) mit [mm] \vektor{n \\ k}, [/mm] nur mit dem Unterschied, dass 1 Kugel weniger vorhanden ist, d.h. alle Paare mit der Nummer n+1 fehlen hier. Diese Paare können nur aus den Kombinationen bestehen, welche die Kugel Nr. n+1 enthalten (Im Falle von [mm] k=2:\{n+1,n\},\{n+1,n-1\},...,\{n+1,1\}. [/mm] Dies sind n Mengen, da [mm] \{n+1,n+1\} [/mm] nicht vorhanden sein kann).
Die gleiche Anzahl (was für die Gleichheit notwendig ist; es werden nur die Kombinationsanzahlen verglichen, nicht die Kombinationen an sich auf Gleichheit untersucht) ensteht nun aus [mm] \vektor{n \\ k-1}
[/mm]
Zügen, d.h. im Falle von k=2 mit n Kugeln.
(Hier fehlt vermutlich nun nur noch das Argument, warum dies im Allgemeinen Fall mit k gelten sollte. Wie anhand von Urnenmodell erläutern?)
2. Gleichung:
Die Gleichung besagt, dass durch die in der Vorlesung bereits bewiesenen Symmetrieeigenschaft man beim Auswählen von k-Kugeln über n insgesamt die Gleiche Anzahl erhält wie bei der Auswahl mit n-k. Allgemein bedeutet dies anhand vom Urnenmodell, dass die Kombinationsmöglichkeiten abnehmen, je mehr [mm] k\to0 [/mm] oder [mm] k\to [/mm] n geht, d.h. wenn nur 0 Kugel gezogen werden, können nur die 0 Paare ausgewählt werden (entspricht der leeren Menge als Anzahl 1). Bei nx Ziehen nur die n Kugeln alle aufeinmal. Die größte Kombinationsmöglichkeit (wie beim Pascalschen Dreieck) ergibt sich bei ungeradem n bei ceil(n/k) und floor(n/k) und bei geraden n bei
n/k (Indexbeginn bei 0). Ist bspw. k=1,
dann werden auf der linken Seite der Gleichung die Kugeln [mm] \{1\}, \{2\},..., \{n\}
[/mm]
gezogen, auf der rechten n-1 Kugeln, d.h. die n-1 Potenzmenge aus n Kugeln.
(Hier immer n-1 Paarungen mit der 1 enthalten, 1 Paarung ohne die 1, d.h. n-Paarungen gesamt.)
Was genau könnte verbessert werden? Vermutlich fehlt die Verallgemeinerung für alle Fälle, was könnte man hier anführen anhand vom Urnenmodell?
Eine Korrektur/Anregungen im Laufe des Tages wären nett.
|
|
| |
|
Ich würde viel anschaulicher argumentieren.
Ein Schiff mit n Passagieren geht unter. Es passen nur k Personen ins Rettungsboot. Dann gibt [mm] \vektor{n \\ k} [/mm] die Anzahl der Möglichkeiten für die Bestückung des Rettungsbootes an.
Genau so gut könnte man aber aus den n Personen diejenigen n-k Personen auswählen, die nicht ins Rettungsboot kommen. Jeder Auswahl der ersten Sichtweise entspricht eine Auswahl der zweiten Sichtweise. Daher ist [mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n \\n-k}.
[/mm]
Nun haben wir aber vergessen, dass ja der Kapitän auch noch getettet werden könnte. Deshalb haben wir nun [mm] \vektor{n+1 \\ k} [/mm] Möglichkeiten für das Rettungsboot. Dazu gehören schon mal alle bisherigen ohne den Kapitän, also [mm] \vektor{n \\ k}, [/mm] und zusätzlich die mit Kapitän. Den setzen wir nun in Gedanken ins Boot, dann haben wir für die k-1 weiteren Plätze noch weitere [mm] \vektor{n \\ k-1} [/mm] Möglichkeiten mit Kapitän. Also ist
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1}.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:14 Mo 23.11.2020 | | Autor: | TS85 |
Ok danke für den Hinweis, das bringt es dann wohl sehr einfach auf den Punkt. Ich werde es in meine Lösung miteinbeziehen, eine Antwort auf diese Weise werde ich allerdings in meiner Position als Student lieber nicht machen.
|
|
|
| |
|
Das sehe ich ganz anders! Je einfacher/anschaulicher die Erklärung, desto verständlicher die Beweisführung. Was ist an Kugeln, die aus einer Urne gezogen werden (wann kommt das wirklich vor?) anders, als an Leuten, die in Rettungsboote springen? Welche Beweisführung werden du und deine Kommilitonen wohl länger im Kopf behalten?
Mach mal den Test: Frag deinen Prof, ob eine solche Beweisführung auch akzeptiert wird.
Hier noch mein Lieblingsbeispiel für die Vereinfachung eines Sachverhalts:
Thema 2 Gleichungen mit 2 Unbekannten. "Auf einem Bauernhof leben Hühner und Schafe. Sie haben zusammen 100 Köpfe und 240 Beine. Wieviele sind es von jeder Sorte?"
Schülerantwort: Wären es nur Hühner, hätten wir 200 Beine. Tauschen wir ein Huhn gegen ein Schaf, werden es 2 Beine mehr. Wir brauchen 40 Beine mehr, tauschen also 20 mal. 20 Schafe, 80 Hühner.
Da war nix mit x und y.
|
|
|
|
