TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS13/Beispiel 202

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.

Lösung

Allgemeine Betrachtung

Um dieses Beispiel zu lösen, muss man zuerst verstehen, um welches Abzählproblem es sich handelt. Für die Vorstellung ist es hilfreich, wenn man sich das Schachbrettmuster als Tabelle mit $m=6$ Spalten und $n=4$ Zeilen vorstellt. Jede Zelle in dieser Tabelle hat dabei die Seitenlänge 1. (Mathematischer wäre die Vorstellung von $m\cdot n=6\cdot 4=24$ Quadraten mit Seitenlänge 1, die ein Rechteck bilden, was aber auf das Gleiche hinausläuft.) Gesucht ist nun die Anzahl der Wege entlang der Ränder von links unten bis rechts oben. Dazu überlegen wir uns zuerst, wie man so einen Weg beschreiben könnte. Da wir den kürzesten Weg suchen, dürfen wir uns nur nach oben und nach rechts bewegen, es bietet sich also an die Buchstaben o für die Bewegung nach oben und den Buchstaben r für die Bewegung nach rechts zu verwenden. Ein kürzerster Weg wäre dann z. B. $\{r,o,r,r,o,o,o,r,r,r\}$. Wie man sieht bzw. aus der Angabe entnehmen kann, müssen wir immer $n$ Mal nach oben gehen und $m$ Mal nach rechts. Das heißt also, dass die Menge immer $n$ Mal $o$ enthält und $m$ Mal $r$. Im Fall (a) also beispielsweise $\{r,r,r,r,r,r,o,o,o,o\}$.

Dass die Menge für alle Lösungen immer die gleiche Anzahl an o ($n$) und r ($m$) enthält, sagt uns, dass es sich bei dem Abzählproblem um eine Permutation handelt. Warum eine Permutation? Wir entnehmen keine Elemente aus der Menge (und bilden damit eine neue Menge) sondern wollen nur alle möglichen Anordnungen der Elemente (Permutationen) berechnen. Nun müssen wir uns noch überlegen, ob sich alle Elemente voneinander unterscheiden (Permutation ohne Wiederholung) oder ob nicht-unterscheidbare (gleichartige) Elemente in der Menge sind (Permutation mit Wiederholung). Die einzelnen Elemente des Weges (die r bzw. o) unterscheiden sich nicht, sie wiederholen sich also. Es handelt es sich also um eine Permutation mit Wiederholung. Eine Permutation mit Wiederholung ist wie folgt definiert:

Eine Permutation mit Wiederholung ist eine Anordnung von $n$ Objekten, von denen manche nicht unterscheidbar sind. Sind genau $k$ Objekte identisch, dann sind diese auf ihren Plätzen vertauschbar, ohne dass sich dabei eine neue Reihenfolge ergibt. Auf diese Weise sind genau $k!$ Anordnungen gleich. Die Anzahl der Permutationen von $n$ Objekten, von denen $k$ identisch sind, ist demnach durch

${\frac {n!}{k!}}$

gegeben. Gibt es nicht nur eine, sondern $s$ Gruppen mit jeweils $k_{1},\ldots ,k_{s}$ identischen Objekten, so können all diese Objekte auf ihren Plätzen vertauscht werden, ohne dass sich neue Anordnungen ergeben. Zählt man auch die Objekte, die nur einmal vorkommen, mit Vielfachheit $1$, dann gilt $k_{1}+\ldots +k_{s}=n$ und die Anzahl der möglichen Permutationen wird durch

${\frac {n!}{k_{1}!\cdot \ldots \cdot k_{s}!}}$

angeben.

Quelle: http://de.wikipedia.org/wiki/Permutation#Permutation_mit_Wiederholung

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

Nach dem Anwenden der Definition der Permutation mit Wiederholung ergibt sich:

$|K(m,n)|={\frac {(m+n)!}{m!\cdot n!}}={\binom {m+n}{m}}={\binom {m+n}{n}}$

Die Darstellung als Binomialkoeffizient ergibt sich aus der Definition ebenjenes.

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

Für (a) ergeben sich also ${\frac {(6+4)!}{6!\cdot 4!}}=210$ verschiedene Möglichkeiten, von links unten nach rechts oben zu gelangen.

(b) 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?

$f:(w_{1},\ldots ,w_{m+n})\mapsto \{i|w_{i}=r\}\subseteq \{1,2,\ldots ,m+n\}$

-- Superwayne 23:23, 22. Nov. 2014 (CET)