hier die Aufgabe
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.
Hier mein bisheriger Lösungsweg:
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
Die Frage aller Fragen ist jetzt, wie ich das folgende verwenden soll: der König kann nicht über die Hauptdiagonale hinweg ziehen. das schränkt die Anzahl Möglichkeiten natürlich ein doch wie genau?
