Weg einer Schachfigur mit Catalan Zahlen |
18.12.2013, 15:53 | skruffes | Auf diesen Beitrag antworten » | |||||
Weg einer Schachfigur mit Catalan Zahlen habe ein blödes Beispiel... folgendes:
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! |
|||||||
18.12.2013, 17:32 | 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.... |
|||||||
18.12.2013, 18:42 | skruffes | Auf diesen Beitrag antworten » | |||||
Danke, das habe ich natürlich komplett überlesen 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. |
|||||||
19.12.2013, 10:20 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |