015 – Anzahl der möglichen Wege im Gitter

 

Startet man in der oberen linken Ecke eines 2×2 Gitters, gibt es 6 Wege (ohne in die falsche Richtung zu gehen) zur Ecke unten rechts.

Anzahl der möglichen Wege im Gitter

Wie viele Wege gibt es in einem 20×20 Gitter?

Lösung

Da man nicht in die falsche Richtung gehen darf, muss jeder Weg 20 Bewegungen nach rechts und 20 Bewegungen nach unten enthalten.

Gesucht ist daher die Anzahl der Permutationen dieser Bewegungen. Bei einem 2×2 Gitter lässt sich dies leicht aufschreiben:

0: nach rechts
1: nach unten

mögliche Wege:

0011
0101
0110
1001
1010
1100

also 6 Möglichkeiten.

Die Anzahl der Permutationen lässt sich mit dem Binomialkoeffizienten berechnen:

N = \left( {\begin{array}{*{20}{c}} w \\ r \\ \end{array} } \right) = \frac{{w!}} {{r!\left( {w-r} \right)!}}

Dabei ist w die Anzahl der zurückgelegten Wegstücke und r die Anzahl der Wege nach rechts. Es ist offensichtlich die Anzahl der nötigen Wegstücke das doppelte der Kantenlänge k. Die Wegstücke nach rechts sind genau die Kantenlänge:

N = \left( {\begin{array}{*{20}{c}} w \\ r \\ \end{array} } \right) = \frac{{w!}} {{r!\left( {w-r} \right)!}} = \left( {\begin{array}{*{20}{c}} {2k} \\ k \\ \end{array} } \right) = \frac{{\left( {2k} \right)!}} {{{{\left( {k!} \right)}^2}}}

Dies ist eine Zeile in Matlab:

factorial(40)/(factorial(20)*factorial(20))

Ergebnis: 137846528820