Kombinatorik: Anzahl der Wege < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe folgende Aufgabe, bei der ich nicht weiß wie ich das anpacken soll:
Es sei ein Schachbrett mit n*m Felder.
Wieviele mögliche Wege gibt es nun den König von links unten nach rechts oben zu bewegen? Dabei stets nur eins nach rechts oder eins nach oben. (NICHT diagonal!)
Ich habe mir das mal mit einem Schachbrett, das lediglich 2*2 groß ist (zeichnerisch) veranschaulicht, dabei konnte ich dann 6 mögliche Weege zeichnen.
Wie kann ich die Aufgabe jedoch rechnerisch lösen (zeichnerisch ist sie ja nicht ausdrückbar, da sie von n&m abhängig ist)?
Würd mich freuen, wenn mir jemand helfen könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:53 Fr 03.12.2004 | | Autor: | Hexe |
Also ich kann dir auf jeden Fall nen Denkanstoß geben . Wenn du das Brett mal anfängst hinzumalen und den Punkten Koordinaten gibst, dann kommst du auf die Rekursion:
Anzahl wege zu (x/y) = Anzahl wege zu (x-1/y) + Anzahl wege zu (x/y-1) , daß heißt, es ergibt sich im Prinzip das Pascalsche Dreieck.
|
|
|
| |
|
???
Ich habe mir mal eine Rekursionsformel für Binomialkoeffizienten angeschaut, komme jedoch leider trotzdem nicht weiter...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:04 Fr 03.12.2004 | | Autor: | Hanno |
Hallo Spaceshark!
Denke folgenden Ansatz zu Ende:
Wenn dein Feld die Maße [mm] $n\times [/mm] m$ hat, dann brauchst du, egal welchen Weg du gehst, genau m+n-2 Züge, da du genau m-1 mal nach rechts, und n-1 mal nach oben ziehen musst. Jetzt bleibt also lediglich zu prüfen, wie du deine Schrittfolge anordnen kannst. Du musst also die n-1 der n+m-2 Züge auswählen, in denen du nach oben ziehen möchtest, und anschließend aus den verbleibenden m-1 Zügen noch diejenigen m-1 Züge auswählen, in denen du nach rechts ziehen möchtest. Mathematisch drückt man die Anzahl der k-elementigen Teilmenge einer n-elementigen Menge über die ........ aus, also lautet die Lösung ........
Schaffst du es?
Liebe Grüße,
Hanno
|
|
|
|
