Wie viele kürzeste Wege gibt es von A nach B?

Question

Aufgabe:

Vorliegend sei folgendes Netz.

Im Eck oben links befinde sich Punkt A mit den Koordinaten (1,1) und im Eck unten rechts der Punkt B mit Koordinaten (n,m). Wie viele kürzeste Wege gibt es von A nach B? Beweisen Sie Ihre Formel mit Induktion nach m+n.

Problem/Ansatz:

Ich habe leider keine wirkliche Idee, wie die Formel aussehen könnte. Ich dachte mir es gibt n Möglichkeiten horizontal zu gehen und m Möglichkeiten vertikal aber wirklich weiter komme ich nicht. Wäre sehr dankbar für Hilfe.

Answer 1

Du kannst jeden Weg von \( (1,1) \) nach \( (n, m) \) als Wort kodieren, nämlich als Kombination von \( R= \) "Eins nach rechts gehen" und \( U= \) "Eins nach unten gehen". Eine mögliche Kodierung für den Fall \( (n, m)=(3,3) \) waere z.B. RURU. Im Allgemeinen kommt in den Kodierungen \( n-1 \) mal \( R \) und \( m-1 \) mal U vor. Du suchst also die Anzahl an Möglichkeiten \( n-1 R \) 's und \( m-1 \) U's auf ein Wort der Länge \( n-1+m-1=n+m-2 \) zu verteilen. Du kannst dich leicht davon überzeugen, dass diese Anzahl gegeben ist durch
\( \left(\begin{array}{c} n+m-2 \\ n-1 \end{array}\right) \)

Sollte der letzte Schritt nicht klar sein, kann ich ihn gerne noch ausführen.

Comments

Danke erstmal für die Antwort.

Das mit der Länge der kürzesten Wege habe ich verstanden.

Und das mit der Formel meine ich auch verstanden zu haben. Denn die Formel beschreibt ja die Anzahl an Möglichkeiten, in den m+n-2 Zügen genau n-1 nach rechts zu gehen. Und das ist gleich der Anzahl an kürzesten Wegen.

Jetzt hab ich aber noch 2 Fragen. Zum einen: Könnte man auch m-1 beim Binomialkoeffizient unten verwenden? Das müsste ja eig aufs gleiche rauskommen, oder?

Und die zweite Frage: Wie mache ich das mit der Induktion. Also m und n müssen ja mindestens mal 1 sein.

Dann wäre der Induktionsanfang: für n+m=2

Wenn Punkt A und B dann auf einander liegen gibt es genau 1 Möglichkeit und das entspricht dem wenn man 0 über 0 bei der Formel erhält.

Aber wie macht man dann den Induktionsschritt?

---

Ja genau, du kannst unten auch \(m-1\) hinschreiben, das folgt zum einen aus dem Lösungsweg, zum anderen ist es eine Eigenschaft des Binomialkoeffizienten. Induktion brauchst du hier garnicht, wenn du mit der natürlichen Bijketion zwischen den Wegen und Kodierungen durch Wörter argumentierst. Du kannst natürlich einen Induktionsbeweis führen, indem du annimmst, die Formel gelte für irgend ein \((n, m)\) und es dann für \((n, m+1), (n+1, m), (n+1, m+1)\) beweist. Die ersten beiden Fälle sind symmetrisch, der Induktionsschritt ist hier, dass du ja eine Reihe hinzufügst (bei \(n, m+1\)), und du also alle möglichen Wege von \((1, 1)\) zu \((1, m), (2, m), \ldots, (n, m)\) berechnest, und dann von jedem dieser Punkte die Anzahl an Wegen zu \((n, m+1) \) berechnest. Du wendest also die Induktionshypothese mehrere male auf unterschiedliche Netze an, insbesondere verwendest du also "starke Induktion".