TU Wien:Statistik und Wahrscheinlichkeitstheorie UE (Gurker)/Übungen WS11/Beispiel 1.15

[Kombinatorik] Betrachten Sie das unten angegebene Gitter von Punkten. Sie starten im Punkt A und möchten nach Punkt B. Dabei können Sie nur jeweils einen Schritt nach oben oder nach rechts machen.
(a) Wieviele verschiedene Wege von A nach B gibt es?
(b) Wieviele verschiedene Wege von A nach B verlaufen durch den eingeringelten Punkt?

Lösungsvorschlag

(a)

Eins ist offensichtlich: Es müssen 4 Schritte nach rechts und 3 nach oben gemacht werden.
Die Reihenfolge ist dabei egal.

Wenn man einen Schritt nach oben mit O und einen Schritt nach rechts mit R codiert, könnte ein Weg wie folgt aussehen:
ROORROR oder
RRORORO

Dass macht es klar alle unterschiedlichen Kombinationen einen möglichen Weg repräsentieren.

Wie kommt man nun auf die Anzahl der unterschiedlichen Wege?
Man hat hier 7 Elmente.
Mit diesen hat man 7! unterschiedliche Kombinationen, wenn alle Teile voneinander unterscheidbar sind.
In unserem Fall haben wir allerdings 3 bzw. 4 gleiche Elemente, d.hh. 3!*4! Kombinationen, die voneinander nicht unterscheidbar sind

$\Rightarrow {\frac {(3+4)!}{3!\cdot 4!}}=35$

(b)

Durch die Einschränkung ergibt sich folgendes Muster

mit der gleichen Überlegung wie oben kommt man für den linken unteren Teil ${\frac {(2+2)!}{2!\cdot 2!}}=6$ Wege und für den rechten oberen Teil ${\frac {(2+1)!}{2!\cdot 1!}}=3$ Wege.

In Summe gibt das $6\cdot 3=18$ unterschiedliche Wege (jeder der 6 Wege kann im oberen Teil auf 3 unterschiedliche Varianten zu Ende geführt werden)