n über k für große Zahlen (Kombinatorik)

Question

Aufgabe:

a) Berechnen Sie \( \left(\left(\begin{array}{l}{999} \\ {309}\end{array}\right)\right) + \left(\left(\begin{array}{l}{999} \\ {301}\end{array}\right)\right)  \cdot \frac{300 !}{(1000)_{300}} \)

b) Bestimmen Sie alle \( n \in \mathbb{N}, n \geq 3, \) für die gilt: \( \left(\begin{array}{c}{n} \\ {n-2}\end{array}\right)+\left(\begin{array}{c}{n-1} \\ {n-3}\end{array}\right)+\left(\begin{array}{c}{n-2} \\ {2}\end{array}\right)=4 \)

 

Ansatz/Probleme:

a) 999!/ 300!*(999-300)! + 999!/ 301!*(999-301)! * 300!/(1000)₃₀₀

Das sind riesen Zahlen, gibt es eine Möglichkeit die anders zu berechnen oder kann ich zum Beispiel die 999 weg kürzen einmal oben und unter dem Bruch? Aber da es mit Fakultätszeichen ist, weiß ich nicht ob man das einfach so wegkürzen kann? Ich hab gelesen rekursiv kann man das machen, aber das sind ja trotzdem große zahlen?

Und bei b) soll man da alle n größer 3 einsetzen und ausprobieren bis es 4 wird?

Comments

a) da kürzt sich sicherlich was weg. Mir ist nicht ganz klar, was (1000)₃₀₀ bedeutet?

b) Man kann schauen, was rauskommt, wenn man n = 3 einsetzt. Allerdings wird behauptet, dass es auch für n größer 3  ginge. Sieht nach vollständiger Induktion aus.

---

bei a) komme ich auch mit (1000)₃₀₀ nicht klar.

b) kann man wohl einfach mal durch Vereinfachung machen.

---

In a) lässt sich die Klammer zusammenfassen.

Answer 1

b)

COMB(n, n - 2) + COMB(n - 1, n - 3) + COMB(n - 2, 2) = 4

n·(n - 1)/2 + (n - 1)·(n - 2)/2 + (n - 2)·(n - 3)/2 = 4

n·(n - 1) + (n - 1)·(n - 2) + (n - 2)·(n - 3) = 8

n^2 - n + n^2 - 3·n + 2 + n^2 - 5·n + 6 = 8

3·n^2 - 9·n = 0

3·n·(n - 3) = 0

n = 3 (oder n = 0)

Es gilt nur für n = 3

Answer 2

(Binom(999,300)+Binom(999,301))*300!/Pochhammer(1000,300)

Zwar kann man bei guten Rechnern wie http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

Pochhammer(1000,300) ausrechnen, aber wir wollen mal kürzen:  

{ Zwischenr.: (Binom(999,300)+Binom(999,301))=(999!*699/301+999!)/(300!*699!)  }

=(999!*699/301+999!)/(699!)/Pochhammer(1000,300)

=(999!*699/301+999!)/(699!)/(1299!/999!)

=(699/301+1)*999!/(699!)/(1299!/999!)

=(699/301+1)*999!²/(699!*1299!)

=(699/301+1)*prod [(k+700)/(k+1000)],k=0...299

=808144989110551352169278161558703056237465478431092397653980261851655961520053292080155495817322548005508596994813083180774322625883246021916774053974364763104860977710571977301977572937560905/

1263363284613635869098084572058815872331360948608560082250856961085426712932143751442162407379373432709098671552000868633661123693978508521429000388662253735592648945335227346770012001940432486690617480588852631695079221289129297402

=1/[1563287902093039245080099050979675270825 + 1/1+...]

bei y die letzten 40 Ziffern weglassen -> dann Ergebnis *10^-40:

=6.396774379569687823744904323361448205566162183...*10^-40

Comments

wegen Pochhammer[n, k]/k! = Binom[n + k - 1, k]   

kann man das Endergebnis auch so schreiben: Binom(1000,301)/Binom(1299,300)  

= 1000!*300!*999!/1299!/301!/699!  

=6.396774379569687823744904323361448205566162183...*10^-40

---

Achtung: alle meine Interpretationen beziehen sich auf die übliche Interpretation von Pochhammer (steigende Faktorielle)

Wie ich gerade nachlese, haben einige Abweichler aus der Kombinatorik eine andere Definition (unten fallende Faktorielle) [aus Wikipedia]:

Interpretation fallende Faktorielle:

Binom(1000,301)*300!*(1000-300)!/1000! =

=100/43

---

Wie kommst du drauf, dass die steigende Faktorielle die Übliche Interpretation ist?
Und da du jetzt ja doch noch auf die Idee gekommen bist, dass meine Interpretation richtig sein kann (und ohne Angabe mein Ergebnis übernommen hast), möchtest du vielleicht deinen Kommentar mein Ergebnis sei falsch

korrigieren?

---

zu "wie komme ich darauf":

http://functions.wolfram.com/GammaBetaErf/Pochhammer/02/

http://functions.wolfram.com/GammaBetaErf/Binomial/27/01/0004/

Die Schreibweise für Fallende Faktorielle ist normalerweise anders:

https://de.wikipedia.org/wiki/Fallende_und_steigende_Faktorielle

Ich habe außer den Wikipedia-Hinweis (den ich per Bild vor über 9 Stunden bereits selbst abgegeben habe) nichts zu dieser unüblichen Schreibweise gefunden.

zu "ohne Angabe mein Ergebnis übernommen hast":  

§1: ich habe selbst Angaben zur Wiki-Quelle getätigt, und mit rot gekennzeichnet, wo die unübliche Interpretation beginnt

§2: ich habe Dir selbst bestätigt, dass Deine 1. Zeile richtig ist, womit man die Binom-Summe zusammenfassen kann

§3: für die Zwischenschritte hatte ich gestern zur späten Stunde keine Zeit -> und das hätte der Fragesteller bestimmt auch hinbekommen:

Binom(1000,301)*300!*(1000-300)!/1000! 

=1000!/1000! * 300!/301! * 700!/699!

= 1/301 * 700/1 = 700/301 = 100/43 = 2.325581395348837209302325581...

Damit wir uns hier nicht um veraltete Schreibweisen streiten schlage ich die eindeutige Benennung vor:

A) normale steigende Faktorielle, die bei zig Definitionen (hypergeometrischen Funktionen) Online Rechnern praktisch angewendet wird:

Pochhammer(x,n)=Gamma(x+n)/Gamma(x)=(x+n-1)!/(x-1)! = Prod (x+k),k=0...n-1

Pochhammer(11,7)=11*12*13*14*15*16*17=98017920

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

http://keisan.casio.com/calculator

WolframAlpha

B) fallende Faktorielle (Mathematica):

FactorialPower[x,n] = x!/(x-n)! = Prod (x-k),k=0...n-1

FactorialPower[11,7]=11*10*9*8*7*6*5 =1663200

Der Fragesteller muss selbst entscheiden, welche Interpretation sein Professor nutzt.

Answer 3

Es gilt: \( \binom n k  + \binom n {k+1} = \binom{n+1}{k+1}\)

und \( \binom n k = \frac{(n)_k}{k!}\).

Damit ist der Term in a) gleich \( \binom {1000}{301} \binom{1000}{300}^{-1}  \)

Außerdem gilt: \( \binom n {k+1} = \binom n k \frac{n-k}{k+1}\)

Damit ergibt sich für den Term: \( \binom{1000}{300} \frac{700}{301} \binom{1000}{300}^{-1}=\frac{700}{301} \)

Comments

schon die 2. Zeile ist falsch, denn:

Pochhammer[a, k] = Gamma[k + 1]* Binom[a + k - 1, k] = k! * Binom[a + k - 1, k]

also Pochhammer[n, k]/k! = Binom[n + k - 1, k]

oder

Binomial[n, k] = Pochhammer[k + 1, n - k]/Gamma[n - k + 1]=Pochhammer[k + 1, n - k]/(n - k)!

richtig ist: nur 1. Zeile und:

Binom(n,k+1)=Binom(n,k)*(n-k)/(k+1)

---

"schon die 2. Zeile ist falsch,"

Nope.

https://de.wikipedia.org/wiki/Pochhammer-Symbol

Stichwort: fallende Faktorielle.

Was hier wirklich gemeint ist, ist  nicht klar ohne die Vorlesung zu kennen, fallende Faktorielle macht aber deutlich mehr Sinn: Das Ergebnis ist nicht so häßlich.

---

Meine Aussage zur 2. Zeile bezieht sich auf diese Quelle, wo über 300 Funktionen für Wissenschaftler definiert sind:  http://functions.wolfram.com/GammaBetaErf/Binomial/27/01/0004/

Binomial[n, k] = Pochhammer[n - k + 1, k]/Gamma[k + 1] = Pochhammer[n - k + 1, k]/k!

Rest (die unterschiedlichen Interpretationen) werde ich oben kommentieren.

---

Ich hätte auch noch diese Quelle:
https://en.wikipedia.org/wiki/Pochhammer_symbol

Die spricht für meine Auffassung gegen deine.

"Rest (die unterschiedlichen Interpretationen) werde ich oben kommentieren. "
Ganz ehrlich, das finde ich eine Unverschämtheit.
Du bezeichnest meine Antwort hier als falsch, wohl um meine Antwort zu diskreditieren. (Und ich ich habe hier bereits Quellen genannt, die meine These stützen)
Bei deiner Antwort, wohl ujm deine Antwort aufzuwerten, nimmst du es dann halb zurück nur um mein Ergebnis zu klauen.

---

Was Du vorgerechnet hast, passt zu FactorialPower[x,n]

http://reference.wolfram.com/language/ref/FactorialPower.html  mit anderer Schreibweise: 

---

Solch gefühlsbelastete Begriffe wie "diskreditieren", "klauen" gehören nicht in eine sachliche mathematische Abhandlung und ich werde auch nicht weiter darauf eingehen.

Warum ich das Wort "falsch" vor über 15 Stunden (als ich noch nichts von der Existenz FactorialPower wußte)

verwendete, habe ich bereits ausgeführt.

Ich bin Dir sogar dankbar, dass Du mit Deiner anderen Interpretation auf die Uneindeutigkeit der Schreibweise gebracht hast.

Du selbst hast ja auch erst vor 5 h zugegeben: "Was hier wirklich gemeint ist, ist  nicht klar ohne die Vorlesung zu kennen..."

Einen sauberen Ausweg für eine exakte Bezeichnung der beiden unterschiedlichen Funktionen Pochhammer(x,n) und FactorialPower[x,n] hatte ich bereits vorgeschlagen.

---

Danke das ihr beide soviel mühe gegeben habt, die Frage zu beantworten und tut mir auch leid, das wegen der Frage so viel Spannung geherrscht hat. Wir machen es mit Factorial, aber trotzdem vielen dank an euch beiden; "hyperG" und "Gastjd132".

---

@hyperG: "Warum ich das Wort "falsch" vor über 15 Stunden (als ich noch nichts von der Existenz FactorialPower wußte)"

Du hast also als "Falsch" geschrieben aufgrund ungenügender Kenntnisse..

Denn wäre es aber nur anständig, insbesondere im Sinne "sachlicher mathematische Abhandlung", dieses "Falsch" auch an der Stelle an der es getätigt wurde zurückzunehmen an nicht woanders.

@MsArray: Gern Geschehen. Und du kannst für das Verhalten von hyperG nichts. Dafür ist er/sie selbst verantwortlich.