Beweis Binomischer Lehrsatz < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:24 Di 25.10.2016 | | Autor: | X3nion |
Hallo zusammen!
Mir ist der direkte Beweis des Binomischen Lehrsatzes ohne vollständige Induktion nicht so ganz klar.
Wenn ich [mm] (a+b)^{n} [/mm] anders geschrieben wäre ja
[mm] \underbrace{(a+b) * (a+b) * (a+b) * ... * (a+b)}_{n-mal}
[/mm]
Was mir einleuchtet ist, dass es Produkte der Form [mm] a^{k}*b^{n-k} [/mm] gibt, da jeder Summand eines Faktors mit jedem Summanden eines anderen Faktors multipliziert wird, quasi nach der Regel "jedes mit jedem" und somit alle Kombinationen vorkommen.
Bei [mm] (a+b)^{2} [/mm] ergibt sich (a+b)*(a+b)=a*a+a*b+b*a+b*b
und es kommen die Kombinationen a², ab und b² vor.
Bei [mm] (a+b)^{3} [/mm] ergibt sich (a+b) * (a+b) * (a+b) = a*a*a + a*a*b + a*b*a + a*b*b + b*a*a + b*a*b + b*b*a + b*b*b
und es kommen die Kombinationen a³, a²b, ab² und b³ vor.
Was ich nun jedoch nicht verstehe ist der Punkt, dass man, um einen Term der Form [mm] a^{k}*b^{n-k} [/mm] zu bekommen, in genau k der insgesamt n Faktoren (x+y) jeweils den Summanden x auswählt, und dass dies gleichbedeutend ist mit der Aussage von [mm] \vektor{n \\ k}, [/mm] also die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge.
Wenn ich zum Beispiel die Zahl der 2-elementigen Teilmengen der 4-elementigen Menge [mm] M=\{1, 2, 3, 4\} [/mm] betrachte, so leuchtet mir der Binomialkoeffizient [mm] \vektor{4 \\ 2} [/mm] und die anschauliche Betrachtung ein:
Ich habe 4 Möglichkeiten, den ersten "linken" Platz in der Menge zu belegen, nämlich einmal mit der 1, 2, 3 oder 4. Um den zweiten "rechten" Platz zu belegen habe ich nur noch 3 Möglichkeiten und insgesamt habe ich 4*3 = 12 Möglichkeiten. Da jedoch die Reihenfolge unerheblich ist, muss ich die 12 Möglichkeiten noch durch die Anzahl an Permutationen teilen, die ich in einer 2-elementigen Menge habe: dies sind in diesem Fall 2, denn ich kann ja in einer zweielementigen Menge nur einmal vertauschen. In einer 3-elementigen Menge würde ich durch 3*2 = 6 teilen, da ich insgesamt 6 Permutationen bekomme.
Aber was sind nun hier die k-elementigen Teilmengen einer n-elementigen Menge, und aus welchen Elementen besteht überhaupt meine n-elementige Menge?
Im Vergleich zu meinem Beispiel oben mit der Menge M verstehe ich zusätzlich nicht, wieso ich z.B. bei [mm] (a+b)^3 [/mm] die Faktoren a*a*b, a*b*a und b*a*a als 1-elementige Teilmengen einer 3-elementigen Menge betrachte, also [mm] \vektor{3\\1}, [/mm] ich habe doch insgesamt 3 Plätze?
Für eure Antworten zum Verständnis wäre ich sehr dankbar!
Viele Grüße,
X3nion
|
|
| |
|
Hiho,
betrachten wir mal dein erstes Argument:
> Wenn ich [mm](a+b)^{n}[/mm] anders geschrieben wäre ja
>
> [mm]\underbrace{(a+b) * (a+b) * (a+b) * ... * (a+b)}_{n-mal}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Was mir einleuchtet ist, dass es Produkte der Form [mm]a^{k}[/mm] *
> b ^{n-k} gibt, da jeder Summand eines Faktors mit jedem
> Summanden eines anderen Faktors multipliziert wird, quasi
> nach der Regel "jedes mit jedem" und somit alle
> Kombinationen vorkommen.
Ja, sieht es mal noch anders: Wir wählen jetzt mal ein festes $k [mm] \in \{0,\ldots,n\}$ [/mm] und überlegen, wie wir von [mm]\underbrace{(a+b) * (a+b) * (a+b) * ... * (a+b)}_{n-mal}[/mm] auf das Produkt [mm] $a^kb^{n-k}$ [/mm] kommen.
Das bekommen wir, indem wir aus den n Faktoren k Stück auswählen, bei denen wir von (a+b) das a nehmen und n-k Klammern, von denen wir das b nehmen.
D.h. wir haben aus n Faktoren k Stück auszuwählen, um [mm] $a^kb^{n-k}$ [/mm] zu erhalten.
Wie viele Möglichkeiten gibt es nun aus n Faktoren k Stück auszuwählen? [mm] $\binom{n}{k}$.
[/mm]
Oder lief deine Frage darauf hinaus, wieso die Anzahl an Kombinationen, um aus n Elementen k Auszuwählen gerade [mm] $\binom{n}{k}$ [/mm] ist?
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:36 Di 25.10.2016 | | Autor: | X3nion |
Hi Gono 
erstmal danke für deine Antwort
Mhm also mir fällt es allgemein etwas schwer zu verstehen, was bei z.B. k=1 und n=3 die k-elementigen Teilmengen der n-elementigen Menge M sind, also wie die Mengen konkret ausschauen würden.
Ein Beispiel:
Bei der Menge M = {1, 2, 3} leuchtet es mir ein, was
- [mm] \vektor{3\\1} [/mm] ist. Die Anzahl der einelementigen Teilmengen meiner 3-elementigen Menge M ist 3, nämlich vertreten durch die Teilmengen {1}, {2} und {3}.
- [mm] \vektor{3\\2} [/mm] ist die Anzahl der 2-elementigen Teilmengen meiner 3-elementigen Menge.
Hierzu betrachte ich zuerst die Anzahl an Möglichkeiten, die 1. von 2 Stellen zu belegen, und habe insgesamt 3, da meine Menge M 3 Elemente besitzt. Für die 2. Stelle habe ich noch 2 Möglichkeiten, da meine Menge durch Positionieren eines Elementes auf der 1. Stelle um 1 Element verringert wurde.
Insgesamt habe ich also 3*2 = 6 Möglichkeiten der Kombination, nämlich vertreten durch die Mengen {1, 2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}.
Dazu muss ich noch durch die Anzahl der Möglichen Permutationen bei einer 2-elementigen Menge teilen, diese beträgt "2" und somit erhalte ich insgesamt für [mm] \vektor{3\\2} [/mm] = 3.
- [mm] \vektor{3\\3} [/mm] beschreibt die Anzahl der 3-elementigen Teilmenge meiner 3-elementigen Menge.
Man hat zuerst 3 Möglichkeiten, um die 1. Position zu belegen.
Nach Belegen der 1. Position habe ich noch 2 Elemente zur Verfügung, und somit noch 2 Möglichkeiten, um die 2. Position zu belegen. Die 3. Position ergibt sich dann in nur noch 1 Möglichkeit, und insgesamt habe ich 3*2 = 6 Möglichkeiten der Kombination. Da die Reihenfolge keine Rolle spielt, muss ich noch durch die Anzahl der Permutationen einer 3-elementigen Menge teilen. Diese ist erneut 3*2 = 6 und somit erhalte ich für [mm] \vektor{3\\3} [/mm] = 1.
- [mm] \vektor{3\\0} [/mm] ist die leere Menge und somit enspricht dies der Anzahl "1"
Wären meine Beschreibungen bis hierhin korrekt?
Nun denn: ich begreife nun nicht, wie ich dies z.B. bei dem Fall
[mm] (a+b)^3 [/mm] notieren würde. Was wäre hier meine 3-elementige Menge konkret aufgeschrieben?
Und was wären z.B. bei k=1 die 1-elementigen Mengen, für k=2 die 2-elementigen Mengen und für k=3 die 3-elementigen Mengen konkret aufgeschrieben?
Es verwirrt mich etwas, wenn die Terme der Gestalt "a*a*b" oder "a*b*b" sind und somit doch immer 3 Positionen vorliegen.
Oder betrachte ich es so: Wenn ich [mm] (a+b)^3 [/mm] = (a+b) * (a+b) * (a+b) habe, so definiere ich eine Menge M = {1, 2, 3} und ordne die 1 dem ersten Faktor, die 2 dem zweiten Faktor und die 3 dem dritten Faktor zu, wobei ich jeweils von den Faktoren den ersten Buchstaben "a" nehme.
Wähle ich von meinen n Faktoren 1 Stück aus, bei denen ich das a nehme, so betrachte ich die Anzahl der 1-elementigen Teilmengen von M. Diese wäre 3, und die Teilmengen {1}, {2}, {3}.
Rückwärts gedacht befindet sich das a einmal an 1. Stelle (a*b*b), einmal an 2. Stelle (b*a*b) und einmal an 3. Stelle (b*b*a).
Wähle ich von meinen n Faktoren 2 Stück aus, bei denen ich das a nehme, so betrachte ich die Anzahl der 2-elementigen Teilmengen von M.
Die Anzahl entspräche 6 und die Mengen wären die oben die folgenden Mengen {1, 2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}, wobei die Reihenfolge der Elemente keine Rolle spielt und ich somit noch durch die Anzahl der Permutationen bei 2-elementigen Mengen teile, also durch 2.
=> Anzahl wäre 3
"Übersetzt" bekäme ich für {1, 2} den Term (a*a*b), für {2,1} den Term (a*a*b), für {1,3} den Term (a*b*a), für {3,1} den Term (a*b*a), ...
Insgesamt 3 Terme sind überflüssig, da sie von der Reihenfolge her exakt den anderen sprechen und können somit vernachlässigt werden.
Wäre meine Idee mit dem Umgang der k-elementigen Teilmengen so korrekt, oder gibt es eine andere Möglichkeit ohne eine Menge separat definieren zu müssen?
Für eure Antworten wäre ich wie immer sehr dankbar!
Gruß X3nion
|
|
|
| |
|
Hiho,
> Wären meine Beschreibungen bis hierhin korrekt?
Ja.
> Oder betrachte ich es so: Wenn ich [mm](a+b)^3[/mm] = (a+b) * (a+b)
> * (a+b) habe, so definiere ich eine Menge M = {1, 2, 3} und
> ordne die 1 dem ersten Faktor, die 2 dem zweiten Faktor und
> die 3 dem dritten Faktor zu, wobei ich jeweils von den
> Faktoren den ersten Buchstaben "a" nehme.
> Wähle ich von meinen n Faktoren 1 Stück aus, bei denen
> ich das a nehme, so betrachte ich die Anzahl der
> 1-elementigen Teilmengen von M. Diese wäre 3, und die
> Teilmengen {1}, {2}, {3}.
> Rückwärts gedacht befindet sich das a einmal an 1.
> Stelle (a*b*b), einmal an 2. Stelle (b*a*b) und einmal an
> 3. Stelle (b*b*a).
>
> Wähle ich von meinen n Faktoren 2 Stück aus, bei denen
> ich das a nehme, so betrachte ich die Anzahl der
> 2-elementigen Teilmengen von M.
> Die Anzahl entspräche 6 und die Mengen wären die oben
> die folgenden Mengen {1, 2}, {1,3}, {2,1}, {2,3}, {3,1},
> {3,2}, wobei die Reihenfolge der Elemente keine Rolle
> spielt und ich somit noch durch die Anzahl der
> Permutationen bei 2-elementigen Mengen teile, also durch
> 2.
> => Anzahl wäre 3
>
> "Übersetzt" bekäme ich für {1, 2} den Term (a*a*b), für
> {2,1} den Term (a*a*b), für {1,3} den Term (a*b*a), für
> {3,1} den Term (a*b*a), ...
>
> Insgesamt 3 Terme sind überflüssig, da sie von der
> Reihenfolge her exakt den anderen sprechen und können
> somit vernachlässigt werden.
diese Beschreibung bringt es eigentlich sehr gut auf den Punkt.
Rein "formal" tut man genau das, was du die ganze Zeit beschreibst:
Du hast die Menge [mm] $\{1,2,\ldots,n\}$ [/mm] (also n Elemente, die du mit den Zahlen 1 bis n identifizierst) und wählst daraus k aus, d.h. du suchst eine k-elementige Teilmenge davon, die gerade die Elemente beschreibt, die du raussuchst.
Im Falle k=3 wäre das beispielsweise:
[mm] $\{1,2,3\} \subseteq \{1,2,\ldots,n\}$ [/mm]
aber auch
[mm] $\{n,n-4,n-6\} \subseteq \{1,2,\ldots,n\}$ [/mm]
Wie viele Möglichkeiten gibt es nun aus dieser n-elementigen Teilmenge k auszuwählen?
Für das erste Element: n
Für das zweite Element: n-1
.
.
.
Für das k-te Element n-(k-1)
Insgesamt hat man also (erstmal) [mm] $n*(n-1)*\ldots*(n-(k-1)) [/mm] = [mm] \frac{n!}{(n-k)!} [/mm] Möglichkeiten. Da bei einer Menge die Reihenfolge der Elemente aber keine Rolle spielt, d.h. bspw. [mm] $\{1,2,3\} [/mm] = [mm] \{3,2,1\} [/mm] = [mm] \{3,1,2\}$ [/mm] muss man noch durch die Anzahl aller Permutationen von k Elementen teilen, das wäre gerade [mm] $k!\;$
[/mm]
Man erhält also insgesamt eine Anzahl von [mm] $\frac{n!}{(n-k)!k!} [/mm] = [mm] \binom{n}{k}$ [/mm] Möglichkeiten, aus einer n-elementigen Teilmenge eine k-elemtige auszuwählen.
Gruß,
Gono
|
|
|
| |
|
Ich würde das Ganze als Wortproblem auffassen. Willst du die Anzahl aller Wörter bestimmen, die man aus den Buchstaben des Wortes
ROKOKOKOMMODE
legen kann, so sind das [mm]\frac{13!}{1!5!3!2!1!1!}[/mm] Stück. Im Zähler steht die Fakultät der Wortlänge, im Nenner stehen die Fakultäten der Häufigkeiten der jeweiligen Buchstaben (1-mal R, 5-mal O, 3-mal K, 2-mal M, 1-mal D und 1-mal E). Vielleicht kennst du die entsprechende Formel. Wenn nicht, kannst du sie dir mit einer Erklärung wie für dein [mm]{4 \choose 2}[/mm] klarmachen.
Und jetzt nehmen wir [mm](a+b)^9 = (a+b)(a+b) \cdots (a+b)[/mm], um ein Beispiel zu haben. Beim Ausmultiplizieren entstehen Produkte mit 9 Faktoren, aus jeder Klammer kommt genau 1 Faktor. Jetzt gibt es Produkte, in denen genau 3-mal ein a und genau 6-mal ein b vorkommt. Um nun kein Durcheinander zu erzeugen, vertauschen wir die Faktoren nicht und fassen auch nichts zu Potenzen zusammen, d.h. wir halten die Reihenfolge der Klammern ein. So bekommen wir z.B. das Produkt babbbaabb oder das Produkt ababbabbb. Da wir nicht kommutieren, können wir die Produkte als Wörter auffassen. Nach der Regel von oben gibt es aber
[mm]\frac{9!}{3!6!} = {9 \choose 3}[/mm]
solche Wörter. Im Sinne der Algebra erzeugt aber jedes solche Wort die Potenz [mm]a^3b^6[/mm]. Damit kommt der Summand [mm]a^3b^6[/mm] genau [mm]{9 \choose 3}[/mm]-mal vor.
Man kann das auch anders sehen. Wir nummerieren die 9 Klammern [mm](a+b)[/mm] von links nach rechts mit 1,2,3,4,5,6,7,8,9. Das Wort babbbaabb von oben liegt fest, sobald wir feststellen, aus welchen Klammern die a sind. Hier sind das die Klammern 2,6,7, also entspricht dem Wort babbbaabb die 3-elementige Teilmenge [mm]\{2,6,7\}[/mm]. Für das Wort ababbabbb bekäme man entsprechend die 3-elementige Teilmenge [mm]\{ 1,3,6 \}[/mm]. Die Beziehung zwischen diesen Wörtern und den 3-elementigen Teilmengen ist bijektiv. Also kann man auch die 3-elementigen Teilmengen der 9-elementigen Menge [mm]\{ 1,2,3,4,5,6,7,8,9 \}[/mm] zählen. Die Anzahl der [mm]k=3[/mm]-elementigen Teilmengen einer [mm]n=9[/mm]-elementigen Menge ist aber [mm]{n \choose k} = {9 \choose 3}[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:58 Sa 29.10.2016 | | Autor: | X3nion |
Hallo zusammen!
Vielen Dank für eure beiden ausführlichen Erklärungen und Beispiele, ich meine es nun verstanden zu haben!
Mir persönlich "gefällt" die Methode mit der Nummerierung der Klammern am besten.
Für [mm] (a+b)^{6} [/mm] z.B. gibt es insgesamt 6 Möglichkeiten, genau ein 'a' aus jeder Klammer zu ziehen, nämlich einmal aus der ersten, einmal aus der zweiten usw. Also abbbbb, babbbb, ... , bbbbba. Da ich jeweils nur ein 'a' ziehe, gibt es auch keine zusätzlichen Permutationen durch die ich teilen müsste.
Das sieht hier aber anders aus: Um genau zwei 'a' aus 6 Klammern zu ziehen gibt es 6*5 = 30 Möglichkeiten, wenn ich die Reihenfolge berücksichtige.
Also z.B. entspricht aabbbb (das erste a kommt aus der 1. Klammer und das zweite a aus der 2. Klammer, als Menge aufgefasst {1,2}) dem Term aabbbb (das erste a kommt aus der 2. Klammer und das zweite a aus der 1. Klammer, als Menge aufgefasst {2,1}.).
Somit hätte ich, wenn ich nur [mm] \frac{n!}{(n-k)!}, [/mm] also in diesem Fall [mm] \frac{6!}{4!} [/mm] betrachten würde, Faktoren zu viel. Insgesamt teile ich folglich noch durch die Anzahl der Permutationen.
Hier wären das die Möglichkeiten, innerhalb einer zweielementigen Menge zu permutieren, und somit 2! = 2*1.
Was ich nun aber nicht verstanden habe ist das Beispiel mit den Worten von dir, Leopold_Gast.
Dass so viele Fakultäten im Nenner stehen, mit so etwas habe ich mich noch nicht beschäftigt, sondern nur wenn ich zwei Fakultäten im Nenner stehen habe, wie das bei [mm] \vektor{n\\k} [/mm] z.B. der Fall ist.
Könntest du oder könnte jemand anders mir die Varianten erklären, wenn man mehrere Fakultäten im Nenner hat und was das genau heißt?
Viele Grüße,
X3nion
|
|
|
| |
|
Hiho,
> Was ich nun aber nicht verstanden habe ist das Beispiel mit
> den Worten von dir, Leopold_Gast.
> Dass so viele Fakultäten im Nenner stehen, mit so etwas
> habe ich mich noch nicht beschäftigt, sondern nur wenn ich
> zwei Fakultäten im Nenner stehen habe, wie das bei
> [mm]\vektor{n\\k}[/mm] z.B. der Fall ist.
> Könntest du oder könnte jemand anders mir die Varianten
> erklären, wenn man mehrere Fakultäten im Nenner hat und
> was das genau heißt?
das heißt erstmal genau das, was da steht. Nämlich dass man durch Zahlen teilen muss 
Warum man das machen musst, ist gar nicht so kompliziert, den Großteil hast du schon verstanden.
Fangen wir also mal da an, was du bereits verstanden hattest:
Ziehst du aus einer n-elementigen Menge k heraus, so gibt es dafür (erstmal) [mm] \bruch{n!}{(n-k)!} [/mm] Möglichkeiten.
Nun kam es bei dir ja dazu, dass die Reihenfolge der k Elemente keine Rolle spielen, aus diesem Grund mussten wir die Anzahl aller Permutationen dieser k Elemente, die in [mm] \bruch{n!}{(n-k)!} [/mm] ja noch drinsteckt, wieder rausrechnen. Dafür gibt es eben k! Möglichkeiten, die wir "rausdividieren".
Ich wiederhole mal: Das lag nur daran, weil uns die Reihenfolge aller k gezogenen Elemente egal war. Du hattest also nur eine Gruppe von Elementen, bei denen dir die Reihenfolge egal war.
Etwas anderes wäre es gewesen, wenn du nun beispielsweise rote und blaue Kugeln gezogen hättest, bei denen die Reihenfolge der Kugeln eine Rolle gespielt hätte. Dann hättest du 2 Gruppen an Elementen gehabt, innerhalb derer die Reihenfolge keine Rolle spielt (es ist eben egal, ob zuerst die Kugel Rot1 und dann Rot2 kommt, oder umgekehrt), aber eben nicht auf die Gesamtmenge betrachtest.
Dann hättest du die Permutationen innerhalb der einzelnen Gruppen "herausdividieren" müssen, hättest also 2 Fakultäten im Nenner.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 22:15 So 30.10.2016 | | Autor: | X3nion |
Hallo Gono,
danke für deinen Versuch zur Erklärung, aber ich habe das mit den mehreren Gruppen immer noch nicht verstanden.
Könnten wir / könnte man das vielleicht an einem Beispiel machen?
Das wäre super!
Viele Grüße,
X3nion
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Di 01.11.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
