Permutationen beim Domino < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | Unser Domino-Spiel hat n*n Spielsteine, n ist die Zahl der verschiedenen Markierungen pro Seite. Ein Spiel mit null bis fünf Punkten hat demnach 36 Spielsteine.
Mit den Steinen soll eine Kette ohne Verzweigungen gebildet werden, wobei kein Stein herumgedreht werden darf. Dabei müssen Sie wie bei den Original-Regeln immer die gleiche Augenzahl aneinander legen.
Eine gültige und eine ungültige Kette mit n=3 zeigen die Abb. 1 und 2. Die drei markierten Steine in Abb. 2 liegen falsch herum, deshalb ist diese Kette für unser Spiel ungültig.
0/1 → 1/2 → 2/1 → 1/1 → 1/0 → 0/2 → 2/2 → 2/0 → 0/0 Abb. 1
1/2 → 2/2→ 2/0 → 0/1 → 1/1→ [mm] \red{1/2} [/mm] → [mm] \red{ 2/0} [/mm] → 0/0 → [mm] \red{0/1} \qquad Abb. [/mm] 2
Wichtiger Hinweis zur Datenstruktur:
Nehmen wir an, wir haben n=2 und damit die Augenzahl Null und Eins. Es ergeben sich folgende Augenpaare:
0/0; 0/1; 1/0; 1/1
a) Wieviele mögliche Ketten gibt es für n=3? Geben Sie ggf. eine Beziehung zur Berechnung der Möglichkeiten an!
|
Ich suche vor allem die allgemeine Beziehung zur Berechnung der Anzahl der möglichen Ketten. Ich meine, dass ich gelesen habe, dass folgende Beziehung gelten soll: n!*n.
Kann mir da jemand bitte weiterhelfen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:38 Di 16.03.2010 | | Autor: | karma |
Hallo und guten Morgen,
wir haben $n=3$ und damit die Augenzahlen Null, Eins und Zwei.
Unser Spiel hat [mm] $3\* [/mm] 3=9$ Spielsteine,
und zwar
0/0
0/1
0/2
1/0
1/1
1/2
2/0
2/1
2/2
Die kürzesten Ketten haben die Länge $2$.
[mm] $0/0\to\ [/mm] 0/1$,
[mm] $0/0\to\ [/mm] 0/2$,
[mm] $0/1\to\ [/mm] 1/0$,
[mm] $0/1\to\ [/mm] 1/1$,
[mm] $0/1\to\ [/mm] 1/2$,
[mm] $0/2\to\ [/mm] 2/0$,
[mm] $0/2\to\ [/mm] 2/1$,
[mm] $0/2\to\ [/mm] 2/2$,
-----------------
[mm] $1/0\to\ [/mm] 0/0$,
[mm] $1/0\to\ [/mm] 0/1$,
[mm] $1/0\to\ [/mm] 0/2$,
[mm] $1/1\to\ [/mm] 1/0$,
[mm] $1/1\to\ [/mm] 1/2$,
[mm] $1/2\to\ [/mm] 2/0$,
[mm] $1/2\to\ [/mm] 2/1$,
[mm] $1/2\to\ [/mm] 2/2$,
-----------------
[mm] $2/0\to\ [/mm] 0/0$,
[mm] $2/0\to\ [/mm] 0/1$,
[mm] $2/0\to\ [/mm] 0/2$,
[mm] $2/1\to\ [/mm] 1/0$,
[mm] $2/1\to\ [/mm] 1/1$,
[mm] $2/1\to\ [/mm] 1/2$,
[mm] $2/2\to\ [/mm] 2/0$,
[mm] $2/2\to\ [/mm] 2/1$.
Das sind [mm] $24=3\* 8=n\* (n\* [/mm] n -1)$ Ketten der Länge $2$
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:49 Mi 17.03.2010 | | Autor: | karma |
Hallo und guten Tag,
für $n=2$ gibt es $4$ Ketten der Länge [mm] $2\* [/mm] 2=4$,
für $n=3$ gibt es $216$ Ketten der Lange [mm] $3\* [/mm] 3=9$.
Ich tippe auf [mm] $(n-1)^{n}\* n^{n}$ [/mm] Ketten der Länge [mm] $n\* [/mm] n$.
Der Beweis der Vermutung müßte noch geführt werden,
z.B. mit vollstandiger Induktion.
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:34 Mi 17.03.2010 | | Autor: | pelzig |
> Hallo und guten Tag,
>
> für [mm]n=2[/mm] gibt es [mm]4[/mm] Ketten der Länge [mm]2\* 2=4[/mm],
> für [mm]n=3[/mm]
> gibt es [mm]216[/mm] Ketten der Lange [mm]3\* 3=9[/mm].
Wie kommst du auf 216?
> Ich tippe auf [mm](n-1)^{n}\* n^{n}[/mm] Ketten der Länge [mm]n\* n[/mm].
>
> Der Beweis der Vermutung müßte noch geführt werden,
> z.B. mit vollstandiger Induktion.
Wie kommst du denn darauf? Das widerspricht doch total dem, was Tobias und ich uns weiter unten überlegt haben, denn dort haben wir denke ich ziemlich gut skizziert, dass z.B. n! stets die Anzahl der möglichen Ketten teilt. Bei deiner Formel teilt z.B. 3 nicht [mm] $(5-1)^5\cdot 5^5$ [/mm] (man schaue sich die Primfaktoren an).
Beste Grüße,
Robert
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:30 Di 16.03.2010 | | Autor: | karma |
Hallo und guten Tag,
$n=2$,
Augenpaare:
0/0; 0/1; 1/0; 1/1,
wie angegeben.
Würde gelten:
Anzahl der möglichen Ketten gleich [mm] $n\* [/mm] n!$,
dann dürfte es im Falle $n=2$ nur [mm] $2\* [/mm] 2!=4$
Dominoketten geben.
Es gibt aber schon sechs mögliche Ketten der Länge zwei,
und zwar:
[mm] $0/0\to\ [/mm] 0/1$ bzw. $00\ 01$,
[mm] $0/1\to\ [/mm] 1/0$ bzw. $01\ 10$,
[mm] $0/1\to\ [/mm] 1/1$ bzw. $01\ 11$,
-----------------------------
[mm] $1/0\to\ [/mm] 0/0$ bzw. $10\ 00$,
[mm] $1/0\to\ [/mm] 0/1$ bzw. $10\ 01$,
[mm] $1/1\to\ [/mm] 1/0$ bzw $11\ 10$.
Die längste Kette bei $n=2$ ist übrigens vier Dominosteine lang;
welche solcher Ketten gibt es,
wieviele sind es?
Wieviel Ketten der Länge drei gibt es bei $n=2$?
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:29 Di 16.03.2010 | | Autor: | tobit09 |
Hallo,
> Würde gelten:
> Anzahl der möglichen Ketten gleich [mm]n\* n![/mm],
> dann dürfte
> es im Falle [mm]n=2[/mm] nur [mm]2\* 2!=4[/mm]
> Dominoketten geben.
>
> Es gibt aber schon sechs mögliche Ketten der Länge zwei, und zwar:
Ich verstehe die Aufgabenstellung so, dass nach Ketten ALLER Dominosteine (also nach Ketten der Länge [mm] $n^2$) [/mm] gefragt ist. Davon gibt es in der Tat für $n=2$ nur 4, wie man durch explizites Ermitteln aller dieser Ketten sehen kann.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:38 Di 16.03.2010 | | Autor: | tobit09 |
Hallo,
also ehrlich gesagt: Ich bin an der Aufgabe für beliebiges n völlig gescheitert! Mir erscheint sie für die Schule definitiv zu schwer zu sein! Habt ihr irgendwelche Tipps bekommen?
Für $n=3$ bin ich durch manuelles Durchspielen einzelner Möglichkeiten auf eine Lösung von [mm] $7*3^2*2$ [/mm] gekommen. Aber gut möglich, dass ich mich unterwegs irgendwo vertan habe.
Auf jeden Fall gibt es für $n=3$ jedoch mehr als $n!*n=3*2*1*3$ Möglichkeiten, so dass die von dir vermutete Formel nicht stimmen kann.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:40 Di 16.03.2010 | | Autor: | tobit09 |
Hallo,
hat irgendjemand eine Idee, wie man das Problem für beliebiges n lösen könnte?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:29 Di 16.03.2010 | | Autor: | pelzig |
Nur sone Idee in welche Richtung man das Problem lenken könnte... vielleicht kann man hier mit Graphentheoretischen Methoden irgendwas machen. Also Definiere [mm] $V_n:=\IN_n^2:=\{0,1,...,n-1\}^2$ [/mm] und [mm] $E_n:=\{((a,b),(c,d))\in V_n^2\mid b=c\text{ und }a\ne d\}$, [/mm] dann ist [mm] $G_n:=(V_n,E_n)$ [/mm] fuer jedes [mm] $n\in\IN$ [/mm] ein gerichteter Graph. Eine vollständige Dominokette ist nun nichts weiter als ein Eulerpfad in [mm] $G_n$. [/mm] Wir fragen nach der Anzahl [mm] $\kappa_n$ [/mm] der Eulerpfade in [mm] $G_n$ [/mm] (siehe Wikipedia für die ganzen Begriffe, da hab ich auch nur geguckt).
Nun kann man sich überlegen:
1) Jedes [mm] $G_n$ [/mm] ist ein Eulergraph, d.h. es existiert mindestens ein Eulerkreis, denn [mm] $G_n$ [/mm] ist (stark) zusammenhängend und jeder Punkt hat genauso viele Eingangs- wie Ausgangskanten. Mit anderen Worten es existiert zumindest schonmal eine Lösung für das Dominospiel, Glück gehabt.
2) Es gibt eine wichtige Symmetrie in [mm] $G_n$, [/mm] nämlich anschaulich indem ich einfach die Beschriftung der Dominosteine permutiere, oder expliziter: [mm] $\operatorname{Aut}(G_n)$ [/mm] enthält zumindest schonmal die Abbildungen der Form [mm] $(a,b)\mapsto(\sigma(a),\sigma(b))$ [/mm] fuer festes [mm] $\sigma\in\operatorname{Bij}(\IN_n)$, [/mm] also [mm] $|Aut(G_n)|\ge|\operatorname{Bij}(\IN_n)|=n!$
[/mm]
Jeder Automorphismus übersetzt nun Eulerpfade in Eulerpfade, also folgt aus 1) und 2) nun [mm] $\kappa_n\ge [/mm] 1$ und $n!\ [mm] \big|\ \kappa_n$, [/mm] insbesondere [mm] $\kappa_n\ge [/mm] n!$, das ist doch schon ganz beachtlich. Zumindest sollte klar werden, wie der Faktor $n!$ hier ins Spiel kommt.
Wenn man noch mehr Symmetrien von [mm] $G_n$ [/mm] findet kann man diese untere Schranke natuerlich noch weiter hochschrauben, interessanter waere aber natuerlich, wirklich qualitativ verschiedene Eulerkreise zu finden...
Edit: Ich habe noch eine interessante Eigenschaft von [mm] $G_n$ [/mm] gefunden: Betrachtet man denselben Graphen aber mit den entgegengesetzt gerichteten Kanten (nennen wir das mal [mm] $-G_n$), [/mm] dann ist das isomorph via [mm] $(a,b)\mapsto [/mm] (b,a)$ zu [mm] $G_n$. [/mm] Ich weiß aber im Moment nicht was das zu bedeuten hat 
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:38 Di 16.03.2010 | | Autor: | tobit09 |
Hallo Robert,
vielen Dank für deine Antwort!
> Nur sone Idee in welche Richtung man das Problem lenken
> könnte... vielleicht kann man hier mit
> Graphentheoretischen Methoden irgendwas machen.
Das erscheint mir tatsächlich ein viel versprechender Ansatz zu sein; die Graphentheorie scheint in der Tat eine gute Sprache zu sein, um das Problem zu erfassen und auf vorhandene Theorie zurückgreifen zu können!
> Definiere [mm]V_n:=\IN_n^2:=\{0,1,...,n-1\}^2[/mm] und
> [mm]E_n:=\{((a,b),(c,d))\in V_n^2\mid b=c\text{ und }a\ne d\}[/mm],
> dann ist [mm]G_n:=(V_n,E_n)[/mm] fuer jedes [mm]n\in\IN[/mm] ein gerichteter
> Graph. Eine vollständige Dominokette ist nun nichts weiter
> als ein Eulerpfad in [mm]G_n[/mm].
Nein. Laut Wikipedia werden bei einem Eulerpfad alle KANTEN des Graphen genau einmal durchlaufen. Wir benötigen jedoch, dass alle KNOTEN genau einmal durchlaufen werden.
Eine vielleicht hilfreiche Beobachtung ist, dass in jeder gesuchten Kette die hintere Augenzahl des letzten Dominosteins mit der vorderen Augenzahl des ersten Dominosteines übereinstimmt (dazu beachte man, dass jede Augenzahl auf genau n Dominosteinen die hintere und auf genau n Dominosteinen die vordere ist).
Wir können daher anstatt von Wegen, die jeden Knoten genau einmal durchlaufen, genauso gut Hamiltonkreise (siehe wieder Wikipedia) betrachten.
> Wir fragen nach der Anzahl
> [mm]\kappa_n[/mm] der Eulerpfade in [mm]G_n[/mm] (siehe Wikipedia für die
> ganzen Begriffe, da hab ich auch nur geguckt).
Ich erlaube mir mal, ab jetzt mit [mm] $\kappa_n$ [/mm] die tatsächlich gesuchte Anzahl der Hamiltonkreise in [mm] $G_n$ [/mm] zu bezeichnen, damit das Weitere besser passt.
> 1) Jedes [mm]G_n[/mm] ist ein Eulergraph, d.h. es existiert
> mindestens ein Eulerkreis, denn [mm]G_n[/mm] ist (stark)
> zusammenhängend und jeder Punkt hat genauso viele
> Eingangs- wie Ausgangskanten. Mit anderen Worten es
> existiert zumindest schonmal eine Lösung für das
> Dominospiel, Glück gehabt.
Das passt dann natürlich mit Hamiltonkreisen statt Eulergraphen so nicht mehr. Meine Wikipedia-Recherche zu hinreichenden Bedingungen für die Existenz von Hamiltonkreisen hat mich leider nicht schlau gemacht, da die dortigen Bedingungen nur für ungerichtete Graphen zu gelten scheinen.
> 2) Es gibt eine wichtige Symmetrie in [mm]G_n[/mm], nämlich
> anschaulich indem ich einfach die Beschriftung der
> Dominosteine permutiere, oder expliziter:
> [mm]\operatorname{Aut}(G_n)[/mm] enthält zumindest schonmal die
> Abbildungen der Form [mm](a,b)\mapsto(\sigma(a),\sigma(b))[/mm] fuer
> festes [mm]\sigma\in\operatorname{Bij}(\IN_n)[/mm], also
> [mm]|Aut(G_n)|\ge|\operatorname{Bij}(\IN_n)|=n![/mm]
Man kann sich sogar überlegen, dass [mm] $\operatorname{Aut}(G_n)$ [/mm] nur aus diesen Abbildungen bestehen kann.
> Jeder Automorphismus übersetzt nun Eulerpfade in
> Eulerpfade,
Geht mit Hamiltonkreisen statt Eulerpfaden haargenau so.
> also folgt aus 1) und 2) nun [mm]\kappa_n\ge 1[/mm] und
> [mm]n!\ \big|\ \kappa_n[/mm], insbesondere [mm]\kappa_n\ge n![/mm], das ist
> doch schon ganz beachtlich. Zumindest sollte klar werden,
> wie der Faktor [mm]n![/mm] hier ins Spiel kommt.
Zumindest $n!\ [mm] \big|\ \kappa_n$ [/mm] bleibt gültig.
> Wenn man noch mehr Symmetrien von [mm]G_n[/mm] findet kann man diese
> untere Schranke natuerlich noch weiter hochschrauben,
S.o.: Weitere Symmetrien gibt es nicht. Eine andere Möglichkeit, die Schranke (unter der unbewiesenen Annahme, dass mindestens eine gesuchte Kette existiert) für manche n etwas hochzuschrauben: Mithilfe der Idee, dass man mit jedem Hamiltonkreis durch Variation des Anfangsknotens gleich [mm] $|V_n|=n^2$ [/mm] verschiedene Hamiltonkreise erhält, kann man sich [mm] $n^2\big|\kappa_n$ [/mm] überlegen.
> interessanter waere aber natuerlich, wirklich qualitativ
> verschiedene Eulerkreise zu finden...
Wenn damit gemeint ist, dass die Hamiltonkreise nicht durch Automorphismen auseinander hervorgehen, gibt es solche qualitativ verschiedenen Hamiltonkreise schon im Fall $n=2$. Im Falle $n=3$ gibt es auch Hamiltonkreise, die noch nicht einmal durch eine Kombination von Automorphismen und Variationen des Anfangsknotens auseinander hervorgehen.
Nochmal danke für deine tollen Impulse!
Kennt sich jemand mit Hamiltonkreisen in gerichteten Graphen aus und kennt hinreichende Bedingungen für deren Existenz oder hat gar eine Idee, wie man die Anzahl der Hamiltonkreise in diesem Graphen bestimmen könnte?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:14 Di 16.03.2010 | | Autor: | pelzig |
> > Eine vollständige Dominokette ist nun nichts weiter
> > als ein Eulerpfad in [mm]G_n[/mm].
> Nein. Laut Wikipedia werden bei einem Eulerpfad alle
> KANTEN des Graphen genau einmal durchlaufen. Wir benötigen
> jedoch, dass alle KNOTEN genau einmal durchlaufen werden.
Ok, nennen wir einen solchen Pfad, der alle Knoten genau einmal durchläuft mal "Dominopfad".
> Eine vielleicht hilfreiche Beobachtung ist, dass in jeder
> gesuchten Kette die hintere Augenzahl des letzten
> Dominosteins mit der vorderen Augenzahl des ersten
> Dominosteines übereinstimmt (dazu beachte man, dass jede
> Augenzahl auf genau n Dominosteinen die hintere und auf
> genau n Dominosteinen die vordere ist).
Ja... eigentlich trivial, aber es muss auch mal gesagt werden, mir ist das jedenfalls noch nicht aufgefallen.
> Wir können daher anstatt von Wegen, die jeden Knoten genau
> einmal durchlaufen, genauso gut Hamiltonkreise (siehe
> wieder Wikipedia) betrachten.
Ja.
> > Wir fragen nach der Anzahl
> > [mm]\kappa_n[/mm] der Eulerpfade in [mm]G_n[/mm] (siehe Wikipedia für die
> > ganzen Begriffe, da hab ich auch nur geguckt).
> Ich erlaube mir mal, ab jetzt mit [mm]\kappa_n[/mm] die
> tatsächlich gesuchte Anzahl der Hamiltonkreise in [mm]G_n[/mm] zu
> bezeichnen, damit das Weitere besser passt.
Ja, so wars ja auch gedacht.
> Das passt dann natürlich mit Hamiltonkreisen statt
> Eulergraphen so nicht mehr. Meine Wikipedia-Recherche zu
> hinreichenden Bedingungen für die Existenz von
> Hamiltonkreisen hat mich leider nicht schlau gemacht, da
> die dortigen Bedingungen nur für ungerichtete Graphen zu
> gelten scheinen.
Okay, aber die Existenz eines Dominopfades kann man in diesem speziellen Fall auch per Hand zeigen, z.B. mit Induktion über $n$:
Der Induktionsanfang ist klar, Nun betrachte [mm] $D_{n+1}$ [/mm] und entferne alle Knoten, die irgendwo $n$ stehen haben (und die Kanten die da dran hängen natürlich auch) und bemerke dass der entstehende Teilgraph [mm] $E\subset D_{n+1}$ [/mm] kanonisch isomorph zu [mm] $D_n$ [/mm] ist, in dem aber nach I.V. ein Dominopfad existiert, also auch in $E$. Nun überzeuge man sich, dass man diesen Dominopfad in $E$ zu einem in [mm] $D_{n+1}$ [/mm] erweitern kann... fertig. (Vereinfacht gesagt: Nimm einfach alle Dominosteine mit der höchsten Zahl weg, lege aus den übrigen einen Dominopfad und dann bastel die weggenommenen Steine wieder ans Ende. Dass das klappt ist nicht ganz klar, sieht man aber schnell ein)
Die Tatsache, dass hier $E$ isomorph zu [mm] $D_n$ [/mm] war, finde ich an sich schon sehr bemerkenswert. Insbesondere bedeutet dass, dass man alle [mm] $D_n$ [/mm] auch als Teilgraph einer viel umfassenderen Struktur, quasi [mm] $D_\infty$ [/mm] auffassen kann (sollte klar sein, was ich damit meine). Vielleicht bringt es also auch was, diese Struktur genauer zu untersuchen...
> > 2) Es gibt eine wichtige Symmetrie in [mm]G_n[/mm], nämlich
> > anschaulich indem ich einfach die Beschriftung der
> > Dominosteine permutiere, oder expliziter:
> > [mm]\operatorname{Aut}(G_n)[/mm] enthält zumindest schonmal die
> > Abbildungen der Form [mm](a,b)\mapsto(\sigma(a),\sigma(b))[/mm] fuer
> > festes [mm]\sigma\in\operatorname{Bij}(\IN_n)[/mm], also
> > [mm]|Aut(G_n)|\ge|\operatorname{Bij}(\IN_n)|=n![/mm]
> Man kann sich sogar überlegen, dass
> [mm]\operatorname{Aut}(G_n)[/mm] nur aus diesen Abbildungen bestehen kann.
Hmm... wie? Ich hätte irgendwie gar nicht erwartet, dass man die Automorphismengruppe einfach hinschreiben kann
> > Jeder Automorphismus übersetzt nun Eulerpfade in Eulerpfade,
> Geht mit Hamiltonkreisen statt Eulerpfaden haargenau so.
>
> > also folgt aus 1) und 2) nun [mm]\kappa_n\ge 1[/mm] und
> > [mm]n!\ \big|\ \kappa_n[/mm], insbesondere [mm]\kappa_n\ge n![/mm], das ist
> > doch schon ganz beachtlich. Zumindest sollte klar werden,
> > wie der Faktor [mm]n![/mm] hier ins Spiel kommt.
> Zumindest [mm]n!\ \big|\ \kappa_n[/mm] bleibt gültig.
>
> > Wenn man noch mehr Symmetrien von [mm]G_n[/mm] findet kann man diese
> > untere Schranke natuerlich noch weiter hochschrauben,
> S.o.: Weitere Symmetrien gibt es nicht. Eine andere
> Möglichkeit, die Schranke (unter der unbewiesenen Annahme,
> dass mindestens eine gesuchte Kette existiert) für manche
> n etwas hochzuschrauben: Mithilfe der Idee, dass man mit
> jedem Hamiltonkreis durch Variation des Anfangsknotens
> gleich [mm]|V_n|=n^2[/mm] verschiedene Hamiltonkreise erhält, kann
> man sich [mm]n^2\big|\kappa_n[/mm] überlegen.
Das stimmt, ich denke das Problem ist aber, dass wir bisher noch nicht die richtigen Symmetrien betrachtet haben. Für uns relevant sind ja eigentlich die Abbildungen, die Dominopfade auf Dominopfade abbilden. Diese Abbildungen müssen ja zwangsläufig bijektiv sein, und ich vermute mal, dass sie auch eine Untergruppe [mm] $\operatorname{Sym}(D_n)$ [/mm] von [mm] $\operatorname{Bij}(V_n)$ [/mm] bilden (die aber sicherlich [mm] $\operatorname{Aut}(D_n)$ [/mm] enthält). Die eigentliche Idee war ja nun, dass [mm] $|\operatorname{Sym}(D_n)|\ \big|\ \kappa_n$, [/mm] das müsste man aber auch erstmal genau zeigen.
> > interessanter waere aber natuerlich, wirklich qualitativ
> > verschiedene Eulerkreise zu finden...
> Wenn damit gemeint ist, dass die Hamiltonkreise nicht
> durch Automorphismen auseinander hervorgehen, gibt es
> solche qualitativ verschiedenen Hamiltonkreise schon im
> Fall [mm]n=2[/mm].
Ja, z.B. durch solche "Shifts" wie du sie oben beschrieben hast, also z.B.
(0,0),(0,1),(1,1),(1,0) und (0,1),(1,1),(1,0),(0,0). Man muss aber aufpassen, denn wenn man den zweiten Kreis jetzt nochmal shiftet, dann landet man schon wieder beim ersten (modulo des Automorphismus [mm] $0\leftrightarrow 1$).
> Im Falle [/mm] [mm]n=3[/mm] gibt es auch Hamiltonkreise, die
> noch nicht einmal durch eine Kombination von Automorphismen
> und Variationen des Anfangsknotens auseinander
> hervorgehen.
Ich hab mir diesen Fall gar nicht genauer angeschaut, war mir zu kompliziert
Naja, ich denk hier könnte man noch ne ganze Weile knobeln.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:48 Mi 17.03.2010 | | Autor: | tobit09 |
Vorweg: Meine Behauptung [mm] $\kappa_3=7*3^2*2$ [/mm] war falsch, ich habe einige Möglichkeiten übersehen. Deine Überlegungen haben mich darauf gebracht, dass [mm] $\kappa_3\ge 4*3*3^2*2=216$ [/mm] gilt. Vermutlich (aber völlig unbewiesenermaßen) gilt sogar Gleichheit (was karmas Wert bestätigen würde). Die Überlegungen sind so frickelich, dass ich mir nicht die Mühe machen möchte, sie aufzuschreiben. Sie sind ohnehin nur für $n=3$ anwendbar.
> Okay, aber die Existenz eines Dominopfades kann man in
> diesem speziellen Fall auch per Hand zeigen, z.B. mit
> Induktion über [mm]n[/mm]:
> Der Induktionsanfang ist klar, Nun betrachte [mm]D_{n+1}[/mm] und
> entferne alle Knoten, die irgendwo [mm]n[/mm] stehen haben (und die
> Kanten die da dran hängen natürlich auch) und bemerke
> dass der entstehende Teilgraph [mm]E\subset D_{n+1}[/mm] kanonisch
> isomorph zu [mm]D_n[/mm] ist, in dem aber nach I.V. ein Dominopfad
> existiert, also auch in [mm]E[/mm]. Nun überzeuge man sich, dass
> man diesen Dominopfad in [mm]E[/mm] zu einem in [mm]D_{n+1}[/mm] erweitern
> kann... fertig. (Vereinfacht gesagt: Nimm einfach alle
> Dominosteine mit der höchsten Zahl weg, lege aus den
> übrigen einen Dominopfad und dann bastel die weggenommenen
> Steine wieder ans Ende. Dass das klappt ist nicht ganz
> klar, sieht man aber schnell ein)
Super, dann ist das geklärt!
(Man erhält auf diese Weise sogar [mm] $\kappa_n*\vektor{n+1\\n}*n!=\kappa_n*(n+1)!$ [/mm] verschiedene Dominopfade in [mm] $D_{n+1}$ ($\kappa_n*\vektor{n+1\\n}$: [/mm] Anzahl der Anfangsstücke dieser Dominopfade, $n!$: Anzahl der Endstücke zu jedem Anfangsstück). Ich konnte aber nicht [mm] $\kappa_n*(n+1)!\big|\kappa_{n+1}$ [/mm] zeigen.)
> > > 2) Es gibt eine wichtige Symmetrie in [mm]G_n[/mm], nämlich
> > > anschaulich indem ich einfach die Beschriftung der
> > > Dominosteine permutiere, oder expliziter:
> > > [mm]\operatorname{Aut}(G_n)[/mm] enthält zumindest schonmal die
> > > Abbildungen der Form [mm](a,b)\mapsto(\sigma(a),\sigma(b))[/mm] fuer
> > > festes [mm]\sigma\in\operatorname{Bij}(\IN_n)[/mm], also
> > > [mm]|Aut(G_n)|\ge|\operatorname{Bij}(\IN_n)|=n![/mm]
> > Man kann sich sogar überlegen, dass
> > [mm]\operatorname{Aut}(G_n)[/mm] nur aus diesen Abbildungen bestehen
> kann.
> Hmm... wie? Ich hätte irgendwie gar nicht erwartet, dass
> man die Automorphismengruppe einfach hinschreiben kann
Sei [mm] $\Sigma\in\operatorname{Aut}(G_n)$. [/mm] Dann induziert [mm] $\Sigma$ [/mm] eine Bijektion auf der Menge [mm] $\{(0,0),(1,1),\ldots,(n-1,n-1)\}$ [/mm] (z.B. da dies die Menge der Knoten mit genau $n-1$ ausgehenden Kanten ist und [mm] $\Sigma$ [/mm] als Isomorphismus insbesondere die Anzahlen der ausgehenden Kanten erhält). Diese Bijektion auf der Menge [mm] $\{(0,0),(1,1),\ldots,(n-1,n-1)\}$ [/mm] identifiziert sich kanonisch mit einem Element [mm] $\sigma\in\operatorname{Bij}(\{0,1,\ldots,n-1\})$.
[/mm]
Behauptung: Für alle [mm] $(a,b)\in V_n$ [/mm] gilt [mm] $\Sigma((a,b))=(\sigma(a),\sigma(b))$.
[/mm]
Für $a=b$ gilt dies nach Konstruktion von [mm] $\sigma$. [/mm] Sei nun [mm] $a\not=b$. [/mm] Sei [mm] $\Sigma((a,b))=(a',b')$. [/mm] Da es eine Kante von $(a,a)$ nach $(a,b)$ gibt, gibt es auch eine Kante von [mm] $\Sigma((a,a))$ [/mm] nach [mm] $\Sigma((a,b))$, [/mm] also von [mm] $(\sigma(a),\sigma(a))$ [/mm] nach $(a',b')$. Somit gilt [mm] $\sigma(a)=a'$. [/mm] Analog überlegt man sich [mm] $\sigma(b)=b'$ [/mm] (mittels der Kante von $(a,b)$ nach $(b,b)$).
> Das stimmt, ich denke das Problem ist aber, dass wir
> bisher noch nicht die richtigen Symmetrien betrachtet
> haben. Für uns relevant sind ja eigentlich die
> Abbildungen, die Dominopfade auf Dominopfade abbilden.
Sicherheitshalber: Ich verstehe das so, dass ALLE Dominopfade auf Dominopfade abgebildet werden.
> Diese Abbildungen müssen ja zwangsläufig bijektiv sein,
> und ich vermute mal, dass sie auch eine Untergruppe
> [mm]\operatorname{Sym}(D_n)[/mm] von [mm]\operatorname{Bij}(V_n)[/mm] bilden
Tun sie. (Für den schwierigen Teil, der Abgeschlossenheit unter Inversenbildung, beachte man, dass jedes Element von [mm] $\operatorname{Sym}(D_n)$ [/mm] eine Injektion und somit eine Bijektion auf der Menge der Dominopfade induziert.)
> Die eigentliche Idee war ja nun, dass
> [mm]|\operatorname{Sym}(D_n)|\ \big|\ \kappa_n[/mm], das müsste man
> aber auch erstmal genau zeigen.
Mein Vorschlag: Auf der Menge der Dominopfade erklären wir eine Äquivalenzrelation, deren Äquivalenzklassen alle jeweils genau [mm] $|\operatorname{Sym}(D_n)|$ [/mm] viele Elemente enthalten. Eine solche Äquivalenzrelation erhalten wir dadurch, dass wir zwei Dominopfade als äquivalent bezeichnen, wenn sie durch ein Element von [mm] $\operatorname{Sym}(D_n)$ [/mm] auseinander hervorgehen.
> Naja, ich denk hier könnte man noch ne ganze Weile
> knobeln.
Glaube ich auch. Und diese Frage kam von einem Schüler! Bin mal gespannt, ob wir noch eine Auflösung erhalten...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:39 Mi 17.03.2010 | | Autor: | pelzig |
> Sei [mm]\Sigma\in\operatorname{Aut}(G_n)[/mm]. Dann induziert
> [mm]\Sigma[/mm] eine Bijektion auf der Menge
> [mm]\{(0,0),(1,1),\ldots,(n-1,n-1)\}[/mm] (z.B. da dies die Menge
> der Knoten mit genau [mm]n-1[/mm] ausgehenden Kanten ist und [mm]\Sigma[/mm]
> als Isomorphismus insbesondere die Anzahlen der ausgehenden
> Kanten erhält). Diese Bijektion auf der Menge
> [mm]\{(0,0),(1,1),\ldots,(n-1,n-1)\}[/mm] identifiziert sich
> kanonisch mit einem Element
> [mm]\sigma\in\operatorname{Bij}(\{0,1,\ldots,n-1\})[/mm].
> Behauptung: Für alle [mm](a,b)\in V_n[/mm] gilt
> [mm]\Sigma((a,b))=(\sigma(a),\sigma(b))[/mm].
> Für [mm]a=b[/mm] gilt dies nach Konstruktion von [mm]\sigma[/mm]. Sei nun
> [mm]a\not=b[/mm]. Sei [mm]\Sigma((a,b))=(a',b')[/mm]. Da es eine Kante von
> [mm](a,a)[/mm] nach [mm](a,b)[/mm] gibt, gibt es auch eine Kante von
> [mm]\Sigma((a,a))[/mm] nach [mm]\Sigma((a,b))[/mm], also von
> [mm](\sigma(a),\sigma(a))[/mm] nach [mm](a',b')[/mm]. Somit gilt
> [mm]\sigma(a)=a'[/mm]. Analog überlegt man sich [mm]\sigma(b)=b'[/mm]
> (mittels der Kante von [mm](a,b)[/mm] nach [mm](b,b)[/mm]).
Muy bien.
> Sicherheitshalber: Ich verstehe das so, dass ALLE
> Dominopfade auf Dominopfade abgebildet werden.
Natürlich.
> > Diese Abbildungen müssen ja zwangsläufig bijektiv sein,
> > und ich vermute mal, dass sie auch eine Untergruppe
> > [mm]\operatorname{Sym}(D_n)[/mm] von [mm]\operatorname{Bij}(V_n)[/mm] bilden
> Tun sie. (Für den schwierigen Teil, der Abgeschlossenheit
> unter Inversenbildung, beachte man, dass jedes Element von
> [mm]\operatorname{Sym}(D_n)[/mm] eine Injektion und somit eine
> Bijektion auf der Menge der Dominopfade induziert.)
>
> > Die eigentliche Idee war ja nun, dass
> > [mm]|\operatorname{Sym}(D_n)|\ \big|\ \kappa_n[/mm], das müsste man
> > aber auch erstmal genau zeigen.
> Mein Vorschlag: Auf der Menge der Dominopfade erklären
> wir eine Äquivalenzrelation, deren Äquivalenzklassen alle
> jeweils genau [mm]|\operatorname{Sym}(D_n)|[/mm] viele Elemente
> enthalten. Eine solche Äquivalenzrelation erhalten wir
> dadurch, dass wir zwei Dominopfade als äquivalent
> bezeichnen, wenn sie durch ein Element von
> [mm]\operatorname{Sym}(D_n)[/mm] auseinander hervorgehen.
Ja, etwas netter aufgeschrieben: du betrachtest die Menge [mm] $\mathfrak{M}_n$ [/mm] der Dominopfade in [mm] $D_n$ [/mm] und lässt darauf [mm] $\operatorname{Sym}(D_n)$ [/mm] in naheliegender Weise wirken. Deine Äquivalenzklassen sind nun genau die Orbits dieser Gruppenwirkung. Man sieht jetzt sofort, dass alle Orbits gleiche Länge [mm] $|\operatorname{Sym}(D_n)|$ [/mm] haben und damit ist [mm] $|\operatorname{Sym}(D_n)|\ \big|\ |\mathfrak{M}_n| [/mm] = [mm] \kappa_n$ [/mm] gezeigt.
Der ganze abstract nonsense bringt uns leider einer expliziten Formel kein Stück weiter.
> > Naja, ich denk hier könnte man noch ne ganze Weile
> > knobeln.
> Glaube ich auch. Und diese Frage kam von einem Schüler!
> Bin mal gespannt, ob wir noch eine Auflösung erhalten...
Es ist auf jeden Fall ein schönes Problem. Es ist für mich persönlich auch grade sehr nett mal zu sehen, dass sich auch Probleme aus der "freien Wildbahn" in die Sprache und Strukturen, die ich so im Studium bisher gesehen habe, übersetzen lassen.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:08 Do 18.03.2010 | | Autor: | pelzig |
Nochmal ein kleines Update... wenn man schon mit Graphen hantiert, dann ist es wesentlich sinnvoller die Domoinosteine als Kanten aufzufassen, und die Zahlen als Knoten. Also betrachte den Graphen [mm] $D_n:=(\IN_n,\IN_n^2)$ [/mm] und Zähle die Anzahl [mm] $\kappa_n$ [/mm] der Eulerpfade (=Eulerkreise!) in [mm] $D_n$. [/mm] Jetzt ist auch wirklich offensichtlich, dass dieser Graph einfach nur jede denkbare Symmetrie aufweißt, d.h. [mm] $\operatorname{Aut}(D_n)=S_n$.
[/mm]
So nach einigem ziemlich frustrierenden, wenig fruchtbaren Rumgrübeleien kommt man immerhin schon auf [mm] $$\kappa_n=n!\cdot(n-1)^{n-1}\cdot n\cdot\gamma_n$$ [/mm] wobei [mm] $\gamma_n$ [/mm] eine gewisse natürliche Zahl ist (s.u.), über die ich sonst noch nicht sehr viel weiß, außer dass [mm] $\gamma_1=\gamma_2=1$, $\gamma_3=3$ [/mm] und dass die Folge der [mm] $\gamma_n$ [/mm] monoton wachsend ist. Insbesondere bestätigt das eure Rechnung für [mm]\kappa_3=3!\cdot 2^2\cdot 3\cdot 3=216[/mm]. Man sieht auch wie schnell diese Folge [mm] $\kappa_n$ [/mm] wächst, z.B. ist schon [mm] $\kappa_4\ge [/mm] 7776$, also keine Chance da irgendwas per Hand zu reißen.
Der Faktor [mm](n-1)^{n-1}\cdot n[/mm] entsteht durch die Überlegung, dass man die Steine der Form (a,a) eigentlich außer Acht lassen kann. In meinen letzten Überlegungen habe ich also nur noch den Graphen [mm] $$\mathcal{D}_n:=(\IN_n,\{(a,b)\in\IN_n^2\mid a\ne b\})$$ [/mm] betrachtet. Nun ist [mm] $\gamma_n$ [/mm] genau die Anzahl der Eulerpfade in [mm] $\mathcal{D}_n$, [/mm] die (o.B.d.A.) bei 1 beginnen, modulo Assoziiertheit, wobei zwei Eulerpfade assoziert heißen, wenn sie durch ein Permutation der Knoten mit Fixpunkt 1 (!) auseinander hervorgehen
Edit: Ahja nochwas, auch wenn das trivial ist, aber ich schlage vor solange man nicht noch was besseres hat solche Ketten als Pfade in [mm] $\mathcal{D}_n$ [/mm] zu notieren, z.B. wird aus (1,1),(1,2),(2,2),(2,1) zunächst (entfernen der Steine (a,a)) (1,2),(2,1) und dann nur noch 121 (Folge der Knoten, die besucht werden). Komplizierteres Beispiel: Die drei "Grundtypen" von Ketten im Falle $n=3$, also die Ketten, deren Anzahl [mm] $\gamma_3$ [/mm] misst, lauten 1213231, 1232131 und 1231321.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:06 Sa 20.03.2010 | | Autor: | tobit09 |
Danke für die interessanten Überlegungen!
> Nochmal ein kleines Update... wenn man schon mit Graphen
> hantiert, dann ist es wesentlich sinnvoller die
> Domoinosteine als Kanten aufzufassen, und die Zahlen als
> Knoten. Also betrachte den Graphen [mm]D_n:=(\IN_n,\IN_n^2)[/mm] und
> Zähle die Anzahl [mm]\kappa_n[/mm] der Eulerpfade (=Eulerkreise!)
> in [mm]D_n[/mm].
Das sieht deutlich einfacher aus!
Gute Idee, die (a,a)-Dominosteine gesondert zu betrachten!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:12 So 21.03.2010 | | Autor: | Karl_Pech |
Hallo Tobias,
Der Ansatz mit den Hamiltonkreisen scheint auf alle Fälle in die richtige Richtung zu gehen. Seht euch mal ![[]](/images/popup.gif) dieses Dokument hier an (bei "Domino Arrangement"). Vielleicht sollte man in dieser Richtung weitersuchen.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:36 So 21.03.2010 | | Autor: | tobit09 |
Hallo Karl,
auch dir vielen Dank für deine Mühe!
Bisher habe ich keine Verbindung gefunden zwischen dem dort thematisierten Problem der Existenz einer Dominokette aus vorgegebenen Dominosteinen und unserem Problem der Anzahl der Dominoketten aus allen Dominosteinen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:08 Di 23.03.2010 | | Autor: | tobit09 |
Danke!
Das wäre eine weitere Idee, falls karmas Idee sich als falsch herausstellen würde.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:02 Sa 20.03.2010 | | Autor: | SEcki |
> hat irgendjemand eine Idee, wie man das Problem für
> beliebiges n lösen könnte?
Noch nicht voll ausgereift, aber mal ne weitere Idee die quasi Induktion ist: aus jeder Kette für n kan ich eine passende für n-1 machen, in dem ich alle Steine mit dem Vorkommen eines n entferne. Dh auf der anderen Seite, eine Kette entsteht, wenn ich eine Kett für n-1 nehme und Kettenteile mit n einfüge - wobei eine Kettenteil in Inneren eines der Teile [m](k_1,n)(n,k_2)(k_2,n)\ldtos(n,k_l)[/m] ist, am Anfang darf [m]k_1[/m] auch n sein, für das Ende darf [m]k_l8/m] auch n sein (und man muss den Rest anpassen). Vielleicht kann man damit arbeiten? Vielleicht kann man zeigen, dass für jede n-1 Kette es genau gleich viele Wege gibt, zu einer n Kette zu kommen (da wir volle Ketten der Länge [m](n-1)^2[/m] annehmen, denke ich sogar, dass dies immer gelten muss).
Vielleicht geht auch jemand hin, und löst das Problem mit einem Computer für die ersten x n? Vielleicht kann man dann etwas folgern? (Ich schreibe mal gleich eines)
EDIT: Ich habe ein kleines Programm geschrieben, Count.java (Lizens BSD, falls wer es benutzen möchte)
| 1: |
| | 2: | import java.util.LinkedList;
| | 3: |
| | 4: | public class Count {
| | 5: | int[][] arr;
| | 6: | long count = 0;
| | 7: | int dimension = 0;
| | 8: | LinkedList<String> out;
| | 9: |
| | 10: | public static void main(String[] args) {
| | 11: | int dimension = Integer.parseInt(args[0]);
| | 12: | Count count = new Count(dimension);
| | 13: | count.execute();
| | 14: | }
| | 15: |
| | 16: | Count(int dim) {
| | 17: | dimension = dim;
| | 18: | arr = new int[dimension][dimension];
| | 19: | for (int i = 0; i < dimension; i++)
| | 20: | for (int j = 0; j < dimension; j++)
| | 21: | arr[i][j] = 0;
| | 22: | out = new LinkedList<String>();
| | 23: | }
| | 24: |
| | 25: | public void execute() {
| | 26: | for (int i = 0; i < dimension; i++) {
| | 27: | for (int j = 0; j < dimension; j++) {
| | 28: | arr[i][j] = 1;
| | 29: | out.add("("+i+","+j+")");
| | 30: | recursion(j,2);
| | 31: | out.removeLast();
| | 32: | arr[i][j] = 0;
| | 33: | }
| | 34: | }
| | 35: | System.out.println("Wir haben "+count+" viele Lösungen für n="+dimension+"!");
| | 36: |
| | 37: | }
| | 38: |
| | 39: | private void recursion(int lastnum, int deepness) {
| | 40: | for (int i = 0; i < dimension; i++) {
| | 41: | if (arr[lastnum][i] != 0) {
| | 42: | continue;
| | 43: | }
| | 44: | if (deepness == (dimension * dimension)) {
| | 45: | count++;
| | 46: | arr[lastnum][i] = deepness;
| | 47: | out.add("("+lastnum+","+i+")");
| | 48: | //if ( (count % 1000000) == 0) {
| | 49: | // System.out.println("\tZwischenstand: "+count);
| | 50: | print();
| | 51: | //}
| | 52: | out.removeLast();
| | 53: | arr[lastnum][i] = 0;
| | 54: | } else {
| | 55: | arr[lastnum][i] = deepness;
| | 56: | out.add("("+lastnum+","+i+")");
| | 57: | recursion(i, deepness + 1);
| | 58: | out.removeLast();
| | 59: | arr[lastnum][i] = 0;
| | 60: | }
| | 61: | }
| | 62: | }
| | 63: |
| | 64: | private void print() {
| | 65: | System.out.println("\t");
| | 66: | for (String s : out) {
| | 67: | System.out.print(s);
| | 68: | }
| | 69: | System.out.println("");
| | 70: | }
| | 71: |
| | 72: | }
|
Für die ersten 3n ergibt dies:
Wir haben 0 viele Lösungen für n=1!
Wir haben 4 viele Lösungen für n=2!
Wir haben 216 viele Lösungen für n=3!
Für n=4 läuft es schon ewig ...
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:52 Sa 20.03.2010 | | Autor: | tobit09 |
Hallo SEcki,
danke auch für deinen Beitrag!
> Noch nicht voll ausgereift, aber mal ne weitere Idee die
> quasi Induktion ist: aus jeder Kette für n kan ich eine
> passende für n-1 machen, in dem ich alle Steine mit dem
> Vorkommen eines n entferne.
Warum sollten die übrigen Steine hintereinanderpassen?
> Dh auf der anderen Seite, eine
> Kette entsteht, wenn ich eine Kett für n-1 nehme und
> Kettenteile mit n einfüge - wobei eine Kettenteil in
> Inneren eines der Teile [m](k_1,n)(n,k_2)(k_2,n)\ldtos(n,k_l)[/m]
> ist, am Anfang darf [m]k_1[/m] auch n sein, für das Ende darf
> [m]k_l8/m] auch n sein (und man muss den Rest anpassen). Vielleicht kann man damit arbeiten?
Vermutlich sind damit nicht alle Ketten abgedeckt. Aber vielleicht kann man so zu neuen unteren Schranken gelangen.
> Vielleicht kann man zeigen, dass für jede n-1 Kette es genau gleich viele Wege gibt,
> zu einer n Kette zu kommen (da wir volle Ketten der Länge [m](n-1)^2[/m] annehmen,
> denke ich sogar, dass dies immer gelten muss).
Ich glaube, dass dies gilt.
> EDIT: Ich habe ein kleines Programm geschrieben, Count.java (Lizens BSD, falls wer es benutzen möchte)
> Für die ersten 3n ergibt dies:> [i][i] Wir haben 0 viele Lösungen für n=1!
Für n=1 müsste eigentlich 1 herauskommen. (Ich habe den Quelltext nicht durchgeguckt.)
> Wir haben 4 viele Lösungen für n=2!> Wir haben 216 viele Lösungen für n=3!
Das passt zu den bisherigen Ergebnissen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:57 Sa 20.03.2010 | | Autor: | pelzig |
> > hat irgendjemand eine Idee, wie man das Problem für
> > beliebiges n lösen könnte?
>
> Noch nicht voll ausgereift, aber mal ne weitere Idee die
> quasi Induktion ist: aus jeder Kette für n kan ich eine
> passende für n-1 machen, in dem ich alle Steine mit dem
> Vorkommen eines n entferne. Dh auf der anderen Seite, eine
> Kette entsteht, wenn ich eine Kett für n-1 nehme und
> Kettenteile mit n einfüge - wobei eine Kettenteil in
> Inneren eines der Teile [m](k_1,n)(n,k_2)(k_2,n)\ldtos(n,k_l)[/m]
> ist, am Anfang darf [m]k_1[/m] auch n sein, für das Ende darf
> [m]k_l8/m] auch n sein (und man muss den Rest anpassen). Vielleicht kann man damit arbeiten? Vielleicht kann man zeigen, dass für jede n-1 Kette es genau gleich viele Wege gibt, zu einer n Kette zu kommen (da wir volle Ketten der Länge [m](n-1)^2[/m] annehmen, denke ich sogar, dass dies immer gelten muss).
Ja ich habe auch schon eine gewisse Zeit darüber nachgedacht, inwieweit $n$-Ketten auch $n-1$-Ketten enthalten usw. Ich denke auch, dass das der Schlüssel zu einer expliziten Formel für [mm] $\kappa_n$ [/mm] ist. Habe nur leider noch nicht den richtigen Geistesblitz gehabt.
> Vielleicht geht auch jemand hin, und löst das Problem mit einem Computer für die ersten x n? Vielleicht kann man dann etwas folgern? (Ich schreibe mal gleich eines)
> EDIT: Ich habe ein kleines Programm geschrieben, Count.java (Lizens BSD, falls wer es benutzen möchte)
> Für die ersten 3n ergibt dies:
> Wir haben 0 viele Lösungen für n=1!
> Wir haben 4 viele Lösungen für n=2!
> Wir haben 216 viele Lösungen für n=3!
> Für n=4 läuft es schon ewig ...
Hey, danke für die Mühe. Ist ja schonmal gut zu wissen dass der Fall $n=3$ dann wahrscheinlich wirklich stimmt. Ich habe mir dein Programm nicht genauer angeschaut, aber vielleicht kannst du es beschleunigen wenn du nur die Anzahl der Ketten berechnest die mit einer festen Zahl beginnen (z.B. mit 1) und dann mit n multiplizierst (das ist jetzt nur ein "educated guess", schliesslich sind ja alle Zahlen gleichberechtigt). Ferner kannst du auch die Steine der Form (a,a) rauswerfen, damit solltest du meinen Überlegungungen zufolge die Menge der Ketten (und damit die Rechenzeit?!) bei $n=4$ insgesamt schon auf $1/432$ reduzieren.
Würde mich sehr interessieren was da rauskommt.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:39 Mi 17.03.2010 | | Autor: | ghost2006 |
Vielen Dank für die hilfreichen Ansätze.
Ich selbst komme bei n=3 auf [mm] 3*2*3*3^2 [/mm] = 162 Möglichkeiten. Faktor 4 bleibt mir unklar.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:49 Mi 17.03.2010 | | Autor: | tobit09 |
Bisher hat anscheinend niemand von uns einen Ansatz für $n=3$ gefunden, den man mal eben schnell komplett ausführen könnte.
> Ich selbst komme bei n=3 auf [mm]3*2*3*3^2[/mm] = 162
> Möglichkeiten.
Kann man deine Vorgehensweise irgendwie ohne zu großen Aufwand erklären oder andeuten?
> Faktor 4 bleibt mir unklar.
Der kam bei mir zustande als Anzahl der Möglichkeiten im Fall $n=2$. Aber ohne komplette Schilderung meiner Überlegungen ist das natürlich nicht nachvollziehbar. Und diese Schilderung wäre halt sehr aufwendig...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:58 So 21.03.2010 | | Autor: | karma |
Hallo und guten Morgen,
Vertauschen wir in "n*n!" (nacktes) n und n!: "n!*n"
und machen aus dem "*" ein "^": "n!^n",
zur Sicherheit ein Klammerpaar: $( n! [mm] )^{n}$.
[/mm]
Fertig.
Es finden sich in einer wohlgeformten Kette der Länge [mm] $n^{2}$ [/mm] bestehend aus $n*n$ Spielsteinen $n!$ komplexe Anordnungsmuster, die $n-mal$ variiert werden.
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:35 So 21.03.2010 | | Autor: | SEcki |
> Vertauschen wir in "n*n!" (nacktes) n und n!: "n!*n"
> und machen aus dem "*" ein "^": "n!^n",
> zur Sicherheit ein Klammerpaar: [mm]( n! )^{n}[/mm].
Dies stimmt mit meinen berechneten Ergebnissen überein.
> Es finden sich in einer wohlgeformten Kette der Länge
> [mm]n^{2}[/mm] bestehend aus [mm]n*n[/mm] Spielsteinen [mm]n![/mm] komplexe
> Anordnungsmuster, die [mm]n-mal[/mm] variiert werden.
Das verstehe ich nicht - was meinst du mit Muster? Was meinst du mit variiert? Warum sind das dann alle? Kannst du das ausführen?
SEcki
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:56 Mo 22.03.2010 | | Autor: | karma |
Hallo und guten Tag,
wenn man den letzten halben Dominostein abschneidet und vorne an die Kette ansetzt,
ensteht eine neue Kette,
die aus einfachen Mustern aufgebaut ist.
Bei $n=2$ wären das die einfachen Muster $00$ und $11$,
bei $n=3$: $00$, $11$ und $22$.
Und so weiter.
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:22 Di 23.03.2010 | | Autor: | tobit09 |
Hallo Karsten,
> wenn man den letzten halben Dominostein abschneidet und
> vorne an die Kette ansetzt,
> ensteht eine neue Kette,
> die aus einfachen Mustern aufgebaut ist.
Soweit kann ich folgen.
Mir ist allerdings noch völlig unklar, wie man die Zahl der so erhaltenen Ketten aus einfachen Mustern einfacher bestimmen kann als die ursprünglich gesuchte Zahl der Dominoketten.
Vielleicht würde es helfen, wenn du ausführen könntest, was du in der vorherigen Antwort mit "komplexen Anordnungsmustern" und "n-maligem Variieren" meintest.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:02 Mi 24.03.2010 | | Autor: | karma |
Hallo und guten Morgen,
durch das Umformen sieht man die Muster besser,
nachfolgend für n=3 ( die einfachen Muster '00' als 'O' veschlüsselt,
'11' als '#', '22' als '*'):
O O # O * # # * *
O O # O * * # # *
O O # # O * # * *
O O # # O * * # *
O O # # * O * * #
O O # # * # O * *
O O # # * * O * #
O O # # * * # O *
O O # * O * * # #
O O # * # # O * *
O O # * * O * # #
O O # * * # # O *
O O * O # # * * #
O O * O # * * # #
O O * # O # # * *
O O * # # O # * *
O O * # # * * O #
O O * # * * O # #
O O * * O # # * #
O O * * O # * # #
O O * * # O # # *
O O * * # # O # *
O O * * # # * O #
O O * * # * O # #
O # O O * # # * *
O # O O * * # # *
O # O * # # * * O
O # O * * # # * O
O # # O O * # * *
O # # O O * * # *
O # # O * # * * O
O # # O * * # * O
O # # * O O * * #
O # # * O * * # O
O # # * # O O * *
O # # * # O * * O
O # # * * O O * #
O # # * * O * # O
O # # * * # O O *
O # # * * # O * O
O # * O O * * # #
O # * O * * # # O
O # * # # O O * *
O # * # # O * * O
O # * * O O * # #
O # * * O * # # O
O # * * # # O O *
O # * * # # O * O
O * O O # # * * #
O * O O # * * # #
O * O # # * * # O
O * O # * * # # O
O * # O O # # * *
O * # O # # * * O
O * # # O O # * *
O * # # O # * * O
O * # # * * O O #
O * # # * * O # O
O * # * * O O # #
O * # * * O # # O
O * * O O # # * #
O * * O O # * # #
O * * O # # * # O
O * * O # * # # O
O * * # O O # # *
O * * # O # # * O
O * * # # O O # *
O * * # # O # * O
O * * # # * O O #
O * * # # * O # O
O * * # * O O # #
O * * # * O # # O
# O O # # * O * *
# O O # # * * O *
# O O # * O * * #
# O O # * * O * #
# O O * O # # * *
# O O * O # * * #
# O O * # # * * O
# O O * # * * O #
# O O * * O # # *
# O O * * O # * #
# O O * * # # * O
# O O * * # * O #
# O # # * O O * *
# O # # * * O O *
# O # * O O * * #
# O # * * O O * #
# O * O O # # * *
# O * O O # * * #
# O * # # * * O O
# O * # * * O O #
# O * * O O # # *
# O * * O O # * #
# O * * # # * O O
# O * * # * O O #
# # O O # * O * *
# # O O # * * O *
# # O O * O # * *
# # O O * # * * O
# # O O * * O # *
# # O O * * # * O
# # O # * O O * *
# # O # * * O O *
# # O * O O # * *
# # O * # * * O O
# # O * * O O # *
# # O * * # * O O
# # * O O # O * *
# # * O O * * # O
# # * O # O O * *
# # * O * * # O O
# # * # O O * * O
# # * # O * * O O
# # * * O O # O *
# # * * O O * # O
# # * * O # O O *
# # * * O * # O O
# # * * # O O * O
# # * * # O * O O
# * O O # O * * #
# * O O # # O * *
# * O O * * # O #
# * O O * * # # O
# * O # O O * * #
# * O # # O O * *
# * O * * # O O #
# * O * * # # O O
# * # O O * * O #
# * # O * * O O #
# * # # O O * * O
# * # # O * * O O
# * * O O # O * #
# * * O O # # O *
# * * O O * # O #
# * * O O * # # O
# * * O # O O * #
# * * O # # O O *
# * * O * # O O #
# * * O * # # O O
# * * # O O * O #
# * * # O * O O #
# * * # # O O * O
# * * # # O * O O
* O O # O * # # *
* O O # O * * # #
* O O # # O * # *
* O O # # O * * #
* O O # # * # O *
* O O # # * * # O
* O O # * # # O *
* O O # * * # # O
* O O * # O # # *
* O O * # # O # *
* O O * * # O # #
* O O * * # # O #
* O # O O * # # *
* O # O O * * # #
* O # # O O * # *
* O # # O O * * #
* O # # * # O O *
* O # # * * # O O
* O # * # # O O *
* O # * * # # O O
* O * # O O # # *
* O * # # O O # *
* O * * # O O # #
* O * * # # O O #
* # O O # # * O *
* # O O # # * * O
* # O O * O # # *
* # O O * * O # #
* # O # # * O O *
* # O # # * * O O
* # O * O O # # *
* # O * * O O # #
* # # O O # * O *
* # # O O # * * O
* # # O O * O # *
* # # O O * * O #
* # # O # * O O *
* # # O # * * O O
* # # O * O O # *
* # # O * * O O #
* # # * O O # O *
* # # * O # O O *
* # # * * O O # O
* # # * * O # O O
* # * O O # # O *
* # * O # # O O *
* # * * O O # # O
* # * * O # # O O
* * O O # O * # #
* * O O # # O * #
* * O O # # * # O
* * O O # * # # O
* * O O * # O # #
* * O O * # # O #
* * O # O O * # #
* * O # # O O * #
* * O # # * # O O
* * O # * # # O O
* * O * # O O # #
* * O * # # O O #
* * # O O # # * O
* * # O O * O # #
* * # O # # * O O
* * # O * O O # #
* * # # O O # * O
* * # # O O * O #
* * # # O # * O O
* * # # O * O O #
* * # # * O O # O
* * # # * O # O O
* * # * O O # # O
* * # * O # # O O
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:19 Mi 24.03.2010 | | Autor: | pelzig |
Hallo Karma,
Ich muss das jetzt einfach mal loswerden, aber es ist echt superanstrengend dir jede kleine Begründung aus der Nase ziehen zu müssen. Deinem mathematischen Background nach zur urteilen müsstest du sehr genau wissen, was ein mathematisches Argument ist. Und ja, es ist bemerkenswert dass eine so einfache Formel wie [mm] $(n!)^n$ [/mm] zumindest für die ersten 3 Fälle mit der gesuchten Folge übereinstimmt und ich denke irgendwie würden die Leute hier (mich eingeschlossen) gern dran glauben, dass es auch allgemein stimmt.
Aber: objektiv betrachtet hast du in meinen Augen bisher kein einziges stichhaltiges Argument geliefert, von einer konkreten Beweis(idee) mal ganz zu schweigen. Stattdessen erzählst du uns was von "komplexen Anordnungsmustern" und "varriieren" und auf die berechtigte Nachfrage hin, was genau das eigentlich sein soll, erzählst du einfach irgendwas komplett Neues von "einfachen Mustern".
Nebenbei bemerkt: Diese Sache mit den "einfachen Mustern" (also dass du einen halben Stein abschneidest usw.)ist wenn man mal kurz überlegt nur eine ziemlich seltsame, aber äquivalente Art, die Dominoketten als Wege im Graphen [mm] $(\IN_n,\IN_n^2)$ [/mm] aufzufassen.
Jetzt fragt Tobias sogar nochmals, was du mit diesen ominösen Begriffen aus dem Post davor eigentlich meinst, und deine Antwort besteht darin, dass du alle (?) Dominoketten für den Fall $n=3$ hinschreibst. Also ehrlich, warum hast du das gemacht?! Ich mein... das macht ja auch Arbeit und alles, aber wer soll denn daraus schlau werden, was hat das überhaupt mit Tobias Frage zu tun?!?! Vielleicht überseh ich ja was, aber ich werde daraus absolut überhaupt nicht schlau.
Also ich habe nämlich eher das Gefühl, dass du wahrscheinlich genauso wie der Rest hier ziemlich im Nebel rumstocherst, was ja an sich nix dramatisches ist und es ist auch nicht verboten die richtigen Formeln vielleicht zu erraten (deine letzte Formel konnte ich ja noch irgendwie widerlegen, aber hier bin ich auch raus), aber das Problem ist einfach, dass ich langsam überhaupt keine Lust mehr habe darüber nachzudenken was du schreibst, weil ich das Gefühl habe ich verschwende meine Zeit weil da eh nix dahinter steckt, und das war ganz sicher nicht dein Anliegen. Aber ich würde mich sehr freuen wenn du mich eines Besseren belehren könntest.
Viele Grüße,
Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:46 Mi 24.03.2010 | | Autor: | SEcki |
> Ich muss das jetzt einfach mal loswerden, aber es ist echt
> superanstrengend dir jede kleine Begründung aus der Nase
> ziehen zu müssen. Deinem mathematischen Background nach
> zur urteilen müsstest du sehr genau wissen, was ein
> mathematisches Argument ist. Und ja, es ist bemerkenswert
> dass eine so einfache Formel wie [mm](n!)^n[/mm] zumindest für die
> ersten 3 Fälle mit der gesuchten Folge übereinstimmt und
Es stimmt bis n=6, btw.
> ich denke irgendwie würden die Leute hier (mich
> eingeschlossen) gern dran glauben, dass es auch allgemein
> stimmt.
Ja, ich auch.
Ansonsten schließe ich mich Robert an - begründe es doch bitte genauer, was du meinst.
SEcki
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:26 Mi 24.03.2010 | | Autor: | karma |
| Aufgabe | | a) Wieviele mögliche Ketten gibt es für n=3? Geben Sie ggf. eine Beziehung zur Berechnung der Möglichkeiten an! |
Hallo und guten Tag,
[mm] $\(n!\)^{n}$ [/mm] stimmt bis n=6, Donnerwetter.
Einen Beweis, daß es füer alle n gilt, kenne ich nicht.
Mir fiel auf,
daß es bei einer Kettenlänge von [mm] $n\* [/mm] n$ Dominsteinen,
n-Teilketten der Länge n gibt.
Angenommen, die Teilketten wären unabhangig,
dann könnte man z.B. hinter Teilkette 1 jede andere der (wie ich vermute) $n!$ Musterketten hängen.
Und so weiter.
Ein einfaches Muster möchte ich Ziffernpaare gleicher Ziffern nennen,
wie z.B. "00", "11" etc.
Ein Beispiel für ein komplexes Muster wäre:
"das erste und das letzte einfache Muster der Teilkette stimmen überein".
Wenn man keinen Beweis der Vermutung [mm] $\(n!\)^n$ [/mm] kennt,
wie wäre es mit einem Gegenbeispiel?
Vielleicht z.B. sind die Teilketten gar nicht unabhängig.
Oder aber,
[mm] $(n!)^n$ [/mm] stimmt,
aber die Begründung nicht.
Schönen Gruß
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Fr 26.03.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
