Wie viele Möglichkeiten gibt es eine Schachfigur von links unten nach rechts oben zu bewegen

Question

folgende Fragestellung:

Eine Figur steht in der linken unteren Ecke eines Schachbretts mit n² Feldern. Wieviele Möglichkeiten gibt es, sie in die rechte obere Ecke zu bringen, wenn die Figur pro Zug entweder nach rechts oder oben bewegt werden darf?

Das ganze lässt sich sicher gut mit Kombinatorik lösen, aber ich hab bisher noch keinen Ansatz.

Answer 1

er muss ja n-1 Schritte nach rechts und n-1 Schritte nach oben zurückgelegt haben. Also 2n- 2 Schritte insgesamt. Nummeriere die Gesamtschritte durch. Jede Bewegung lässt sich eindeutig durch die Aufteilung der n-1 Schritte in die eine Richtung auf die Gesamtschritte beschreiben. Die Reihenfolge der Zuordnung spielt keine Rolle. Wieviele unterschiedliche Bewegungen gibt es also?

Gruß

Comments

Erstmal danke für die Antwort :)

Ich hab mir heute Deine Antwort genauer angeschaut und Zeit gehabt etwas zu knobeln. Offensichtlich kommt als Ergebnis 2n-2 über n-1 raus, aber ich verstehe noch nicht wirklich warum. Also dass man 2n-2 Züge hat, auf die man was verteilen will, meine ich verstanden zu haben, aber warum ist dann k gerade n-1?

---

Weil jede Bewegung durch die Angabe der \(n-1\) Schritte in eine Richtung beschrieben werden kann. Wie gesagt kannst du die gesamten Schritte nummerieren:

Schritt 1, Schritt 2, ..., Schritt \(2n - 2\)

Wenn du jetzt aus diesen Schritten \(n-1\) Schritte festlegst an denen er nach rechts geht, muss er an den restlichen Schritten ja nach oben gegangen sein. Analog kannst du die Schrittauswahl damit vergleichen aus einer Urne mit insgesamt \(2n-2\) Kugeln mit den Nummern von 1 bis \(2n-2\), \(n-1\) Kugeln zu ziehen und zu sagen, bei diesen Zahlen (also bei diesen Schrittnummern) gehe ich in die eine Richtung. 

---

Achso ja klar macht Sinn. Super danke!

Answer 2

Stell dir einfach ein reguläres Schachbrett n = 8 vor. Dann müsste man 7 mal nach rechts und 7 mal nach oben gehen

R R R R R R R O O O O O O O

Nun fragt man sich wieviele Anordnungen kann es für die R's und O's geben.

Das sind nach der Kombinatorik

(7 + 7)! / (7! * 7!) = 3432

Umgesetzt für ein allgemeines n wären es

((n - 1) + (n - 1))!/((n - 1)!·(n - 1)!) = (2·n + 2)!/(n + 1)!^2