Herleitung Pascalsches Dreieck

22.09.2011, 23:30

Nord.Kind

Herleitung Pascalsches Dreieck

Meine Frage:
Moinsen!

Meine Frage bezieht sich auf die auf Wikipedia genannte Herleitung zum Pscalschen Dreieck.

Zitat:"Das pascalsche Dreieck ist eine geometrische Darstellung der Binomialkoeffizienten $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ . Sie sind im Dreieck derart angeordnet, dass jeder Eintrag die Summe der zwei darüberstehenden Einträge ist. Dieser Sachverhalt wird durch die Gleichung

$\begin{eqnarray*} \begin{pmatrix} n +1 \\ k + 1 \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k + 1 \end{pmatrix} \end{eqnarray*}$

beschrieben. Dabei kann die Variable n als Zeilenindex und k als Spaltenindex interpretiert werden, wobei die Zählung mit Null beginnt (also erste Zeile n = 0, erste Spalte k = 0).

____________________________ $\begin{eqnarray*} \begin{pmatrix} 0 \\ 0 \end{pmatrix} \end{eqnarray*}$

___________________________ $\begin{eqnarray*} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{eqnarray*}$

________________________ $\begin{eqnarray*} \begin{pmatrix} 2 \\ 0 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 2 \\ 1 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 2 \\ 2 \end{pmatrix} \end{eqnarray*}$

______________________ $\begin{eqnarray*} \begin{pmatrix} 3 \\ 0 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 3 \\ 1 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 3 \\ 2 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 3 \\ 3 \end{pmatrix} \end{eqnarray*}$

____________________ $\begin{eqnarray*} \begin{pmatrix} 4 \\ 0 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 4 \\ 1 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 4 \\ 2 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 4 \\ 3 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 4 \\ 4 \end{pmatrix} \end{eqnarray*}$

__________________ $\begin{eqnarray*} \begin{pmatrix} 5 \\ 0 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 5 \\ 1 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 5 \\ 2 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 5 \\ 3 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 5 \\ 4 \end{pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} 5 \\ 5 \end{pmatrix} \end{eqnarray*}$

Daraus ergibt sich dann laut Wiki das Pascalsche Dreieck:

___________________________ $\begin{eqnarray*} 1 \end{eqnarray*}$

__________________________ $\begin{eqnarray*} 1, 1 \end{eqnarray*}$

_________________________ $\begin{eqnarray*} 1, 2, 1 \end{eqnarray*}$

________________________ $\begin{eqnarray*} 1, 3, 3, 1 \end{eqnarray*}$

_______________________ $\begin{eqnarray*} 1, 4, 6, 4, 1 \end{eqnarray*}$

______________________ $\begin{eqnarray*} 1, 5, 10, 10, 5, 1 \end{eqnarray*}$

Meine Ideen:

Also sollte sich die untere Pyramide aus der obigen Formel + die obere Pyramide ergeben.

Tut sie aber meiner Meinung nach nicht, denn die untere Pyramide ergibt sich meiner Ansicht nach aus der oberen Pyramide + $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n- k)!} \end{eqnarray*}$

Es gillt doch $\begin{eqnarray*} \begin{pmatrix} n +1 \\ k + 1 \end{pmatrix} = \frac{(n+1)!}{(k+1)!((n+1)- (k+1))!} \end{eqnarray*}$ oder?

Wie kann man dann durch die Formel auf die Pyramide schließen?
Mir ist zwar aufgefallen, dass sich durch diese Formel in Verbindung mit einer Stelle aus der obigen Pyramide immer die niedriger liegende Zahl in der unteren Pyramide ergibt, allerdings nur eine und grenzen meist zwei Zahlen an eine obige.
Z.B. folgt auf $\begin{eqnarray*} \begin{pmatrix} 3 \\ 2 \end{pmatrix} \end{eqnarray*}$ nach obiger Logik die 4, aber nicht die 6.

Wie ist die obige Definition also zu verstehen?

Ps:Wenn mir jmd sagen kann, wie man Leerstellen einbaut bin ich ganz Ohr Augenzwinkern

Latex Leerzeichen scheinen auch nicht zu gehen.
Übrigens genauso wie das einfügen von Fettschrift etc. eine kurze Suche im Forum hat nichts gebracht und Befehle wie <b> scheinen auch nicht zu funktionieren =/

23.09.2011, 09:20

lgrizu

Auf diesen Beitrag antworten »

RE: Herleitung Pascalsches Dreieck
Der Beweis kann per Induktion geführt werden, und $\begin{eqnarray*} \begin{pmatrix} 3 \\ 2 \end{pmatrix}=3 \end{eqnarray*}$ , das ist der dritte Eintrag in der vierten Spalte.

Man kann das auch geschickt ausrechnen:

$\begin{eqnarray*} \binom {n+1}{k+1}= \binom {n}{k} + \binom{n}{k+1} \end{eqnarray*}$ ist äquivalent zu:

$\begin{eqnarray*} \binom {n+1}{k+1} - \binom {n}{k} = \binom{n}{k+1} \end{eqnarray*}$

Nun kann man anfangen zu rechnen:

$\begin{eqnarray*} \frac{(n+1)!}{(k+1)! \cdot ((n+1)-(k+1))!}-\frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

$\begin{eqnarray*} =\left( \frac{n+1}{k+1} -1\right) \cdot \frac{n!}{k! \cdot (n-k) \cdot (n-k-1)!} \end{eqnarray*}$

$\begin{eqnarray*} = \frac{n-k}{k+1} \cdot \frac{1}{n-k} \cdot \frac{n!}{k! \cdot (n-(k+1)!}=\frac{n!}{(k+1) \cdot k! \cdot (n-(k+1))!}=\binom{n}{k+1} \end{eqnarray*}$

23.09.2011, 10:38

Nord.Kind

Auf diesen Beitrag antworten »

p89fq3
Mh ok...

Ich gebe nun die Koeffizienten in die untere Formel ein um die entsprechenden Werte für das Pascalsche Dreieck zu bekommen.

Es folgt:

$\begin{eqnarray*} \frac{n!}{(k+1)\cdot k!\cdot (n-(k+1))!} = \frac{3!}{(2+1)\cdot 2!\cdot (3-(2+1))!}= \frac{3\cdot2\cdot1}{3\cdot 2\cdot1\cdot1}=1 \end{eqnarray*}$

Es sollte doch 3 rauskommen oder nicht?

Beste Grüße!

23.09.2011, 10:49

lgrizu

Auf diesen Beitrag antworten »

RE: p89fq3
Wieso sollte da 3 herauskommen? verwirrt

Das bedeutete ja, dass gilt $\begin{eqnarray*} \binom{3}{2}= \binom{3}{2+1} \end{eqnarray*}$ , also im Endeffekt $\begin{eqnarray*} \binom{n}{k}= \binom{n}{k+1} \end{eqnarray*}$ , aber das sagt die Gleichung nicht aus.

Edit: Betrachte doch einmal das dritte Element in der vierten Zeile, dieses ist:

$\begin{eqnarray*} 3=\binom{3}{2}= \binom{2+1}{1+1} \end{eqnarray*}$ , also k=1 und n=2.

Wir setzen das einmal ein und wir wissen, dass gilt 3=2+1, nun ist $\begin{eqnarray*} 2=\binom{2}{1} \end{eqnarray*}$ und $\begin{eqnarray*} 1= \binom{2}{2} \end{eqnarray*}$ .

Wir erhalten also $\begin{eqnarray*} 2+1= \binom{2}{1} + \binom{2}{2}=3=\binom{3}{2}=\binom{2+1}{1+1} \end{eqnarray*}$

23.09.2011, 11:33

Nord.Kind

Auf diesen Beitrag antworten »

Vielen Dank erstmal für diene Hilfe!
_____________________________________________________
Erste Frage:
Mh...anscheinend habe ich die Defininition nicht richtig verstanden....

Aus dem Text von Wikipedia "Dieser Sachverhalt wird durch die Gleichung

$\begin{eqnarray*} \begin{pmatrix} n +1 \\ k + 1 \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k + 1 \end{pmatrix} \end{eqnarray*}$

beschrieben. Dabei kann die Variable n als Zeilenindex und k als Spaltenindex interpretiert werden, wobei die Zählung mit Null beginnt (also erste Zeile n = 0, erste Spalte k = 0).
"

Geht für mich hervor, dass die Formel für jede Stelle der Pyramide durch den Zeilenindex n und den Spaltenindex k einen Wert definiert.

Also bin ich so vorgegangen, dass ich mir in der oberen Pyramide eine Zeile n mit der Spalte k ausgesucht habe, diese in die Formel eingegeben habe und erwartet habe, dass mir daraus die entsprechende Zahl für die zweite Pyramide geliefert würde.

Also in meinem Beispiel n=3, k=2. Daraus sollte dann die 3 folgern...

unglücklich

Wenn ich dich richtig verstehe ist das aber nicht der Fall.

Stattdessen trage ich die Zeilenzahl-1, sowie die Spaltenzahl-1 ein, um dann wieder auf das entsprechende Ergebnis für die zweite Pyramide zu kommen.

Also quasi $\begin{eqnarray*} n_{1}+1=n \end{eqnarray*}$ und $\begin{eqnarray*} k_{1}+1=k \end{eqnarray*}$ .

Was also verstehe ich falsch? Hab da wohl irgendwo was falsch verknüpft unglücklich

_________________________________________________________________
Zweite Frage: Habe ich mich beim Eintragen der Werte in deine Formel verrechnet oder käme so wirklich 1 raus?
_______________________________________________________________
Dritte Frage:

Mh und dazu kommt, dass ich deine Umformung nicht ganz verstehe...ok das ist untertrieben Augenzwinkern

Ich verstehe sie eigentlich gar nich hehe.

$\begin{eqnarray*} <br /> \begin{pmatrix}\frac{n+1}{k+1}-1\end{pmatrix}\cdot \frac{n!}{k!\cdot (n-k)!\cdot (n-k-1)!} \end{eqnarray*}$ ist doch ausmultipliziert $\begin{eqnarray*} \frac{n\cdot n!+n!}{(k\cdot k!\cdot (n-k)!\cdot (n-k-1)!)+(k!\cdot (n-k)!\cdot (n-k-1)!)} -\frac{n!}{k!\cdot (n-k)!\cdot (n-k-1)!} \end{eqnarray*}$ oder?

Beste Grüße!

23.09.2011, 11:36

lgrizu

Auf diesen Beitrag antworten »

Warte bitte kurz, ich bin dabei zu tippen, dauert etwas, das vollständig auszuführen. Augenzwinkern

$\begin{eqnarray*} \binom{n+1}{k+1}- \binom{n}{k}=\frac{(n+1)!}{(k+1)! \cdot ((n+1)-(k+1))!}-\frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

Das sollte klar sein. Nun weiter, wir verwenden nun, dass $\begin{eqnarray*} ((n+1)-(k+1))=n+1-k-1=n-k \end{eqnarray*}$ ist, erhalten also:

$\begin{eqnarray*} =\frac{(n+1)!}{(k+1)! \cdot (n-k)!}-\frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

Nun nutzen wir, dass gilt $\begin{eqnarray*} (n+1)!= (n+1) \cdot n! \end{eqnarray*}$ und $\begin{eqnarray*} (k+1)!=(k+1) \cdot k! \end{eqnarray*}$ und erhalten:

$\begin{eqnarray*} \frac{(n+1) \cdot n!}{(k+1) \cdot k! \cdot (n-k)!}-\frac{n!}{k! \cdot (n-k)!}= \frac{n+1}{k+1} \cdot \frac{n!}{k! \cdot (n-k)!}-\frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

Wir wenden das Distributivgesetz an:

$\begin{eqnarray*} =\left( \frac{n+1}{k+1} -1\right) \cdot \frac{n!}{k! \cdot (n-k) !} \end{eqnarray*}$

Nun erzeugen wir Nennergleichheit in der Klammer:

$\begin{eqnarray*} =\left( \frac{n+1}{k+1} -\frac{k+1}{k+1} \right) \cdot \frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

Wir fassen den Bruch in der Klammer zusammen:

$\begin{eqnarray*} = \frac{n-k}{k+1} \cdot \frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

Nun benutzen wir, dass gilt $\begin{eqnarray*} (n-k)!=(n-k) \cdot (n-k-1)!=(n-k) \cdot (n-(k+1))! \end{eqnarray*}$ und erhalten:

$\begin{eqnarray*} = \frac{n-k}{k+1} \cdot \frac{n!}{(n-k) \cdot k! \cdot (n-(k+1)!} \end{eqnarray*}$

Wir kürzen zum Schluss noch (n-k) heraus und haben:

$\begin{eqnarray*} =\frac{n!}{(k+1) \cdot k! \cdot (n-(k+1))!}=\binom{n}{k+1} \end{eqnarray*}$

So viel zu der ausführlichen Rechnung mit Erläuterung.

Die Zählung beginnt bei 0 bedeutet, dass die erste Zeile die Nullzeile ist, also das Pascalsche Dreieck mit dem Binominalkoeffizienten $\begin{eqnarray*} \binom{0}{0} \end{eqnarray*}$ beginnt.

Der Zusammenhang, der sich ergibt kommt dadurch zustande, dass die Summe der beiden Elemente, die "schräg oberhalb" eines Elements sind, das Element ergibt.

Nehmen wir zum Beispiel einmal ein Element heraus, das Element $\begin{eqnarray*} 10=\binom{5}{2} \end{eqnarray*}$ .

Hier wäre dann n=4 und k=1, Die beiden darüber liegenden Elemente sind $\begin{eqnarray*} 4=\binom{4}{1} \end{eqnarray*}$ und $\begin{eqnarray*} 6=\binom{4}{2} \end{eqnarray*}$

Nun ist $\begin{eqnarray*} 10=4+6 \end{eqnarray*}$ , also $\begin{eqnarray*} 10=\binom{4+1}{1+1}=\binom{4}{1}+\binom{4}{1+1} \end{eqnarray*}$ .

Das kann man für jedes beliebige Element des Pascalschen Dreiecks so nachvollziehen.

Zitat:

Original von Nord.Kind

$\begin{eqnarray*} <br /> \begin{pmatrix}\frac{n+1}{k+1}-1\end{pmatrix}\cdot \frac{n!}{k!\cdot (n-k)!\cdot (n-k-1)!} \end{eqnarray*}$ ist doch ausmultipliziert $\begin{eqnarray*} \frac{n\cdot n!+n!}{(k\cdot k!\cdot (n-k)!\cdot (n-k-1)!)+(k!\cdot (n-k)!\cdot (n-k-1)!)} -\frac{n!}{k!\cdot (n-k)!\cdot (n-k-1)!} \end{eqnarray*}$ oder?

Das stimmt, aber etwas umständlich notiert, denn im Zähler steht $\begin{eqnarray*} n \cdot n! + n!=(n+1) \cdot n!=(n+1)! \end{eqnarray*}$ .

Im Nenner kann man sortieren:

$\begin{eqnarray*} (k+1) \cdot k!=(k+1)! \end{eqnarray*}$ und $\begin{eqnarray*} (n-k) \cdot (n-k-1)!=(n-k)! \end{eqnarray*}$

23.09.2011, 21:19

Nord.Kind

Auf diesen Beitrag antworten »

Ahhh vielen Dank, jetzt wird einiges klarer Augenzwinkern

Dankeschön!

Den Zusammenhang hatte ich ja irgendwie geahnt=)

Zitat:

Originial von Nord.Kind

Mir ist zwar aufgefallen, dass sich durch diese Formel in Verbindung mit einer Stelle aus der obigen Pyramide immer die niedriger liegende Zahl in der unteren Pyramide ergibt, allerdings nur eine und grenzen meist zwei Zahlen an eine obige.

Jetzt bin ich bei der obligatorischen Überprüfung über etwas anderes gestolpert!

Und zwar ergibt sich aus der nun zu genüge beschriebenen Formel ja quasi " die Zahl unter den genommenen Tulpel rechts".
Oder umgekehrt

Zitat:

Originial von lgrizu

Der Zusammenhang, der sich ergibt kommt dadurch zustande, dass die Summe der beiden Elemente, die "schräg oberhalb" eines Elements sind, das Element ergibt.

Wie bereits gezeigt lässt sich also aus n=4 , k=1 eingesetzt in genannte Formel auf $\begin{eqnarray*} \begin{pmatrix}5 \\ 2 \end{pmatrix} \end{eqnarray*}$ schließen.

Das hieße ja, dass n=4 , k=4 über die Formel auf $\begin{eqnarray*} \begin{pmatrix} 5 \\ 5 \end{pmatrix} \end{eqnarray*}$ schließen lassen müsste.

Dabei bin ich auf folgendes gestoßen:
$\begin{eqnarray*} \binom{4+1}{4+1}=\binom{4}{4}+\binom{4}{4+1}=\frac{4!}{(4-4)!4!} + \frac{4!}{(4-5)!5!}=1 + \frac{4!}{(-1)!5!} \end{eqnarray*}$ .

Wie gehe ich mit -1! um?

23.09.2011, 21:39

lohrio

Auf diesen Beitrag antworten »

binomialkoeffizient n über k ist als 0 definiert falls k negativ oder k > n smile

das sollte deine frage lösen smile

Was übrigens über die rechenregeln zum binomialkoeffizienten zum gleichen ergebnis führt

24.09.2011, 12:58

Nord.Kind

Auf diesen Beitrag antworten »

Naja, hier ist ja weder n noch k negativ, noch k>n =)

Aber beim Umformen der Gleichung gelangt man auf 1!.

________________________________________________________

Frage: Wie ist eine negative Fakultät definiert?

Beste Grüße Augenzwinkern

Neue Frage »

Antworten »

Herleitung Pascalsches Dreieck

Verwandte Themen