0 Daumen
1,2k Aufrufe

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? 

Avatar von

Ich weiss nicht, ob dir das was hilft, es verallgemeinert jetzt nur mal, was du bisher notiert hast und hat sehr wenig mit der Rekursionsformel zu tun, die du da angegeben hast.

Die kürzesten Wege die der König machen kann bestehen aus (n-1)+(n-1) = 2n-2 Zügen.

n-1 nach oben und n-1 nach rechts.

Es gibt somit (2n-2 tief n-1) = (2(n-1) tief (n-1)) kürzeste Wege.

Nun müsste man noch die Wege abziehen, die über die Hauptdiagonale hinausschiessen.

Wegen Cn(2n über n) - (2n über n+1)

ist Cn-1 = (2(n-1) tief (n-1)) - (2(n-1) tief n)) zu beweisen.

Wir hätten hier mal den blauen Teil der Behauptung.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community