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

Ähnliche Artikel

1 Kommentar zu “015 – Anzahl der möglichen Wege im Gitter”

Ich komme irgendwie nicht zu einer plausiblen Lösung für folgende abgewandelte Aufgabe:

in einem 3 x 3 Gitter:

1. Ein beliebiges Feld außer das Feld (2,2) wird ausgewählt.
2. Vom Startfeld (z.B. 1,1) muss man zum gegenüber liegenden Feld gelangen (3,3), und kann dabei rechts, links, hoch und runter gehen ohne ein Feld doppelt zu betreten.

Wie viele mögliche Wege gibt es, wenn die Richtung des Wegs (Start/Ende) vernachlässigt wird?

Freue mich sehr über eure Antworten!

Kommentar verfassen