Pascalsches Dreieck berechnen

Wissenschaft Mathematik
#1

Hallo,

für eine Schulaufgabe muss ich im PC mithilfe einer selbstprogrammierten Funktion das Pascalsche Dreieck berechnen. Ist auch kein größeres Problem.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
…

Das ganze benötige ich, um mir eine Gauss-Filtermaske zu berechnen. Sagen wir mal, die Filtermaske arbeitet mit einem 5’er-Kern, dann muss ich aus der obenstehenden Pyramide lediglich die fünfte Zeile berechnen - also 1 4 6 4 1 - um daraus die Gaussfiltermaske zu berechnen.

Nun zu meinem Problem: Ich berechne die Pyramide mit einer simplen Formel. Eine beliebige Zahl lässt sich berechnen (x gibt die Spaltenposition und y die Zeile an), indem ich rechne Wert(x,y) = Wert(x-1,y-1) + Wert(x,y-1) (natürlich außer für die erste und letzte Position einer Zeile - aber deren Wert ist ja sowieso bekannt).

So weit, so gut - der Haken an der Formel ist nur, das ich die Reihe darüber kennen muss, um sie auszuführen. Das wiederum bedeutet, das ich die komplette Pyramide berechnen muss (denn um die Reihe über der zu berechnenden Reihe zu berechnen, muss ich ja die Reihe über der Reihe, die ich berechnen will, berechnen, usw.).

Von daher: Kennt jemand einen einfacheren Weg, um eine bestimmte Zeile in einem Pascalschen Dreieck zu berechnen? Und kann ihn so erklären, das sogar ein Mathe-Laie wie ich das verstehe?

Danke!

JM

#2

Hallo,

Kennt jemand einen einfacheren Weg, um eine
bestimmte Zeile in einem Pascalschen Dreieck zu berechnen?

weißt du, dass die Einträge im Pascalschen Dreieck die Binomialkoeffizienten (n über k) sind? (n: Zeile, k: „Spalte“)
http://de.wikipedia.org/wiki/Binomialkoeffizient#Rek…

Dann weißt du bestimmt, dass man Binomialkoeffizienten mit Hilfe von Fakultäten (n! = 1*2*3*…*(n-1)*n) so berechnen kann:

(n über k) = n! / (k! * (n-k)!)

Das wäre aufgrund der vielen Multiplikationen und Divisionen immer noch sehr aufwendig, außerdem kürzt sich der Großteil der Faktoren weg; berechnet man nur die Faktoren, die sich nicht wegkürzen (und in einer cleveren Reihenfolge, damit es nur ganzzahlige Ergebnisse gibt), kommt man auf so einen Algorithmus: http://de.wikipedia.org/wiki/Binomialkoeffizient#Alg…

Jetzt könntest du hingehen und mit diesem Algorithmus die einzelnen Einträge deiner Zeilen berechnen. Es geht aber noch besser, da du die ganze Zeile brauchst: Die Einträge einer Zeile, die nebeneinander stehen, sind ja nicht unabhängig voneinander. Wenn du mal (n über k+1) als Quotient aus Fakultäten schreibst (mach’s mal) und versuchst, (n über k) wiederzuentdecken, kommst du auf so ein Ergebnis:

(n über k+1) = (n über k) * (n-k) / (k+1)

(n über 0) ist immer 1; mit der Formel kannst du den Eintrag rechts davon berechnen, also (n über 1), dann den nächsten Eintrag, etc.

Beispiel:

(5 über 0) = 1
(5 über 1) = (5 über 0) * 5 / 1 = 1 * 5 / 1 = 5
(5 über 2) = (5 über 1) * 4 / 2 = 5 * 4 / 2 = 10
(5 über 3) = (5 über 2) * 3 / 3 = 10 * 3 / 3 = 10
…

Das sollte ziemlich effizient sein. (Dann würde ich noch die Symmetrie ausnutzen und nur bis zur Hälfte rechnen.)

Viel Erfolg,

Andreas

#3

Kennt jemand einen einfacheren Weg, um eine
bestimmte Zeile in einem Pascalschen Dreieck zu berechnen?

weißt du, dass die Einträge im Pascalschen Dreieck die
Binomialkoeffizienten (n über k) sind? (n: Zeile, k: „Spalte“)

Hmm, falls das für einen „Mathe-Laien“ doch zu heftig war und du die Binomialkoeffizienten noch nicht kennst, brauchst du vorläufig nur zu wissen, dass ich mit der Schreibweise „(n über k)“ dasselbe meine wie du mit „Wert(k,n)“.

Andreas

#4

hi,

für eine Schulaufgabe muss ich im PC mithilfe einer
selbstprogrammierten Funktion das Pascalsche Dreieck
berechnen. Ist auch kein größeres Problem.

welche art von software solls denn sein?
das ganze geht mit jeder tabellenkalkulation (openOffice calc z.b.; von mir aus auch excel). hat den vorteil, dass du keine faktoriellen berechnen musst, die schnell sehr groß werden.

du lässt z.b. in der spalte A viele 1en eintragen.
du schreibst in zelle B2 „=A1+B1“ und füllst diese formel nach unten und rechts aus.

du kannst dann mit der index-funktion aus dem sich ergebenden zahlenschema eine geeignete zeile auswählen: +
=INDEX(bereich;zeile;spalte)

hth
m.

#5

Hi,

welche art von software solls denn sein?
das ganze geht mit jeder tabellenkalkulation (openOffice calc
z.b.; von mir aus auch excel). hat den vorteil, dass du keine
faktoriellen berechnen musst, die schnell sehr groß werden.

du lässt z.b. in der spalte A viele 1en eintragen.
du schreibst in zelle B2 „=A1+B1“ und füllst diese formel nach
unten und rechts aus.

Nein, ich programmiere es in C++. Ist aber letztlich auch egal, weil die Lösung allgemeiner Natur ist. Deine Excel-Lösung hilft mir da natürlich nicht weiter, da sie nur das macht, was ich selber bereits weiß :wink:. Trotzdem danke für den Vorschlag.

#6

Hallo Andreas,

weißt du, dass die Einträge im Pascalschen Dreieck die
Binomialkoeffizienten (n über k) sind? (n: Zeile, k: „Spalte“)
http://de.wikipedia.org/wiki/Binomialkoeffizient#Rek…

Ähm, nein. Ich weiß nicht was ein Binomialkoeffizient ist. Die Erklärung in wikipedia hilft mir auch nicht weiter, die verstehe ich nicht. Ich bin ein absoluter Mathe-Laie.

(n über k+1) = (n über k) * (n-k) / (k+1)

(n über 0) ist immer 1; mit der Formel kannst du den Eintrag
rechts davon berechnen, also (n über 1), dann den nächsten
Eintrag, etc.

Beispiel:

(5 über 0) = 1
(5 über 1) = (5 über 0) * 5 / 1 = 1 * 5 / 1 = 5
(5 über 2) = (5 über 1) * 4 / 2 = 5 * 4 / 2 = 10
(5 über 3) = (5 über 2) * 3 / 3 = 10 * 3 / 3 = 10

Die Erklärung habe ich leider nicht verstanden, die Formel hingegen schon. Dankeschön! :smile:

#7

hi,

Nein, ich programmiere es in C++. Ist aber letztlich auch
egal, weil die Lösung allgemeiner Natur ist. Deine
Excel-Lösung hilft mir da natürlich nicht weiter, da sie nur
das macht, was ich selber bereits weiß :wink:. Trotzdem danke für
den Vorschlag.

dann wie es andreas schon gesagt hat:
das schema

 1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 1 5 10 10 5 1

usw. bekommst du auch als binomialkoeffizienten über die faktoriellen.

die 5. zeile (1 4 6 4 1) sind die zahlen
(4 über 0) = 1, (4 über 1) = 4, (4 über 2) = 6, (4 über 3) = 4 und (4 über 4) = 1
allgemein gilt: (n über 0) = 1, (n über n) = 1, (n über 1) = n,
(n über k) = (n über n-k)

und (n über k) = n! / (k! (n-k)!)

also z.b.
(4 über 2) = 4! / (2! 2!) = 4.3.2.1 / ((2.1).(2.1)) = 6

und so kann man sie berechnen ohne auf die zeilen davor einzugehen. nachteil: du bekommst sehr schnell sehr große teilergebnisse (für den zähler); du bekommst für den zähler schneller speicherüberlauf als für den gesamten binomialkoeffizienten, der wesentlich kleiner ist. du kannst dir evtl. damit behelfen nicht
(n über k) = n! / (k! (n-k)!)
zu berechnen, sondern durch (n-k)! zu kürzen, dann hast du:
(n über k) = n.(n-1).(n-2)…(n-k+1) / k!

hth
m.

#8

OT: Faktoriellen?
Hallo Michael!

hat den vorteil, dass du keine
faktoriellen berechnen musst, die schnell sehr groß werden.

Hab gerade herausgefunden, dass das in Österreich tatsächlich „Faktorielle“ heißt. War echt erstaunt! Für alle, die diesen Austriazismus nicht kennen und die auch das englische „factorial“ nicht verstehen (also wohl für die meisten Bundesrepublikaner) ist der Begriff „Fakultät“ hinzuzufügen. Ich werd demnächst, da ich das nun weiß und hier auch Österreicher lesen, auf alle Fälle immer beide Wörter benutzen, wenn ich etwas erkläre, wo Fakultäten / Faktoriellen vorkommen.

Liebe Grüße
Immo