Wege im Gitternetz

27.10.2010, 13:26	Gast9000	Auf diesen Beitrag antworten »
Wege im Gitternetz Hallo, ich beschäftige mich mit einer Übungsaufgabe aus einem Buch und komme nicht auf die Lösung. Vielleicht hat jemand einen Tipp. In einem m x n - Gitternetz soll sich von oben links nach unten rechts bewegt werden. Erlaubte Bewegungen sind "nach unten" und "nach rechts". Wie viele Wege sind denkbar, ist die Frage. Das dürften also "m+n über m" mögliche Wege sein. Also durch die Auswahl der "rechts"-Schritte ist ein Weg klar definiert. Was ist aber, wenn eine zusätzliche Bewegung erlaubt wird, nämlich "schräg nach rechts". D.h. diagonal. Wählt man einen diagonalen Schritt, spart man genau einen Schritt ein. Aber wie kommt man auf die Anzahl aller möglichen Wege?
27.10.2010, 14:50	wisili	Auf diesen Beitrag antworten »
RE: Wege im Gitternetz Mit genau d Schritten "schräg nach rechts unten" gibt es soviele Wege: $\begin{eqnarray} \begin{pmatrix} m+n-d\\d \end{pmatrix} \cdot \begin{pmatrix} m+n-2d\\m-d \end{pmatrix} \end{eqnarray}$ Man hat m+n-d Schritte zu machen (nach rechts, unten oder diagonal), davon d diagonal. Den Rest der Schritte m+n-2d (nach rechts oder unten) behandelt man wie gehabt.
27.10.2010, 14:58	Gast9000	Auf diesen Beitrag antworten »
RE: Wege im Gitternetz Hallo, erst einmal danke für die Antwort. Aber was genau steckt dahinter? Vor allem, wofür brauche ich d, wenn die Anzahl der Diagonal-Schritte unbekannt ist? Wenn d unbekannt ist, wie sieht es dann aus?
27.10.2010, 15:29	wisili	Auf diesen Beitrag antworten »
RE: Wege im Gitternetz Dann kann man nichts sagen.
27.10.2010, 15:53	Gast9000	Auf diesen Beitrag antworten »
RE: Wege im Gitternetz Ist das definitiv so? Gibt es keine Formel, die nur von m und n abhängt? Angenommen, man möchte nun die Gesamtzahl der möglichen Wege ermitteln. Dann wäre es doch "m+n über m" (ohne Diagonal-Schritte) + Summe Anzahl der Wege mit d Diagonal-Schritten von d=1 bis d=m?
27.10.2010, 17:06	wisili	Auf diesen Beitrag antworten »
RE: Wege im Gitternetz Du meintest also nicht «d unbekannt», sondern «d beliebig». Dann kann man die Summe über alle d-Werte verwenden. Wenn n<=m (und d=0 zugelassen) etwa so: $\begin{eqnarray} \sum\limits_{d=0}^n \left( \begin{pmatrix} m+n-d\\d \end{pmatrix} \begin{pmatrix} m+n-2d\\m-d \end{pmatrix} \right) \end{eqnarray}$ . Eine Vereinfachung der Summe ist mir nicht bekannt.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »