Wege durch ein Schachbrettmuster

Die folgende Aufgabe kommt in vielen Varianten und in verschiedenen Klassenstufen vor. Stehen keine Hilfsmittel aus der Kombinatorik zur Verfügung, so kann man auf das Pascalsche Dreieck zurückgreifen; mit Hilfe der Kombinatorik lassen sich die Aufgaben zügig und elegant lösen.

Wir betrachten den ersten Quadranten des gewohnten kartesischen x- y- Koordinatensystems und beschränken uns auf Gitterpunkte mit ganzzahligen Koordinaten. Vom Ursprung (0|0) soll der Weg zu einem Punkt (m|n) führen, wobei folgende Regeln gelten. Jeder Schritt besteht darin, entweder die x- oder die y- Koordinate um genau 1 zu vergrößern. Anschaulich gesprochen: Jeder Schritt geht entweder um eins nach rechts oder um eins nach oben; Schritte nach links oder nach unten sind nicht zulässig.
Wie viele solcher Wege vom Ursprung (0|0) zum Punkt (m|n) gibt es?
Rechne die Anzahlen der Wege zu den Punkten (4 | 4 ) und ( 6 | 3 ) aus.

Ein Weg von (0|0) nach (m|n) besteht aus m Schritten in x-Richtung (nach rechts) und in n Schritten in y- Richtung ( nach oben), insgesamt aus m + n Schritten. Umgekehrt führt jede Schrittfolge, die man so wählt, von (0|0) nach (m|n) .
Mit der Wahl des Zielpunktes ist die Gesamtzahl der Schritte eines jeden Weges festgelegt: Sie ist die Summe seiner Koordinaten. Die Wege unterscheiden sich darin, auf welchen Plätzen der m + n Schritte die m Schritte liegen, welche in x-Richtung gehen.
Ein Weg entsteht, indem man diese m Plätze auswählt.

Dazu gibt es binomial Möglichkeiten ("m+n über m").

Ein Weg repräsentiert eine m-elementige Teilmenge einer (m+n)-elementigen Menge.
Man kann ebenso aus m+n Schritten die Plätze der n Schritte auswählen, die in y-Richtung gehen. Dazu gibt es

binomial Möglichkeiten. In der Tat gilt ja binomial = binomial

Man kann sich übrigens von der Richtigkeit der Gleichung wie folgt überzeugen. Zu jeder m-elementigen Teilmenge einer (m+n)-elementigen Menge gibt es genau eine n-elementige Komplementärmenge.

Vom Ursprung zum Punkt ( 4 | 4) gibt es 8*7*6*5/ 4! = 70 Wege, vom Ursprung zum Punkt ( 6 | 3) gibt es "9 über 3" = 84 Wege.