Anzahl Touren in Z² < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:23 Di 12.05.2009 | | Autor: | Held |
| Aufgabe | | Wie viele Touren von (0,0) nach (0,0) gibt es in [mm] \IZ \times \IZ [/mm] mit n Schritten? |
Ich habe die Frage in keinem anderem Forum gestellt.
Ich glaube das ist ein bekanntes Problem, habe aber bei Google nix gefunden.
Meine Idee war, alle möglichen Wege zu gehen bis n/2 und von dort aus alle zurück.
Ich hab auch z.B. herausgefunden das es [mm] \vektor{n \\ k} [/mm] Wege gibt um nach (n, n-k) zu kommen,
ohne Wiederholungen wenn ich [mm] \IN \times \IN [/mm] betrachte. Allerdings fehlen mir hierbei alle möglichen
Touren die Wiederholung haben und ich weiß nicht wieviele Möglichkeiten es gibt zurückzugehen.
Kennt jemand eine gute Lösung? Link wär auch toll!
Gruß Held
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:35 Di 12.05.2009 | | Autor: | abakus |
> Wie viele Touren von (0,0) nach (0,0) gibt es in [mm]\IZ \times \IZ[/mm]
> mit n Schritten?
> Ich habe die Frage in keinem anderem Forum gestellt.
>
> Ich glaube das ist ein bekanntes Problem, habe aber bei
> Google nix gefunden.
> Meine Idee war, alle möglichen Wege zu gehen bis n/2 und
> von dort aus alle zurück.
> Ich hab auch z.B. herausgefunden das es [mm]\vektor{n \\ k}[/mm]
> Wege gibt um nach (n, n-k) zu kommen,
> ohne Wiederholungen wenn ich [mm]\IN \times \IN[/mm] betrachte.
> Allerdings fehlen mir hierbei alle möglichen
> Touren die Wiederholung haben und ich weiß nicht wieviele
> Möglichkeiten es gibt zurückzugehen.
>
> Kennt jemand eine gute Lösung? Link wär auch toll!
Hallo,
ich weiß nicht, ob es hilft: Um von (0|0) nach (0|0) zu kommen, muss man genau so viele Schritte in positive wie in negative x-Richtung gehen (y-Richtung analog).
Lässt sich das Ganze vielleicht induktiv aufbauen?
Nehmen wir an, es gibt x Touren für n Schritte. Wenn ich stattdessen n+2 Schritte machen darf, kann ich an eine beliebige Stelle jedes bisherigen Wegs einen Zusatzschritt einbauen und muss dafür an eine beliebige andere Stelle den entsprechenden Gegenschritt einbauen.
Gruß Abakus
>
> Gruß Held
|
|
|
|
