Weg einer Schachfigur mit Catalan Zahlen

Neue Frage »

skruffes Auf diesen Beitrag antworten »
Weg einer Schachfigur mit Catalan Zahlen
Hallo,

habe ein blödes Beispiel... folgendes:


code:
1:
2:
3:
4:
Cn bezeichne die n-te Catalan-Zahl. Zeigen Sie: Es gibt genau C n-1 mögliche Wege, auf denen ein König auf einem Schachbrett der Größße n×n von der linken unteren zur rechten oberen Ecke ziehen kann, wenn er immer nur nach rechts oder 
oben ziehen und kein Feld oberhalb der Hauptdiagonale berühren darf.

Hinweis: Man zeige, dass die gesuchte Zahlenfolge und die Folge der Catalanzahlen dieselbe Rekursion erfüllen.




Ok. Formel der Catalan Zahlen ist (2n über n) - (2n über n+1)

zuerst: der König darf nur nach oben oder nach rechts springen.

die Länge des weges bei einem nxn schachbrettes beträgt somit:
L=(n-1)2, kann man einfach mal testen bei einem 4x4 Brett im Kopf.
die Anzahl der Operationen für rechts=r und oben=o.

aufgrund der Symmetrie kann man sagen #o=#r=((n-1)2)/2=n-1

so nun hat man zb. bei einem 4x4 brett --> 6 schritte (4-1)2.

so also 6 slots für die rs und os--> bsp anordnung ist o,r,o,r,o,r

so wenn ich nun alle 3 os wähle und sie in die 6 slots packte, sind die rs auch festgelegt:

das ist also reihenfolge egal, ohne wiederholung also kombination anwenden: da kommt denn (L über #r) bzw. (L über #o) raus.


Also hab ich hier schon das (2n über n) aber wie gehts weiter? Was muss ich hier noch abziehen?


Bsp 4*4

Cat3 = 13
Mein Ergebnis (L über #r) = 20


Würde mich über Hilfe sehr freuen!
Math1986 Auf diesen Beitrag antworten »
RE: Weg einer Schachfigur mit Catalan Zahlen
Dein Problem liegt darin, dass der König nicht über die Hauptdiagonale hinweg ziehen kann, das schränkt die Anzahl Möglichkeiten natürlich ein.

So darf man z.B. nicht mit einem Schritt nach oben beginnen, ebenso wäre r,o,o unzulässig....
skruffes Auf diesen Beitrag antworten »

Danke, das habe ich natürlich komplett überlesen böse


Wie begründe ich dass diese Einschränkung 2n (für alle Züge) über n+1 liegt?


Hab da für das n+1 nicht wirklich eine passende Lösung. verwirrt
Math1986 Auf diesen Beitrag antworten »

Hm, es muss ja gelten dass du nie mehr Schritte nach oben als nach rechts gehen darfst. Das erinnert mich schonmal an das Auszählen von Stimmen, so dass Kandidat A niemals vor Kandidat B liegt, was auch widerrum durch Catalan-Zahlen beschrieben werden kann.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »