Berechnung vom Binomialkoeffizient?

[Durcairion]

Hi, ich muss in Pseudocode (C++) folgende Aufgabe realisieren:

http://img425.imageshack.us/img425/796/webtech9ym.th.jpg (http://img425.imageshack.us/my.php?image=webtech9ym.jpg)

Ich verstehe 0,000 von der Mathematischen Formel :)

Kann mir vll. mal ein Mathegenie unter euch erklären wobei es dabei geht?

Also die Formale für normale Menschen verständlich darstellen? :)

Wäre sehr dankbar über Hilfe :)

[Korrom]

EDIT: Aaargh! Das Forum hat meine Formatierungen gefressen! Ich bekomm's auch nicht hin. Scheint so, als würden "unnötige" Leerzeichen entfernt werden. Sorry....

Der Binomialkoeffizient ist ein schneller Weg zur Konstruktion der Koeffizienten der Binompotenzen in binomischen Formeln n-ten Grades (so daß man es nicht über das Pascalesche Dreieck machen muß). Ausgeschrieben sieht der Binomialkoeffizient dann so aus:

/n\ n!
| | = -----------
\k/ k!*(n-k)!

Deine Rekursionsformel folgt direkt aus dem Aufbau des Pascaleschen Dreiecks:

n=0 0
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 5 4 1

Schreibt man hier die Binomialkoeffizienten hin, dann sieht das so aus (Ausschnitt, Bin. ohne Klammern geschrieben):

n=1 1 1
0 1
n=2 2 2 2
0 1 2
\_/
n=3 3 3 3 3
0 1 2 3

Wo ich die Markierung dazwischengemalt habe siehst du, daß hier
2 und 2 über 3 stehen, als ausgerechnete Zahlen also 2+1(oben)=3(unten)
1 2 2

Sie sieht es also anschaulich aus, wie man mit deiner Rekursionsformel einen bestimmten Binomialkoeffizienten ausrechnet (die Formel ist ja in deinem Bild drin, deshalb bastle ich sie hier nicht nochmal hin).

Mit dem Binomialkoeffizient lassen sich z.B. Probleme aus der Kombinatorik lösen, bei denen Teilmengen mit k Elementen aus Mengen mit n Elementen ohne zurücklegen gezogen werden.

So, ich hoffe die Sache ist einigermaßen klar geworden. Wenn nicht: fragen.

[Durcairion]

Ok, vielen Dank habe die Aufgabe gelöst!