Abgeschnittenes Pascalsches Dreieck

28.10.2014, 12:50

Voldi

Abgeschnittenes Pascalsches Dreieck

Guten Morgen!

Im Zuge einer Übungsaufgabe, die ich ein bisschen abstrahiert habe, bin ich auf folgendes Problem gestoßen:

Nehmen wir ein abgewandeltes Pascalsches Dreieck. Abgewandelt in diesem Fall: Wir ziehen eine senkrechte Linie von $\begin{eqnarray*} \begin{pmatrix} 2 \\ 0 \end{pmatrix} \end{eqnarray*}$ runter und alle Werte links davon sind 0.
Kleine Skizze dazu befindet sich im Dateianhang, konnte hier keine URL posten.
Die orangenen Ziffern stehen für die Zeilen, die grünen für die Spalten.

Nun zu meinem "Problem":
Ich hab mich gefragt, ob es eine einheitliche Formel zur Berechnung einzelner Elemente gibt.
Die links fehlenden Zahlen haben ja ab Zeile 3 auch Auswirkungen auf die Zahlen rechts der Grenze.
Ich hab mir also ein paar der Zahlen angeschaut "Richtiges Dreieck" minus "mein Dreieck", um zu schauen wie die Differenz aussieht.

Und in der Tat hatten diese Zahlen ein bestimmtes Muster - in Zeile 3 waren ja 12 Spalten betroffen, die jeweils die Differenz $\begin{eqnarray*} \begin{pmatrix} 4 \\ 0 \end{pmatrix} \end{eqnarray*}$ bis $\begin{eqnarray*} \begin{pmatrix} 15 \\ 0 \end{pmatrix} \end{eqnarray*}$ (also alle 1) aufwiesen.
In Zeile 4 waren es nur noch 11 Spalten, die jeweils als Differenz $\begin{eqnarray*} \begin{pmatrix} 6 \\ 1 \end{pmatrix} \end{eqnarray*}$ bis $\begin{eqnarray*} \begin{pmatrix} 16 \\ 1 \end{pmatrix} \end{eqnarray*}$ aufwiesen.
Noch zur Zeile 5: 10 Spalten mit Differenz $\begin{eqnarray*} \begin{pmatrix} 8 \\ 2 \end{pmatrix} \end{eqnarray*}$ bis $\begin{eqnarray*} \begin{pmatrix} 17 \\ 2 \end{pmatrix} \end{eqnarray*}$ .
Ich denke, das Muster ist offensichtlich. Dies setzte sich so fort.

Ganz im speziellen möchte ich auf die 13. Spalte hinweisen - die Differenz von den "richtigen" Pascal-Zahlen zu "meinen" waren dort aufsteigend von Zeile 3: $\begin{eqnarray*} \begin{pmatrix} 15 \\ 0 \end{pmatrix} \end{eqnarray*}$ , $\begin{eqnarray*} \begin{pmatrix} 16 \\ 1 \end{pmatrix} \end{eqnarray*}$ , $\begin{eqnarray*} \begin{pmatrix} 17 \\ 2 \end{pmatrix} \end{eqnarray*}$ , ... , $\begin{eqnarray*} \begin{pmatrix} 26 \\ 11 \end{pmatrix} \end{eqnarray*}$ .
Wenn ich also bspw. wissen möchte, was in "meinem" Dreieck im Feld $\begin{eqnarray*} \begin{pmatrix} 26 \\ 12 \end{pmatrix} \end{eqnarray*}$ steht, muss ich bloß $\begin{eqnarray*} \begin{pmatrix} 26 \\ 12 \end{pmatrix} \end{eqnarray*}$ - $\begin{eqnarray*} \begin{pmatrix} 26 \\ 11 \end{pmatrix} \end{eqnarray*}$ (meine eben gezeigte Differenz) rechnen.

Nur weiß ich leider nicht, wieso das so ist. Also kombinatorisch-logisch, meine ich. x__x
Die Zahlen im Pascal-Dreieck geben ja quasi an, auf wie viele verschiedenen Wegen man eine Zahl erreichen kann, wenn man von der Wurzel aus immer Schritte nach links unten oder nach rechts unten machen kann.
Mein Dreieck soll also zeigen, auf wie viele verscheidene Wege man ein Feld erreichen kann, wenn man die Linie nicht "überqueren" darf. Wo kommt also diese Differenz (im Beispiel $\begin{eqnarray*} \begin{pmatrix} 26 \\ 11 \end{pmatrix} \end{eqnarray*}$ ) her? Das muss demnach ja die Anzahl Wege sein, die die Linie überquert hat. Aber wie kommt man da (kombinatorisch) drauf? x____x

Danke im Voraus, ich hoffe irgendjemand konnte meinem Kauderwelsch folgen. Hammer

28.10.2014, 13:26

HAL 9000

Auf diesen Beitrag antworten »

Es ist ein wenig schwierig, deinen Beispielen zu folgen:

Wenn man im Pascalschen Dreieck von "Zeilen" spricht, dann meint man i.d.R. waagerechte Zeilen - du meinst da aber anscheinend abweichend davon Diagonalen (von links oben nach rechts unten?), ähnlich wahrscheinlich dann deine Spalten (von rechts oben nach links unten?).

28.10.2014, 13:30

Voldi

Auf diesen Beitrag antworten »

Stimmt, ist ein bisschen verwirrend, aber ja, richtig. Meine Notizzettel sind noch verworrener, sonst hätt ich die auch hochgeladen.

Mit den Zeilen / Spalten hab ich mich an die n über k Notation gehalten, war vielleicht etwas verwirrend. Dazu die farbigen Zahlen am Rand. Ich wollte gut ablesen können, welche Zahl (also in der n über k Form) in welchem Feld liegen sollte (nach dem Pascal-Dreieck).

28.10.2014, 13:37

HAL 9000

Auf diesen Beitrag antworten »

Also gut: Das ganze Palaver eingedampft willst du also sagen, dass in deiner Zeile $\begin{align*} m\geq 3 \end{align*}$ an Spaltenposition $\begin{align*} n\geq m-2 \end{align*}$ die Zahl

$\begin{align*} a_{m,n} = \binom{m+n}{m} - \binom{m+n}{m-3} \end{align*}$

steht? Das lässt sich per vollständiger Induktion beweisen, dabei darf gemäß deinem Konstruktionsprinzip für $\begin{align*} m\geq 3 \end{align*}$ folgende "abgeschnittene" Pascal-Rekursion verwendet werden:

$\begin{align*} a_{m,n} = \begin{cases} a_{m,n-1}+a_{m-1,n} & \;\mbox{falls}\, n\geq m-1 \\ a_{m-1,n} & \;\mbox{falls}\, n=m-2 \\ 0 &\;\mbox{sonst} \end{cases} \end{align*}$ .

28.10.2014, 15:24

Voldi

Auf diesen Beitrag antworten »

In der Induktion zeige ich also erst, dass $\begin{eqnarray*} a_{3,1} \end{eqnarray*}$ korrekt ist, und dann, dass $\begin{eqnarray*} a_{m+1,n} = \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix} - \begin{pmatrix} m+n+1 \\ m-2 \end{pmatrix} \end{eqnarray*}$ , indem ich die linke Seite durch $\begin{eqnarray*} a_{m,n} \end{eqnarray*}$ und das dann wiederum durch $\begin{eqnarray*} \begin{pmatrix} m+n \\ m \end{pmatrix} - \begin{pmatrix} m+n \\ m-3 \end{pmatrix} \end{eqnarray*}$ ersetze und Gleichheit zeige?
(Und das gleiche dann noch für $\begin{eqnarray*} a_{m,n+1} \end{eqnarray*}$ mit Ersetzung durch $\begin{eqnarray*} a_{m-1,n} + a_{m-1,n+1} \end{eqnarray*}$ ?)

28.10.2014, 15:29

HAL 9000

Auf diesen Beitrag antworten »

An sich hatte ich an eine Induktion weder über $\begin{align*} m \end{align*}$ noch über $\begin{align*} n \end{align*}$ (die funktionieren nämlich streng genommen nicht), sondern über $\begin{align*} m+n \end{align*}$ gedacht, das ist sozusagen die "echte" Pascaldreieck-Zeilennummer.

28.10.2014, 15:42

Voldi

Auf diesen Beitrag antworten »

Klappt das auch, wenn ich wieder zur "normalen" Zeilenschreibweise zurückkehre und $\begin{eqnarray*} a_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} - \begin{pmatrix} n \\ k-3 \end{pmatrix} \end{eqnarray*}$ zeigen möchte?

Würde die Induktion dann über n und k laufen? verwirrt

28.10.2014, 16:12

HAL 9000

Auf diesen Beitrag antworten »

Nur über $\begin{align*} n \end{align*}$ , man muss aber noch dazu sagen, für welche $\begin{align*} k \end{align*}$ (in Abhängigkeit von $\begin{align*} n \end{align*}$ ) das dann gelten soll - ist etwas komplizierter zu formulieren.

Hier ist ziemliche Sorgfalt angesagt, dass man sich nicht mit den Indizes verheddert, auch in gerade in Nachbarschaft zur Trennlinie.

P.S.: Bei der Gelegenheit könnte man die Geschichte auch gleich etwas allgemeiner "anpacken", und die Trennlinie nicht bei 3, sondern allgemein $\begin{align*} t \end{align*}$ legen - aber nur, wenn dich das nicht durcheinanderbringt. Ok, mach es erstmal für $\begin{align*} t=3 \end{align*}$ , aber an sich ist es für allgemeines $\begin{align*} t \end{align*}$ auch nicht signifikant schwerer.

28.10.2014, 16:16

Voldi

Auf diesen Beitrag antworten »

Alles klar, danke smile

Würde sagen, dass das für $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ und $\begin{eqnarray*} k \geq \frac{n}{2} - 1 \end{eqnarray*}$ gilt.

28.10.2014, 19:31

HAL 9000

Auf diesen Beitrag antworten »

Ok, machen wir uns nochmal die genaue Zuordnung zwischen beiden "Koordinatensystemen" klar: Wenn

$\begin{align*} k \end{align*}$ ... Diagonalzeile (orange)

$\begin{align*} s \end{align*}$ ... Diagonalspalte (grüne)

$\begin{align*} n \end{align*}$ ... Pascaldreieck-Zeile

dann ist $\begin{align*} n=k+s \end{align*}$ , und $\begin{align*} k \end{align*}$ ist auch die Position des Elements innerhalb der Pascaldreieck-Zeile, wenn wir von rechts beginnend (also anders als beim Pascal-Dreieck) und mit 0 anfangend zählen.

Für das Element $\begin{align*} b_{n,k} \end{align*}$ in Pascal-Zeile $\begin{align*} n \end{align*}$ und Position $\begin{align*} k \end{align*}$ gilt nun die "abgeschnittene" Pascal-Rekursion

$\begin{align*} b_{n,k} = \begin{cases} 1 &\;\mbox{für}\;k=0 \\ b_{n-1,k-1}+ b_{n-1,k} & \;\mbox{für}\; 0< k < \frac{n+t-1}{2} \\ b_{n-1,k-1} & \;\mbox{für}\;k=\frac{n+t-1}{2} \\ 0 & \;\mbox{sonst}\end{cases} \end{align*}$ .

Beweisen wollen wir nun per vollständiger Induktion

$\begin{align*} b_{n,k} = \begin{cases} \binom{n}{k} & \;\mbox{für}\,0\leq k<t \\ \binom{n}{k}-\binom{n}{k-t} & \;\mbox{für}\,t\leq k \leq \frac{n+t-1}{2} \\ 0 & \;\mbox{sonst} \end{cases} . \end{align*}$

28.10.2014, 23:34

Voldi

Auf diesen Beitrag antworten »

Alles klar, dann hab ich es, glaub ich... smile

Noch mal zur Probe, ob das so stimmt:

Als Induktionsanfang zeige ich, dass die mittlere Zeile für k = t gilt (was dann $\begin{eqnarray*} \begin{pmatrix} n \\ t \end{pmatrix} -1 \end{eqnarray*}$ ist).
Dann zeige ich $\begin{eqnarray*} b_{n, k+1} = \begin{pmatrix} n \\ k+1 \end{pmatrix} - \begin{pmatrix} n \\ k + 1 - t \end{pmatrix} \end{eqnarray*}$ , indem ich links $\begin{eqnarray*} b_{n, k+1} \end{eqnarray*}$ durch $\begin{eqnarray*} b_{n-1, k} + b_{n-1, k+1} \end{eqnarray*}$ ersetze und Gleichheit zeige, richtig? Auf dem Papier hats spontan hingehauen, ich hoffe das passt so.

Eigentlich reicht es schon damit, oder? Also dass $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ für $\begin{eqnarray*} 0 \leq k \leq t \end{eqnarray*}$ gilt, muss man nicht noch mal zeigen, oder? .... Hammer

29.10.2014, 10:59

HAL 9000

Auf diesen Beitrag antworten »

Ich hab mich mal hingesetzt und versucht, das sorgfältig aufzuschreiben und gebe zu: Das ist der reinste Indexkrieg. Ich schreibe es dennoch mal auf um zu zeigen, dass nicht immer alles schön elegant geht.

Die Pascal-Zeilen $\begin{align*} n=0\ldots t-1 \end{align*}$ sollten klar sein, sie entsprechen dem normalen Pascal-Dreieck.

In Zeile $\begin{align*} n=t \end{align*}$ haben wir auch die Pascal-Dreieck-Zahlen mit einer Ausnahme ganz links (d.h. für $\begin{align*} k=n \end{align*}$ ), dort steht nun eine 0 statt 1.

Betrachten wir $\begin{align*} n=t \end{align*}$ damit gewissermaßen als Induktionsanfang.

Der Induktionsschritt $\begin{align*} (n-1)\to n \end{align*}$ ist dann nur für $\begin{align*} n\geq t+1 \end{align*}$ zu betrachten:

Wir gehen die einzelnen Positionen $\begin{align*} 0\leq k\leq n \end{align*}$ dieser $\begin{align*} n \end{align*}$ -ten Pascal-Zeile durch, die sich auf mehrere Fälle aufteilen:

a) Position $\begin{align*} k=0 \end{align*}$ (ganz rechts) mit $\begin{align*} b_{n,k}=1 \end{align*}$ ist klar.

b) Für die Positionen $\begin{align*} 0<k\leq t-1 \end{align*}$ kann wegen $\begin{align*} t-1<\frac{n+t-1}{2} \end{align*}$ die Rekursion $\begin{align*} b_{n,k}=b_{n-1,k-1}+b_{n-1,k} \end{align*}$ verwendet werden, infolge $\begin{align*} 0\leq k-1<t \end{align*}$ ergibt sich dann über die Induktionsvoraussetzung

$\begin{align*} b_{n,k} = \binom{n-1}{k-1}+\binom{n-1}{k} = \binom{n}{k} \end{align*}$

genau wie beim Pascalschen Dreieck.

c) Für Position $\begin{align*} k=t \end{align*}$ haben wir im Fall $\begin{align*} n\geq t+2 \end{align*}$ wieder $\begin{align*} t<\frac{n+t-1}{2} \end{align*}$ und damit dann

$\begin{align*} b_{n,t} = b_{n-1,t-1} + b_{n-1,t} = \binom{n-1}{t-1} + \binom{n-1}{t} - \binom{n-1}{0} = \binom{n}{t} - \binom{n}{0} \end{align*}$ .

Nur im Ausnahmefall $\begin{align*} n=t+1 \end{align*}$ ergibt sich

$\begin{align*} b_{t+1,t} = b_{t,t-1} = \binom{t}{t-1} = t = (t+1)-1 = \binom{t+1}{t} - \binom{t+1}{0} \end{align*}$ .

d) Für Positionen $\begin{align*} t+1\leq k\leq \frac{n+t-2}{2} \end{align*}$ haben wir sowohl $\begin{align*} t\leq k-1 < \frac{n-1+t-1}{2} \end{align*}$ als auch $\begin{align*} t< k \leq \frac{n-1+t-1}{2} \end{align*}$ und folglich

$\begin{align*} b_{n,k} = b_{n-1,k-1}+b_{n-1,k} = \binom{n-1}{k-1} - \binom{n-1}{k-1-t} + \binom{n-1}{k} - \binom{n-1}{k-t} = \binom{n}{k} - \binom{n}{k-t} \end{align*}$

e) Position $\begin{align*} t+1 \leq k=\frac{n+t-1}{2} \end{align*}$ (nur für $\begin{align*} n\geq t+3 \end{align*}$ überhaupt möglich) ergibt insbesondere $\begin{align*} t\leq k-1 < \frac{n-1+t-1}{2} \end{align*}$ und somit über $\begin{align*} n=2k+1-t \end{align*}$

$\begin{align*} b_{n,k} = b_{n-1,k-1} = \binom{n-1}{k-1}- \binom{n-1}{k-1-t} = \binom{2k-t}{k-1}- \binom{2k-t}{k-1-t} \stackrel{?}{=} \binom{2k+1-t}{k}- \binom{2k+1-t}{k-t} = \binom{n}{k}- \binom{n}{k-t} \end{align*}$

Gleichheit $\begin{align*} \stackrel{?}{=} \end{align*}$ kann begründet werden durch Addition der nahrhaften Null $\begin{align*} \binom{2k-t}{k} - \binom{2k-t}{k-t} = 0 \end{align*}$ .

f) Position $\begin{align*} k\geq \frac{n+t}{2} \end{align*}$ , hier ist per Festlegung ja bereits $\begin{align*} b_{n,k}=0 \end{align*}$ .

--------------------------

Ist also ein ziemliches Stück Arbeit, die aber nötig ist: Ein einziger Fehler an irgendeiner Zeilenposition kann aufgrund des rekursiven Bildungsgesetzes das ganze Gebilde zum Einsturz bringen...

29.10.2014, 21:40

Voldi

Auf diesen Beitrag antworten »

Whui, das war ja mal umfangreich. Danke! smile

Kaum bin ich fertig damit, das alles auszuformulieren, hör ich was von Catalanzahlen.... naja, vielleicht wärs mit denen irgendwie schneller gegangen, aber ist jetzt ja auch egal Hammer

30.10.2014, 12:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Voldi
Kaum bin ich fertig damit, das alles auszuformulieren, hör ich was von Catalanzahlen....

Soweit mir bekannt ist, nennt man diese Anzahl nur im Fall $\begin{eqnarray*} t=1,k=\frac{n}{2} \end{eqnarray*}$ dann Catalanzahl. Aber ich kann mich irren, so genau kenne ich mich da auch nicht aus. Augenzwinkern

Neue Frage »

Antworten »

Abgeschnittenes Pascalsches Dreieck

Verwandte Themen