Maus Pinky läuft auf Gitter

Neue Frage »

Kaka Auf diesen Beitrag antworten »
Maus Pinky läuft auf Gitter
Meine Frage:
Käse-Kombinatorik

Die Maus Pinky läuft auf ihrem 2D-Gitter prinzipiell nur auf Wegen, die monoton
sind. Sie befindet sich gerade am Gitterpunkt (0, 0) und möchte zu Ihrem Spielgefährten am Gitterpunkt (n, n). Allerdings sieht sie am Gitterpunkt (k, k), 0 < k < n, einen leckeren Käse.

i) Finden Sie eine Formel für die Anzahl a_{k} der Gitterwege, über die Pinky laufen kann, um zu Ihrem Spielgefährten zu kommen und dabei den Käse an Position (k, k) einzusammeln.

ii) Zeigen Sie, dass a_{k} = a_{n?k} ist.

iii) Zeigen Sie, dass für k = 1 und jedes n > 1 mehr als die Hälfte aller Wege am Käse vorbeikommen.

Meine Ideen:
Ich hab ger keine Ahnung drüber.
Aber Der Weg isz monoton wachsend, d.h. Eine Bewegung vom (a, b) führt zu entweder (a + 1, b) oder (a, b + 1).

Also (0, 0) -> (k, k) -> (n, n) =
Leopold Auf diesen Beitrag antworten »

Du könntest dir zunächst überlegen, daß jeder Weg von nach eine Folge von rechts-hoch-Entscheidungen ist. Wenn etwa ist, dann wären rrhrhhrh oder hrhrhrrh oder rrrhhrhh usw. mögliche Wege. Wie viele von dieser Sorte gibt es? Und entsprechend mußt du die Wege von nach zählen.
Jeder Gesamtweg setzt sich zusammen aus einem Weg von nach und einem von nach . Die Teilwege sind frei kombinierbar. Worauf läuft das bei der Anzahlbestimmung hinaus?
Neue Frage »
Antworten »



Verwandte Themen

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