TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 209

Stellen Sie sich ein rechteckiges Schachbrettmuster vor, bestehend aus $m$ mal $n$ Quadraten mit Seitenlänge 1. Wege seien nur entlang der Ränder dieser Quadrate erlaubt. Die kürzesten Wege vom linken unteren zum rechten oberen Eckpunkt des Rechtecks haben offenbar alle die Länge $m+n$. Die Menge all dieser kürzesten Wege sei mit $K(m,n)$ bezeichnet.

(a) Wieviele kürzeste Wege gibt es für $m=6$ und $n=4$?

(b) Jeder kürzeste Weg $w$ lässt sich darstellen als eine Abfolge von Schritten $w_i$ nach oben ($o$) oder nach rechts ($r$), symbolisch also $w=(w_1,\dots ,w_{m+n})$, z.B. $w=(r,o,r,r,o,o,o,r,r,r)$ (hier ist wieder $m=6,n=4$). Welche Bijektion $f$ zwischen $K(m,n)$ und der Menge $T(m,n)$ aller $m$-elementigen Teilmengen von $\{1,2,\dots ,m+n\}$ wird durch diese Darstellung nahegelegt?

(c) Geben Sie eine allgemeine Formel für $|K(m,n)|$ an.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Dieses Beispiel hat noch keinen Lösungsvorschlag. Um einen zu erstellen, kopiere folgende Zeilen, bearbeite die Seite und aktualisiere den status=unsolved Mögliche status=... Werte stehen hier: Vorlage:Beispiel

== Lösungsvorschlag von ~~~ ==
--~~~~

Siehe auch Hilfe:Formeln und Hilfe:Beispielseiten.