Das Galton-Brett

Ein Garten ist nach einem Schachbrettmuster angelegt, wobei es aber nur 16 Felder gibt, welche in diesem Fall die Beete darstellen sollen. Die Beete sind von Wegen eingeschlossen, die in der Skizze als Linien erscheinen. Wie viele Möglichkeiten gibt es, den Garten von A nach B zu durchqueren, wenn an jedem erreichten Eckpunkt der Weg nur nach rechts oder nach oben, aber nie nach links oder nach unten fortgesetzt werden darf?



Es handelt sich um eine der unerschöpflich vielen Aufgaben zum Pascalschen Dreieck und zum Galton - Brett (unsere Aufgabe zum Weg des Wachmannes war ebenfalls ein Beispiel dazu). Die aufeinanderfolgenden Entscheidungen lassen sich wie folgt skizzieren, und das Pascalsche Dreieck zeigt in übersichtlicher Weise, wie man die Anzahl der Wege zu den einzelnen Verzweigungspunkten ausrechnet. Die Summe dieser Zahlen muss in der n-ten Zeile 2n ergeben, da sich die Anzahl der Wege in jeder Zeile verdoppelt. In der vierten Zeile sind das 24 = 16 .

Nun zu unserem Problem.

Es gibt 70 Wege der geforderten Art von A nach B.
Wie viele solcher Wege gäbe es, wenn das Quadrat n Zeilen und n Spalten enthielte?
Man erhielte dann die Folge 2, 6, 20 ,70 mit der expliziten Form „2n über n“ für das Folgenglied mit der Nummer n.