Anzahl der kürzesten Wege in Manhattan

04.10.2012, 14:36	Kevin-357	Auf diesen Beitrag antworten »
Anzahl der kürzesten Wege in Manhattan Meine Frage: Hallo! Ich habe hier folgende Aufgabe: Sie stehen in Manhattan an der Kreuzung (0,0). (a) Wie viele Möglichkeiten gibt es auf kürzestem Weg von (0,0) nach (n,k) zu gelangen? (b) Wie viele Möglichkeiten gibt es auf kürzestem Weg von (0,0) über (6,8) nach (12,12) zu gelangen? Meine Ideen: Ich habe beide Aufgaben soweit gelöst, bin mir aber nicht ganz sicher, ob meine Ansätze richtig sind. Zu (a): Der kürzeste Weg umfasst n Schritte in Richtung Osten und k Schritte in Richtung Norden. Man kann die n+k Schritte auf (n+k)! Möglichkeiten anordnen. Da sich die n Schritte in Richtung Osten und die k Schritte in Richtung Norden aber nicht unterscheiden, muss noch durch die Anzahl dieser Anordnungen dividiert werden. Man erhält also $\begin{eqnarray} \frac{(n+k)!}{n!\cdot k!} \end{eqnarray}$ Möglichkeiten. Zu (b): Wir wenden zweimal das Ergebnis aus Aufgabenteil (a) an: 1. Um von (0,0) nach (6,8) zu kommen, gibt es $\begin{eqnarray} \frac{(6+8)!}{6!\cdot 8!} \end{eqnarray}$ Möglichkeiten. 2. Um von (6,8) nach (12,12) zu kommen (äquivalent dazu von (0,0) nach (6,4) zu kommen), gibt es $\begin{eqnarray} \frac{(6+4)!}{6!\cdot 4!} \end{eqnarray}$ Möglichkeiten. Somit ergeben sich insgesamt $\begin{eqnarray} \frac{(6+8)!}{6!\cdot 8!} \cdot \frac{(6+4)!}{6!\cdot 4!} =630630 \end{eqnarray}$ Möglichkeiten.
04.10.2012, 14:45	tmo	Auf diesen Beitrag antworten »
Ja, das stimmt so. Du kannst das Ergebnis aus (a) natürlich noch zu $\begin{eqnarray} \binom{n+k}{k} \end{eqnarray}$ umformen. Vielleicht als Zusatz noch ein anderer Zugang zu dieser Aufgabe: $\begin{eqnarray} N(n,k) \end{eqnarray}$ bezeichne die gesuchte Anzahl der Möglichkeiten. Vor dem letzten Schritt ist man ja entweder bei $\begin{eqnarray} (n-1,k) \end{eqnarray}$ oder bei $\begin{eqnarray} (n,k-1) \end{eqnarray}$ angekommen. Daher ist $\begin{eqnarray} N(n,k) = N(n-1,k) + N(n,k-1) \end{eqnarray}$ . Das ist genau die gleiche Rekursionsformel, die der Binomialkoeffizient $\begin{eqnarray} \binom{n+k}{k} \end{eqnarray}$ hat. In dem Fall ist der direkte Ansatz wohl intuitiver, aber es gibt bestimmt Probleme, bei dem man mit dem rekursiven Ansatz besser zum Ziel kommt
04.10.2012, 14:55	Kevin-357	Auf diesen Beitrag antworten »
Danke für deine schnelle Antwort tmo! Das mit dem Trick über die rekursive Darstellung ist zum beweisen ganz gut, wenn man bereits weiß, wie die gesuchte Formel lautet. Aber ansonsten wäre ich da nicht drauf gekommen.
04.10.2012, 15:16	tmo	Auf diesen Beitrag antworten »
Ja, sofort zu erkennen, dass diese Rekursionformel dann zu diesem Binomialkoeffizient führt, wäre natürlich nicht einfach. Aber im Allgemeinen arbeitet man ja deswegen auch länger als eine halbe Minute an einem Problem Der Klassiker für diese rekursive Vorhergehensweise ist übrigens dieser hier: Man hat eine Treppe mit n Stufen und kann sich bei jedem Schritt überlegen, ob man nur 1 Stufe nimmt oder gleich 2 Stufen auf einmal hochsteigt. Wenn man sich nun überlegt, wie viele Möglichkeiten (in Abhängigkeit von n) man hat, so taucht die Fibonaccifolge auf.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »