Kombinatorik: Mögliche Wege ermitteln?
Mein Ansatz wäre zu sagen, da man kein Umweg machen darf kommt nur das weiterfahren gen Norden oder Westen in Frage. Somit hat man an jeder Kreuzung 2 mögliche Wege die man nehmen kann. Es gibt auch da es m N-S-Straßen und n W-O-Straßen gibt die sich alle kreuzen m*n-Kreuzungen oder ? Sind meine bisherigen Informationen richtig ? Wenn ja, hat jemand einen Ansatz um der Lösung näherzukommen oder muss ich die Aufgabe anders angehen ?
2 Antworten
https://www.gutefrage.net/frage/wie-komme-ich-zum-richtigen-ergebnis
Es gibt n ⋅ m Kreuzungen. Zur Lösung schaut man sich aber die n + m Straßen in einer Lösung und deren Permutationen an.
Du hast recht, es gibt m*n Kreuzungen. Aber nicht an jeder Kreuzung kann er sich entscheiden, ist er nämlich ganz oben im Norden angekommen, kann er nur noch nach Osten weiter fahren (und umgekehrt).
Du kannst dir das so vorstellen: für eine Entscheidung nach Norden schreibst du eine 0 auf, für eine Entscheidung Richtung Osten eine 1.
Du bekommst dann so einen Ausdruck aus lauter 0'en und 1'en:
0010010111... usw.
Insgesamt ist dieser Ausdruck m+n lang - denn er braucht insgesamt ja m+n Schritte, davon gehen m in Richtung Osten (jedesmal überquert er eine Straße, die in Nord-Süd-Richtung verläuft) und n gehen in Richtung Norden.
Du brauchst also alle Ausdrücke der Form von oben, in denen genau n 0'en und m 1'en vorkommen.
Jetzt kannst du weiter überlegen.