Anzahl der möglichen Wege in einem MxN Gitter

21.08.2007, 16:38

eugen

Anzahl der möglichen Wege in einem MxN Gitter

Hey Leute,
in einer Altklausur steht folgende Aufgabe:
In einem m x n Gitter bezeichne A die linke untere und B die rechte obere Ecke. Berechnen Sie für beliebige m und n die Anzahl der verschiedenen Wege von A nach B, die stehts nach oben oder nach rechts gehen.
Also in einem 5x3 Gitter gibt es 6 knoten nach rechts und 4 Knoten nach oben über die man gehen kann.
Ich hab jetzt etwas herumprobiert und bin zu folgender Lösung gekommen:
$\begin{eqnarray*} \sum_{i=0}^m~{\sum_{j=i}^n~j} \end{eqnarray*}$

Könnte das stimmen? Und wenn nicht, wie setzt man bei dieser Aufgabe an?

21.08.2007, 16:58

Tomtomtomtom

Auf diesen Beitrag antworten »

Du hast insgesamt acht Wegstücke, darunter kannst du dir drei beliebige aussuchen, die nach oben gehen. Dadurch ist ein Weg eindeutig festgelegt. Umgekehrt entspricht jedem zulässigen Weg genau die Auswahl von drei Wegstücken nach oben unter den acht Wegstücken insgesamt.

Du suchst also den Binomialkoeffizienten "8 über 3" oder allgemein halt "m+n über m".

BTW: Wie schreibt man Binomialkoeffizietnen in LaTEX?

21.08.2007, 17:00

vektorraum

Auf diesen Beitrag antworten »