# Bernoulli-Dreieck

Das Bernoulli-Dreieck ist eine Form der grafischen Darstellung von Partialsummen der Binomialkoeffizienten ${\tbinom {n}{k}}$. Der Name geht auf den Mathematiker Jakob I Bernoulli zurück.

## Beschreibung

Für jede nicht negative ganze Zahl $n$ und für jede ganze Zahl $k$ zwischen $0$ und $n$ ist die $n$-te Zeile und $k$-te Spalte des Bernoulli-Dreiecks gegeben durch die Summe der ersten $k$ Binomialkoeffizienten $n$-ter Ordnung:
    $\sum _{p=0}^{k}{\binom {n}{p}}$
Die ersten Zeilen des Bernoulli-Dreiecks lauten:
    ${\begin{array}{cc|cccccccccccc}&k&0&1&2&3&4&5&6&7&8&9\\n&&\\\hline 0&&1\\1&&1&2\\2&&1&3&4\\3&&1&4&7&8\\4&&1&5&11&15&16\\5&&1&6&16&26&31&32\\6&&1&7&22&42&57&63&64\\7&&1&8&29&64&99&120&127&128\\8&&1&9&37&93&163&219&247&255&256\\9&&1&10&46&130&256&382&466&502&511&512\end{array}}$
Ähnlich wie beim Pascalschen Dreieck ist jede Stelle im Bernoulli-Dreieck die Summe von zwei Stellen der vorherigen Zeile, mit Ausnahme der letzten Zahl jeder Zeile, die das Doppelte der letzten Zahl der vorherigen Zeile ist. Sei zum Beispiel $B_{n,k}$ das Element in der $n$-ten Zeile und $k$-ten Spalte. Dann gilt:
    ${\begin{aligned}B_{n,0}=&1&{\mbox{ für }}&k=0\\B_{n,k}=&B_{n-1,k}+B_{n-1,k-1}&{\mbox{ für }}&0<k<n\\B_{n,n}=&2\cdot B_{n-1,k-1}=2^{n}&{\mbox{ für }}&k=n\end{aligned}}$

## Eigenschaften

Die Spalten des Bernoulli-Dreiecks ergeben spezielle Zahlenfolgen (wobei, falls es noch keine Zahl in dieser Spalte gibt, die ganz rechten Werte aus den oberen Zeilen genommen werden):
* Die erste Spalte ganz links $(k=0)$ ergibt die triviale Einerfolge, es ist $B_{n,0}=1$:
       1, 1, 1, 1, 1, 1, 1, … (Folge A000012 in OEIS)
* Die zweite Spalte von links $(k=1)$ ergibt die Folge der natürlichen Zahlen, es ist $B_{n,1}=n+1$:
       1, 2, 3, 4, 5, 6, 7, … (Folge A000027 in OEIS)
* Die dritte Spalte von links $(k=2)$ ergibt die Folge der Dreieckszahlen plus Eins, es ist $B_{n,2}={\frac {n^{2}+n}{2}}+1={\frac {n^{2}+n+2}{2}}$. Dies ist auch die Folge der zentralpolygonalen Zahlen (auch Zahlenfolge des faulen Kellners genannt (vom englischen Lazy caterer's sequence)):
       1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, …(Folge A000124 in OEIS)
* Die vierte Spalte von links $(k=3)$ ergibt die Folge der Kuchenzahlen (vom englischen cake number), es ist $B_{n,3}={\frac {1}{6}}\cdot (n+1)\cdot (n\cdot (n-1)+6)$:
       1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, … (Folge A000125 in OEIS)
* Die fünfte Spalte von links $(k=4)$ ergibt die Zahlenfolge, die die maximale Anzahl von Regionen angibt, die durch Verbinden von $n+1$ Punkten um einen Kreis durch gerade Linien erhalten werden können, es ist also $B_{n,4}=1+{\binom {n+1}{2}}+{\binom {n+1}{4}}$. Alternativ gibt die fünfte Spalte auch die maximale Anzahl von Regionen im vierdimensionalen Raum an, die man durch $n-1$ dreidimensionale Hyperebenen bilden kann (beginnend mit $n=1$):
       1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, 562, 794, 1093, 1471, 1941, 2517, 3214, … (Folge A000127 in OEIS)
* Im Allgemeinen gibt die $(k+1)$-te Spalte die maximale Anzahl von Regionen im $k$-dimensionalen Raum an, die durch $n-1$ $(k-1)$-dimensionale Hyperebenen gebildet werden (beginnend mit $n=1$).
    Zum Beispiel bedeutet das für die $(k+1)=6$-te Spalte die maximale Anzahl von Regionen im $k=5$-dimensionalen Raum, die durch $n-1$ $(k-1)=4$-dimensionale Hyperebenen gebildet werden (beginnend mit $n=1$).
       1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, … (Folge A006261 in OEIS)
          Beispiel:
             An der achten Stelle (also bei $n=8$) dieser sechsten Spalte des Bernoulli-Dreiecks (es ist also $(k+1)=6$ und somit $k=5$) steht die Zahl 120. Man kann somit im fünfdimensionalen Raum $n-1=7$ vierdimensionale Hyperebenen so legen, dass der fünfdimensionale Raum in 120 Teilräume (Regionen) zerfällt.
* Die $(k+1)$-te Spalte gibt auch die Anzahl der Kompositionen von $n$ in $k+1$ oder weniger Teile an (also die Anzahl der Möglichkeiten, die Zahl $n$ in die Summe von $k+1$ oder weniger natürliche Zahlen zu zerlegen), wobei die Reihenfolge eine Rolle spielt.
          Beispiel 1:
             Man betrachte zum Beispiel die $(k+1)=2$-te Spalte des Bernoulli-Dreiecks:
                1, 2, 3, 4, 5, 6, 7, … (Folge A000027 in OEIS)
                   An der fünften Stelle (also bei $n=5$) dieser zweiten Spalte des Bernoulli-Dreiecks (es ist also $k+1=2$) steht die Zahl 5. Es gibt also 5 Möglichkeiten, die Zahl $n=5$ in $k+1=2$ oder weniger Teile zu zerlegen. Diese Möglichkeiten lauten:
                      5 = 5 = 1+4 = 4+1 = 2+3 = 3+2
          Beispiel 2:
             Man betrachte zum Beispiel die $(k+1)=3$-te Spalte des Bernoulli-Dreiecks:
                1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, …(Folge A000124 in OEIS)
                   An der fünften Stelle (also bei $n=5$) dieser dritten Spalte des Bernoulli-Dreiecks (es ist also $k+1=3$) steht die Zahl 11. Es gibt also 11 Möglichkeiten, die Zahl $n=5$ in $k+1=3$ oder weniger Teile zu zerlegen. Diese Möglichkeiten lauten:
                      5 = 5 = 1+4 = 4+1 = 2+3 = 3+2 = 1+1+3 = 1+3+1 = 3+1+1 = 1+2+2 = 2+1+2 = 2+2+1
          Beispiel 3:
             Man betrachte zum Beispiel die $(k+1)=9$-te Spalte des Bernoulli-Dreiecks:
                1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1013, 1981, 3797, 7099, 12911, 22819, 39203, 65536, … (Folge A008861 in OEIS)
                   An der zehnten Stelle (also bei $n=10$) dieser neunten Spalte des Bernoulli-Dreiecks (es ist also $k+1=9$) steht die Zahl 511. Es gibt also 511 Möglichkeiten, die Zahl $n=10$ in $k+1=9$ oder weniger Teile zu zerlegen. Die einzige Möglichkeit, die nicht gezählt wird, ist $1+1+1+\ldots +1=10$, weil hier die Zahl $n=10$ in 10 Summanden aufgeteilt wird, aber nur maximal 9 erlaubt sind.
* Wie im Pascalschen Dreieck führen Summen von Komponenten entlang diagonaler Pfade in Bernoullis Dreieck zur Fibonacci-Folge. Diese lauten:
       0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, … (Folge A000045 in OEIS)
    Man erhält diese Fibonacci-Folge ab ihrem 3. Wert im Bernoulli-Dreieck auf die folgende Art und Weise:
       $n\downarrow k\to$0123456789 01--------- 112-------- 2134------- 31478------ 415111516----- 51616263132---- 6172242576364--- 718296499120127128-- 8193793163219247255256- 911046130256382466502511512 so erhält man die Fibonacci-Zahlen $1=1$ $2=2$ $3=4-1$ $5=8-3$ $8=16-7-1$ $13=32-15-4$ $21=64-31-11-1$ $34=128-63-26-5$ $55=256-127-57-16-1$ $89=512-255-120-42-6$