Gitterwege

26.11.2017, 19:21

FelNa1109

Gitterwege

"Wir schauen uns die Gitterwege eines N x M Gitters von (0,0) nach (N,M) an. Diesmal sei N = M, d.h. die Wege führen von der linken unteren Ecke zur rechten oberen Ecke des N×N-Quadrats. Wir wollen zwei Gitterwege als äquivalent betrachten, wenn wir sie durch eine Drehung oder Spiegelung miteinander zur Deckung bringen können. Wieviele wesentlich verschiedene Pfade gibt es dann?"

Ich hätte mir jetzt als erstes mal folgendes überlegt:

Wir interessieren uns ja für die Wege von links unten nach rechts oben, also können wir ja nicht jede Drehung oder Spiegelung betrachten. Zum Beispiel würde ja eine Drehung um 90° aus der Menge raus führen. Möglich wäre demnach die Identität, Drehung um 180°, Spiegelung an den Diagonalen.
Als Hinweis soll ich die Pfade als Folgen $\begin{eqnarray*} \left(w_1, ..., w_{2N}\right) , w_i\in\left\{ h,r\right\} \end{eqnarray*}$ interpretieren, wobei h hoch und r rechts sind.

Und es gibt ja insgesammt $\begin{eqnarray*} N+N \end{eqnarray*}$ Verbindungen, wobei ein Pfad durch die Platzierungen der horizontalen oder vertikalen Wege definiert ist. Also müsste:

die Anzahl aller Wege $\begin{eqnarray*} \begin{pmatrix} 2N \\ N \end{pmatrix} \end{eqnarray*}$ sein.

27.11.2017, 07:37

HAL 9000

Auf diesen Beitrag antworten »

D.h., dein vorheriger Thread enthält (mit n=2N und k=n) eine hier brauchbare Hilfsaussage. Augenzwinkern

Zitat:

Original von FelNa1109
Also müsste die Anzahl aller Wege $\begin{eqnarray*} \begin{pmatrix} 2N \\ N \end{pmatrix} \end{eqnarray*}$ sein.

Richtig.

27.11.2017, 09:13

FelNa1109

Auf diesen Beitrag antworten »

Meinst du ich kann für die 180° Drehung den 1. Fall: n gerade hier verwenden, da mit n = 2N und k=N, n immer gerade sein muss? Damit gäbe es $\begin{eqnarray*} \begin{pmatrix} N \\ N/2 \end{pmatrix} \end{eqnarray*}$ Möglichkeiten?

27.11.2017, 09:21

HAL 9000

Auf diesen Beitrag antworten »

Das wäre für den Fall "N gerade" die Anzahl der Pfade, die bei Drehung 180° in sich selbst übergehen. Das ist dann einer der Hilfswerte, die in die Burnside-Frobenius-Formel eingehen, um die letztlich hier im Thread gesuchte Anzahl zu bestimmen, ja.

Die zweite Kategorie wäre die Pfade, die an der Diagonale "links unten - rechts oben" gespiegelt in sich selbst übergehen. Davon gibt es keine - sollte klar sein.

Schließlich und endlich gibt es als dritte Kategorie die Pfade, die bei Spiegelung an der Diagonale "links oben - rechts unten" in sich selbst übergehen. Davon gibt es eine ganze Menge... bin gespannt auf deine Überlegungen dazu.

27.11.2017, 10:03

FelNa1109

Auf diesen Beitrag antworten »

Meine Idee wäre, für die Diagonale von l.o. nach r.u. das ich die Wege von $\begin{eqnarray*} (0,0) \end{eqnarray*}$ nach $\begin{eqnarray*} (N,N) \end{eqnarray*}$ mit einer Geraden $\begin{eqnarray*} x+y=N \end{eqnarray*}$ klassifiziere.

Wenn der Schnittpunkt durch $\begin{eqnarray*} i \end{eqnarray*}$ vorgegeben ist, dann müsste ja...

$\begin{eqnarray*} \begin{pmatrix} N \\ N-i \end{pmatrix} \end{eqnarray*}$ Anzahl der Mögl. zum Schnittpunkt zu gehen,

$\begin{eqnarray*} \begin{pmatrix} N \\ i \end{pmatrix} \end{eqnarray*}$ Anzahl der Mögl. nach Schnittpunkt weiter zu gehen sein

Da jeder Weg einmal die Gerade schneidet, ergibt sich die Gesamtzahl, wenn ich über alle $\begin{eqnarray*} i \end{eqnarray*}$ summiere, also:

$\begin{eqnarray*} \sum\limits_{i\geq 0}^{} \begin{pmatrix} N \\ N-i \end{pmatrix} \begin{pmatrix} N \\ i \end{pmatrix} \end{eqnarray*}$

27.11.2017, 10:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von FelNa1109
Meine Idee wäre, für die Diagonale von l.o. nach r.u. das ich die Wege von $\begin{eqnarray*} (0,0) \end{eqnarray*}$ nach $\begin{eqnarray*} (N,N) \end{eqnarray*}$ mit einer Geraden $\begin{eqnarray*} x+y=N \end{eqnarray*}$ klassifiziere.

Wenn der Schnittpunkt durch $\begin{eqnarray*} i \end{eqnarray*}$ vorgegeben ist, dann müsste ja...

$\begin{eqnarray*} \begin{pmatrix} N \\ N-i \end{pmatrix} \end{eqnarray*}$ Anzahl der Mögl. zum Schnittpunkt zu gehen,

$\begin{eqnarray*} \begin{pmatrix} N \\ i \end{pmatrix} \end{eqnarray*}$ Anzahl der Mögl. nach Schnittpunkt weiter zu gehen sein

Da jeder Weg einmal die Gerade schneidet, ergibt sich die Gesamtzahl, wenn ich über alle $\begin{eqnarray*} i \end{eqnarray*}$ summiere, also:

$\begin{eqnarray*} \sum\limits_{i\geq 0}^{} \begin{pmatrix} N \\ N-i \end{pmatrix} \begin{pmatrix} N \\ i \end{pmatrix} \end{eqnarray*}$

Grundsätzlicher Denkfehler: Der Weg nach dem Schnittpunkt mit Gerade x+y=N ist durch die Spiegelungsbedingung festgeklopft - da gibt es nichts mehr zu wählen. Tatsächlich ist die Anzahl also einfach $\begin{eqnarray*} \sum_{i=0}^N\binom{N}{i}=2^N \end{eqnarray*}$ .

Dieser Wert $\begin{eqnarray*} 2^N \end{eqnarray*}$ ergibt sich auch durch eine einfachere Überlegung: Die ersten $\begin{align*} N \end{align*}$ Schritte können beliebig (!) sein - man landet garantiert auf dieser Diagonalen x+y=N. Der Rest ist dann durch die Spiegelungsbedingung festgelegt.

--------------------------------------

So, und jetzt ist alles gut angerichtet für Burnside-Frobenius. smile

27.11.2017, 11:08

FelNa1109

Auf diesen Beitrag antworten »

Dankeschön, deine Ratschläge helfen mir wirklich jedes Mal sehr weiter smile

27.11.2017, 15:16

FelNa1109

Auf diesen Beitrag antworten »

So, hier Burnside-Frobenius:

$\begin{eqnarray*} | M | = \frac{1}{4} \left(\begin{pmatrix} 2N \\ N \end{pmatrix} + \begin{pmatrix} N \\ N/2 \end{pmatrix} + 0 + 2^N \right) \end{eqnarray*}$

stimmt das so?
Wink

27.11.2017, 15:17

HAL 9000

Auf diesen Beitrag antworten »

Im Fall "N gerade" ist das richtig. Im Fall "N ungerade" fällt der Term $\begin{align*} \binom{N}{N/2} \end{align*}$ ersatzlos weg.

Neue Frage »

Antworten »

Gitterwege

Verwandte Themen