Gitterwege zählen

Aufrufe: 244     Aktiv: 12.06.2022 um 23:11

0
Hallo, ich soll Gitterwege zählen und zwar: 



Die Anzahl der Gitterwege ohne Beachtung der Gruppenoperation wäre $2n \choose n$.
Jetzt habe ich zur Visualisierung alle möglichen Gitterwege mit den oben genannten Vorgaben für 2x2 gezeichnet und habe insgesamt 3 verschiedene Gitterwege.

Für die Wegbeschreibung habe ich Codes mit r=rechts und o=oben geschrieben. 
Insgesamt sind es: oorr, orro, oror, rroo, roor, roro
Nach obiger Beschreibung wären oorr=rroo, orro=roor, oror=roro (3 verschiedene Möglichkeiten) 



Ich weiß nicht genau, wie ich alle Gitterwege zähle, ohne die identischen doppelt zu zählen...
Kann jemand helfen?

 
Diese Frage melden
gefragt

Punkte: 20

 
Kommentar schreiben
2 Antworten
-1

Ich finde die Aufgabenstellung ist etwas unklar formuliert dahingehend was u und v genau tun.

bspw "u dreht einen Gitterweg um" könnte man so verstehen dass di Schritte in entgegengesetzter Reihenfolge passieren.

Also wenn oroorro der Weg ist, dann wäre unter Anwendung von u ein dazu gleicher Weg orrooro.

Also die Buchstabenfolge spiegeln sozusagen.

Es könnte aber auch was ganz anderes mit "umdrehen" gemeint sein, wer weiß?

 

Genauso v, hier ist gar nicht klar was gemeint ist.

Was definitiv nicht gmeeint sein kann wäre , jedes alte r durch o und jedes alte o durch r zu ersetzen, denn da käme ein anderer Weg raus (Beispiel: roror würde zu ororo was was Anderes ist!)

 

obwohl es in einem gewissen Sinne schon wieder möglich wäre, nämlich dann wenn die o und r anzahl gleich ist.

Was bei einem n x n grid sein muss.

 

Irgendwo glaube ich fast schon, doch richtig zu liegen, denn es ist ja vorgegeben dass 2 Wege gleich sind wenn sie sich durch EINE Operation unterscheiden.

Das heißt umgekehrt, 2 komplett verschieden AUSSEHENDE Wege sind trotzdem als gleich anzusehen wenn eine Operation den einen in den anderen überführt.

 

Heißt auch, entgegen meiner nicht erwähnten anfänglichen Vermutung,  dass die Operationen nicht nur 2 Zeichen vertauschen, sondern auf den ganzen string angewendet werden.

 

Also wie oben erwähnt alle o und r s miteinander vertauschen im string.

oder den string spiegeln.

 

Am Ende vom Lied gehts nur drum, wie kann man n Blöcke auf 2n stelllen verteilen (wobei blöcke hier rs sein können. oder os. was davon spielt keine rolle da ja mittels v eh austauschbar. geht nur drum dass du n gleiche sachen auf 2n fächer verteilen musst).

Wie man nun sozusagen palindrome (zeichenketten aus o und r s, die von vorne nach hinten und umgekehrt gleich sind) gesondert behandelst?

gute Frage.

 

Wobei eine Idee hätte ich:

Finde erst mal alle Möglichkeiten (rein deren Anzahl), wie man n gleiche sahcen auf 2n felder verteilen kann.

bzw. nutze eine der grundlegenden formeln der kombinatorik, den binomialkoeffizienten.

 

dann bestimme wie viele palindrome es gibt.

nun ziehe von der gesamtanzahl die palindromanzahl ab.

obwohl ich mir gerade nicht sicher bin ob beim binomialkoeffizient palindrome nicht eh von selbst nur einmal gezählt werden.

keine ahnung.

müsstest du einfach mal wo nachlesen :-)

zu den palindromen und deren anzahl:

weil spiegelsymmetrisch und bspw. die anzahl der os gleich n, muss in der hälfte der felder die hälfte der os liegen.

heißt , in (2n)/2=n feldern müssen n/2 os verteilt werden.

also n/2 sachen auf n felder verteilen.

lässt sich gut ausrechnen.

du hast halt den vorteil dass der string immer gerade länge hat, daher ist die anzahl an os und rs immer gleich.

 

TL;DR: Es wird vermutlich sowas wie (2n über n)-(n über n/2) rauskommen :-)

Diese Antwort melden
geantwortet

Student, Punkte: 286

 

$2n \choose n$ - $n \choose n/2$ stimmt leider für ein Beispiel schonmal nicht. Wenn wir ein 2x2 Gitter betrachten und die nach obiger Definition verschiedene Gitterwege zählen möchten, sollte eigentlich 3 herauskommen. $4 \choose 2$ - $2 \choose 1$ ist aber 4.

:/…
  ─   huhu123 09.06.2022 um 11:54

$2n \choose n$ kann man ja schonmal festhalten. Wie ziehe ich aber alle doppelt gezählten ab, weil sie nach obiger Definition gleich sind ?   ─   huhu123 09.06.2022 um 11:56

@zest, hast du vielleicht eine Idee?   ─   huhu123 10.06.2022 um 09:34

Kommentar schreiben