Binomialkoeffizient < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:44 Fr 09.11.2012 | | Autor: | fairy89 |
| Aufgabe | | Wie viele Möglichkeiten gibt es, 1000 als Summe von drei positiven ganzen Zahlen zu schreiben? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Für kleinere Zahlen kann ich dieses Problem mit der Formel [mm] \bruch{n!}{n!*(n-k)!} [/mm] lösen.
Für so große Zahlen ist dieses mit dem Taschenrechner jedoch nicht möglich.
Jetzt habe ich erfahren und ausprobiert, dass auch die Gaussche Formel anwendbar ist. Also in diesem Fall [mm] \bruch{(1000-2)*(1000-1)}{2}
[/mm]
Ich kann jedoch nicht erklären, wieso das auch richtig ist und wie man dahin kommt.
Kann mir da jemand weiterhelfen?
Danke im voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:04 Fr 09.11.2012 | | Autor: | abakus |
> Wie viele Möglichkeiten gibt es, 1000 als Summe von drei
> positiven ganzen Zahlen zu schreiben?
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Für kleinere Zahlen kann ich dieses Problem mit der Formel
> [mm]\bruch{n!}{n!*(n-k)!}[/mm] lösen.
> Für so große Zahlen ist dieses mit dem Taschenrechner
> jedoch nicht möglich.
> Jetzt habe ich erfahren und ausprobiert, dass auch die
> Gaussche Formel anwendbar ist. Also in diesem Fall
> [mm]\bruch{(1000-2)*(1000-1)}{2}[/mm]
> Ich kann jedoch nicht erklären, wieso das auch richtig
> ist und wie man dahin kommt.
> Kann mir da jemand weiterhelfen?
> Danke im voraus!
Hallo,
Falls die kleinste Zahl 1 ist, gibt es für die anderen beiden Zahlen 499 Möglichkeiten (1+998 bis 499+500).
Falls die kleinste Zahl 2 ist, gibt es für die anderen beiden Zahlen 498 Möglichkeiten (2+896 bis 499+499).
Falls die kleinste Zahl 3 ist, gibt es für die anderen beiden Zahlen 496 Möglichkeiten (3+994 bis 498+499).
Falls die kleinste Zahl 4 ist, gibt es für die anderen beiden Zahlen 495 Möglichkeiten (4+992 bis 498+498).
Falls die kleinste Zahl 5 ist, gibt es für die anderen beiden Zahlen 493 Möglichkeiten (5+990 bis 497+498).
Falls die kleinste Zahl 6 ist, gibt es für die anderen beiden Zahlen 492 Möglichkeiten (6+992 bis 497+497).
Wenn die kleinste Zahl ungerade ist (kann 1 bis 333 sein), hat man
499+496+493+...7+4+1 Möglichkeiten (dafür gibt es eine Summenformel.
Wenn die kleinste Zahl gerade ist (kann 2 bis 332 sein), hat man
498+495+492+...6+3 Möglichkeiten (dafür gibt es auch eine Summenformel.
Gruß Abakus
|
|
|
| |
|
Hallo Fee,
da stimmt etwas von Anfang an nicht.
> Wie viele Möglichkeiten gibt es, 1000 als Summe von drei
> positiven ganzen Zahlen zu schreiben?
>
> Für kleinere Zahlen kann ich dieses Problem mit der Formel
> [mm]\bruch{n!}{n!*(n-k)!}[/mm] lösen.
Garantiert nicht.
Nehmen wir mal die 5. Als Summe von drei Zahlen gehen da nur 1+1+3 und 1+2+2. Also zwei Möglichkeiten.
Kein Binomialkoeffizient [mm] \vektor{5\\k} [/mm] ergibt aber 2. Möglich sind hier nur 1,5,10 (und, je nach Definition, auch noch die 0).
Oder kommt es auf die Additionsreihenfolge an? Dann gibt es die Aufteilungen 1+1+3, 1+3+1, 3+1+1, 1+2+2, 2+1+2 und 2+2+1. Also sechs Möglichkeiten. Geht also auch nicht, siehe oben.
Oder ist die Null als Summand erlaubt?
Dann sind es ohne Reihenfolge 0+0+5, 0+1+4, 0+2+3, 1+1+3, 1+2+2. Fünf Möglichkeiten. Schon besser. Immerhin ist [mm] \vektor{5\\1}=\vektor{5\\4}=5. [/mm] Aber woher kommen die 1 oder die 4 "unten" im Binomialkoeffizienten? Und klappt das auch so ähnlich, wenn ich die 6 oder 7 zerlegen will statt der 5?
Mit Null, ohne Reihenfolge. Die schreibe ich nicht mehr alle auf, aber es sind 3+6+6+3+3=21 Möglichkeiten. Die kann man tatsächlich als Binomialkoeffizient bestimmen, muss aber erstmal erklären, wieso hier [mm] \vektor{7\\2} [/mm] die richtige Lösung ist.
Also erstmal braucht die Aufgabe mehr Genauigkeit.
Was genau heißt "drei Zahlen"?
> Für so große Zahlen ist dieses mit dem Taschenrechner
> jedoch nicht möglich.
Nicht exakt, aber mit der ![[]](/images/popup.gif) Stirlingformel geht es trotzdem ziemlich genau. "Nicht möglich" ist also zu vorschnell.
> Jetzt habe ich erfahren und ausprobiert, dass auch die
> Gaussche Formel anwendbar ist. Also in diesem Fall
> [mm]\bruch{(1000-2)*(1000-1)}{2}[/mm]
Auch wieder: definitiv nicht. Das ist z.B. die Zahl möglicher Paare aus 999 Personen (das "Händeschüttelproblem"...). Bei 1000 Personen müsste man sich schon eine kompliziertere Geschichte ausdenken.
> Ich kann jedoch nicht erklären, wieso das auch richtig
> ist und wie man dahin kommt.
Ich auch nicht. Es ist nämlich falsch.
Immerhin kann man aber mit dem Taschenrechner Binomialkoeffizienten [mm] \vektor{n\\k} [/mm] auch dann noch exakt ausrechnen, wenn n groß und k klein ist, z.B. [mm] \vektor{786\\5}=\bruch{786*785*784*783*782}{1*2*3*4*5}
[/mm]
Das kannst Du Dir aus der allgemeinen Formel aber auch leicht selbst herleiten. Überleg mal, wieso das so ist.
> Kann mir da jemand weiterhelfen?
> Danke im voraus!
Tja, wie gesagt: erst einmal muss das Problem genau definiert werden.
1) Kommt es auf die Reihenfolge der Summanden an?
2) Ist die Null erlaubt?
Danach können wir ja mal genauer nach einer "Formel" suchen. Abakus hat damit ja schon angefangen, allerdings dabei implizit die beiden obigen Fragen verneint. Aber wie gesagt: auch dann stimmt keine Deiner bisherigen Formeln.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:20 Fr 09.11.2012 | | Autor: | fairy89 |
Hallo Reverend,
Oder kommt es auf die Additionsreihenfolge an? Dann gibt es die Aufteilungen 1+1+3, 1+3+1, 3+1+1, 1+2+2, 2+1+2 und 2+2+1. Also sechs Möglichkeiten. Geht also auch nicht, siehe oben.
Oder ist die Null als Summand erlaubt?
Also, es sind nur positive ganze Zahlen erlaubt, die 0 ist nicht mit dabei.
Die Reihenfolge ist wichtig, d.h. es gibt für die Zahl 5 Möglichkeiten, diese
darzustellen.
1+2+2
2+1+2
2+2+1
1+1+3
1+3+1
3+1+1
Für die Zahl 6 gibt es 10 Möglichkeiten, für die Zahl 7 gibt es 15, für die Zahl 8 gibt es 21.
Das sind die Dreieckszahlen des Pascalschen Dreiecks.
Gebe ich jetzt also für die Zahl 5 in die Formel
[mm] \bruch{4!}{2*(4-2)!} [/mm]
ein, so kommt 6 heraus, genau das gleiche, wenn ich [mm] \bruch{(5-2)*(5-1)}{2}
[/mm]
eingebe. Und das passt auch bei allen anderen Zahlen.
Ich auch nicht. Es ist nämlich falsch.
Warum sollte es also falsch sein?
Aber wie gesagt: auch dann stimmt keine Deiner bisherigen Formeln.
Bist du dir ganz sicher dass es völlig falsch ist?
|
|
|
| |
|
Hallo nochmal,
Du hast Recht. Gerade für diesen Fall habe ich mich vertan.
> Oder kommt es auf die Additionsreihenfolge an? Dann gibt es
> die Aufteilungen 1+1+3, 1+3+1, 3+1+1, 1+2+2, 2+1+2 und
> 2+2+1. Also sechs Möglichkeiten. Geht also auch nicht,
> siehe oben.
>
> Oder ist die Null als Summand erlaubt?
>
> Also, es sind nur positive ganze Zahlen erlaubt, die 0 ist
> nicht mit dabei.
Das hatte ich erwartet...
> Die Reihenfolge ist wichtig,
...und das nicht.
> d.h. es gibt für die Zahl 5
> Möglichkeiten, diese
> darzustellen.
> 1+2+2
> 2+1+2
> 2+2+1
> 1+1+3
> 1+3+1
> 3+1+1
>
> Für die Zahl 6 gibt es 10 Möglichkeiten, für die Zahl 7
> gibt es 15, für die Zahl 8 gibt es 21.
> Das sind die Dreieckszahlen des Pascalschen Dreiecks.
Stimmt.
> Gebe ich jetzt also für die Zahl 5 in die Formel
> [mm]\bruch{4!}{2*(4-2)!}[/mm]
Wo steht denn da eine 5?
> ein, so kommt 6 heraus, genau das gleiche, wenn ich
> [mm]\bruch{(5-2)*(5-1)}{2}[/mm]
> eingebe. Und das passt auch bei allen anderen Zahlen.
Klar. Aber die Formel ist nicht allgemein [mm] \vektor{n\\k}.
[/mm]
Die Möglichkeiten, die Zahl n in drei positive Summanden [mm] \not=0 [/mm] (unter Beachtung der Reihenfolge) aufzuteilen, sind [mm] \vektor{n-1\\2}. [/mm] Für alle n.
> Ich auch nicht. Es ist nämlich falsch.
> Warum sollte es also falsch sein?
Wie gesagt, an dieser Stelle habe ich mich geirrt.
> Aber wie gesagt: auch dann stimmt keine Deiner bisherigen
> Formeln.
>
> Bist du dir ganz sicher dass es völlig falsch ist?
Nein, nur die Angabe des Binomialkoeffizienten.
Man kann die Formel übrigens auch kombinatorisch herleiten, braucht dazu aber erstmal einen Zugang. Hast Du eine Idee, oder ist Dir die Herleitung sowieso nicht wichtig?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:07 Sa 10.11.2012 | | Autor: | fairy89 |
Hallo,
ich hoffe, solange kommen wir der Sache näher.
> Gebe ich jetzt also für die Zahl 5 in die Formel
> $ [mm] \bruch{4!}{2\cdot{}(4-2)!} [/mm] $ ein
> Wo steht denn da eine 5?
Wenn du dir mal folgenden Link ansiehst, verstehst du vielleicht, was ich meine:
http://www.mathematische-basteleien.de/pascaldreieck.htm
Da die erste Reihe ja bei 0 anfängt, wäre die Zahl 6 also in der 5ten
Reihe, die Zahl 5 in der 4ten Reihe usw.
Deswegen komme ich auf 4 und 2.
> genau das gleiche, wenn ich
> $ [mm] \bruch{(5-2)\cdot{}(5-1)}{2} [/mm] $
> eingebe. Und das passt auch bei allen anderen Zahlen.
> Klar. Aber die Formel ist nicht allgemein
Die Gaussche Summenformel
[mm] \bruch{n*(n+1)}{2}
[/mm]
habe ich so umformuliert, dass [mm] \bruch{(n-2)*(n+1-2)}{2}
[/mm]
sodass ich also zu der Formulierung der Formel komme.
Somit ist das eigentlich auch wieder allgemein oder?
> Man kann die Formel übrigens auch kombinatorisch herleiten, braucht
> dazu aber erstmal einen Zugang. Hast Du eine Idee, oder ist Dir die
> Herleitung sowieso nicht wichtig?
Die Herleitung ist mir sehr wichtig, deswegen habe ich diese Frage hier erst gestellt.
Grüße
fairy
|
|
|
| |
|
Hallo fairy,
> ich hoffe, solange kommen wir der Sache näher.
Das sieht so aus.
> > Gebe ich jetzt also für die Zahl 5 in die Formel
> > [mm]\bruch{4!}{2\cdot{}(4-2)!}[/mm] ein
> > Wo steht denn da eine 5?
>
> Wenn du dir mal folgenden Link ansiehst, verstehst du
> vielleicht, was ich meine:
> http://www.mathematische-basteleien.de/pascaldreieck.htm
> Da die erste Reihe ja bei 0 anfängt, wäre die Zahl 6
> also in der 5ten
> Reihe, die Zahl 5 in der 4ten Reihe usw.
> Deswegen komme ich auf 4 und 2.
Deine Beobachtung ist ja richtig, aber die Begründung genügt nicht.
Wenn ich aus 5 Spielkarten 3 ziehe, habe ich [mm] \vektor{5\\3} [/mm] Möglichkeiten. Warum sind es nur [mm] \vektor{4\\2}, [/mm] wenn ich die 5 in drei Summanden aufteile?
Oder allgemeiner: warum gibt es [mm] \vektor{n-1\\k-1} [/mm] Möglichkeiten, die Zahl n in k Summanden aufzuteilen? (Voraussetzung nach wie vor: kein Summand 0, Reihenfolge der Summanden wird beachtet bzw. unterschieden.)
> > genau das gleiche, wenn ich
> > [mm]\bruch{(5-2)\cdot{}(5-1)}{2}[/mm]
> > eingebe. Und das passt auch bei allen anderen Zahlen.
>
> > Klar. Aber die Formel ist nicht allgemein
>
>
> Die Gaussche Summenformel
> [mm]\bruch{n*(n+1)}{2}[/mm]
> habe ich so umformuliert, dass [mm]\bruch{(n-2)*(n+1-2)}{2}[/mm]
> sodass ich also zu der Formulierung der Formel komme.
> Somit ist das eigentlich auch wieder allgemein oder?
Ja, es ist allgemein, aber es ist nicht begründet, siehe oben.
> > Man kann die Formel übrigens auch kombinatorisch
> herleiten, braucht
> > dazu aber erstmal einen Zugang. Hast Du eine Idee, oder ist
> Dir die
> > Herleitung sowieso nicht wichtig?
>
> Die Herleitung ist mir sehr wichtig, deswegen habe ich
> diese Frage hier erst gestellt.
Ah, ok.
Ich leite die Formel rein kombinatorisch her. Dabei verwende ich als bekannt, dass man aus m unterscheidbaren Kugeln [mm] \vektor{m\\r} [/mm] Sets von r Kugeln bilden kann.
Wir haben nun n gleiche Kugeln vorliegen (sagen wir: weiß), die wir in k "Haufen" aufteilen wollen. Kein Haufen darf leer sein.
Dazu legen wir erst einmal k Kugeln beiseite.
Zu den restlichen n-k Kugeln legen wir k-1 Kugeln anderer Farbe (sagen wir: rot). Diese insgesamt n-1 Kugeln verteilen wir nun auf n-1 Plätze nebeneinander.
Die roten Kugeln sind dabei nur "Trenner". Der erste Haufen geht also von links bis zur ersten roten Kugel (die nicht mitzählt), der zweite beginnt danach und geht bis zur nächsten roten Kugel, etc.
Wir erhalten so k "Haufen", die allerdings auch leer sein können.
Als letztes erhält aber nun jeder Haufen genau eine der k anfangs beiseitegelegten Kugeln. Damit ist kein Haufen mehr leer.
Klingt kompliziert, ist aber leicht zu berechnen.
Man braucht jetzt nur die Zahl der Möglichkeiten, die k-1 roten Kugeln auf n-1 Plätze zu verteilen, und diese Zahl ist [mm] \vektor{n-1\\k-1}.
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:54 Sa 10.11.2012 | | Autor: | fairy89 |
Ok, vielen Dank reverend.
Ich muss noch darüber nachdenken, aber ich glaube so in etwa
habe ich es verstanden.
Gruß
fairy
|
|
|
|
