Orbit-Counting theorem < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei $G$ eine endliche Gruppe, die auf einer endlichen Menge $M$ operiere. Ferner sei mit $M/G$ die Menge der Bahnen von $M$ unter $G$ bezeichnet und für [mm] $g\in [/mm] G$
[mm] $\text{Fix}_M(g):=\left\{x\in M : gx=x\right\}
[/mm]
In einem ersten Aufgabenteil ist das ![[]](/images/popup.gif) Orbit-Counting Theorem zu beweisen.
Betrachte nun eine Halskette auf die in drei Farben je drei Perlen aufgezogen werden sollen. Die Perlen derselben Farbe seien nicht unterscheidbar. Je zwei Anordnungen dieser Perlen werden als gleich betrachtet, wenn sie durch Drehungen/Spiegelungen ineinander überführt werden können.
Bestimmen Sie die Anzahl der verschiedenen Anordnungen. Betrachten Sie dazu eine Menge mit [mm] $\frac{9!}{3!3!3!}$ [/mm] Elementen, die die verschiedenen Anordnungen enthalten und operieren Sie mit einer geeigneten Gruppe $G$ auf dieser Menge, um die Spiegelungen/Drehungen zu modellieren. |
Das Orbit-Counting Theorem habe ich bewiesen. Ich finde für den zweiten Teil der Aufgabe aber überhaupt keinen Ansatz.
Wenn mir jemand einen Anstoß geben könnte, wäre das echt super.
Liebe Grüße
Toasten
|
|
| |
|
Hi Differential,
der naheliegende Ansatz ist ja, den Orbit-Satz von Burnside dann auch zu verwenden. Insofern sehe ich nicht genau, wie das Problem aussieht. Gegeben ist eine Menge $M$ von Anordnungen
[mm] $\red{\bullet_1}\blue{\bullet_1}\blue{\bullet_2}\green{\bullet_1}\red{\bullet_2}\green{\bullet_2}\red{\bullet_3}\blue{\bullet_3}\green{\bullet_3}$.
[/mm]
Zwei solche nennen wir äquivalent, wenn nur die Indizes von gleichfarbigen Kugeln übereinstimmen, dadurch ist eine Äquivalenzrelation gegeben und der Quotient nach dieser Relation hat noch $9!/3!^3$ Elemente, auf welche jetzt die Gruppe operiert.
Wie ich die Aufgabenstellung verstehe, sind Drehung/Spiegelung synonym zu verstehen. Ich verstehe es so, dass [mm] $G=\{\operatorname{id},\sigma\}$, [/mm] wobei [mm] $\sigma^2=\operatorname{id}$, [/mm] und dass [mm] $\sigma(\red{\bullet_1}\blue{\bullet_1}\blue{\bullet_2}\green{\bullet_1}\red{\bullet_2}\green{\bullet_2}\red{\bullet_3}\blue{\bullet_3}\green{\bullet_3})=\green{\bullet_3}\blue{\bullet_3}\red{\bullet_3}\green{\bullet_2}\red{\bullet_2}\green{\bullet_1}\blue{\bullet_2}\blue{\bullet_1}\red{\bullet_1}$. [/mm] Eigentlich wäre hier noch zu zeigen, dass die Relation $G$-invariant ist, das heißt, dass äquivalente Anordnungen auch nach der Wirkung eines Elementes noch äquivalent sind, aber das kann man auch glauben. Dann haben wir jedenfalls eine Operation auf den Quotienten nach der Farben-Relation.
Wenn jetzt auch durch Drehung ineinander überführbare Anordnungen als äquivalent angesehen werden, sind die Äquivalenzklassen genau die Orbites und deren Anzahl ist gesucht. Diese liefert ja genau Burnside, also suchen wir, um [mm] $|M/G|=\dfrac{1}{|G|}\sum_g|\operatorname{Fix}(g)|$ [/mm] verwenden zu können im Wesentlichen nur die Kardinalität von [mm] $\operatorname{Fix}(\sigma)$.
[/mm]
Jetzt bist du dran 
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:35 Fr 10.01.2014 | | Autor: | Differential |
Hallo,
und vielen Dank für die Mühe die du dir gemacht hast!
So ganz verstanden habe ich es aber leider trotzdem nicht. Ich würde es gerne nochmal in eigenen Worten versuchen zu formulieren:
Es gibt $9!$ verschiedene Anordnungen von $9$ Perlen. Wir betrachten eine Äquivalenzrelation [mm] $\sim$ [/mm] auf der Menge $M$ aller Anordnungen derart, dass zwei Anordnungen als äquivalent zu verstehen sind, wenn sich diese nur innerhalb gleichfarbiger Perlen unterscheiden. Der Quotient bzgl. dieser Äquivalenzrelation hat folglich $9!/3!^3$ Elemente und sei mit [mm] $M/\sim$ [/mm] bezeichnet.
Sei nun [mm] $G=\left\{ \text{id} ,\sigma \right\}$ [/mm] derart, dass [mm] $\sigma^2=\text{id}$. [/mm] Ferner operiere $G$ auf [mm] $M/\sim$ [/mm] durch Drehung oder Spiegelung der Anordnungen in [mm] $M/\sim$ [/mm] derart, dass zwei Anordnungen, die durch Wirkung der Operation ineinander überführt werden können, in der selben Bahn liegen.
Dann ist die Anzahl der möglichen Perlenanordnungen gegeben durch:
[mm] $|(M/\sim)&G|=\frac{1}{|G|}\left(\text{Fix}_{M/\sim}\text{id}+\text{Fix}_{M/\sim}\sigma\right)=\frac{1}{2}\left(\frac{9!}{3!^2}+?\right)$
[/mm]
Passt das so ungefähr? Wie wirkt [mm] $\sigma$ [/mm] den auf eine Anordnung aus [mm] $M/\sim$? [/mm] So wie du es dargestellt hast, wurde ja nur die Reihenfolge invertiert. Mit Spiegelung oder Drehung kann aber denke ich noch einiges mehr erreicht werden, oder?
Gruß
Differential
|
|
|
| |
|
Hi,
Ja, genauso habe ich das alles gemeint. Dass die Gruppe oder die Operation, die ich vorgeschlagen habe, noch nicht stimmen, ist schon möglich. Die Reihenfolge umzukehren war das einzige, was mir zur "Drehung/Spiegelungen einer Perlenkette" eingefallen ist. Was stellst du dir denn darunter vor?
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 12:41 Sa 11.01.2014 | | Autor: | Differential |
Hallo,
ich stelle mir so etwas vor, was man unter einem Circular shift versteht. Dies würde ich als Drehung auffassen. Eine Spiegelung könnte man wie folgt verstehen: Fixiere ein Element, vertausche seine linke und rechte Seite und invertiere dann die Reihenfolge beider Seiten. In unserem Fall ist dies aber in der Rat identisch damit, dass man einfach die Reihenfolge der Anordnung invertiert.
Ich würde also die Permutationen
[mm] $\text{id}, \sigma_1(i)\equiv [/mm] (i+1) [mm] \text{ mod } [/mm] 9, [mm] \sigma_2(i)\equiv [/mm] (i-1) [mm] \text{ mod } [/mm] 9, [mm] \sigma_3(i)\equiv \overline{i}$
[/mm]
vorschlagen. Mehr sollte allerdings nach obigen Überlegungen mit einer Spiegelung oder einer Drehung nicht möglich sein.
Was meinst du dazu? Ist nicht so meine Aufgabe. Wie würde ich nun [mm] $\text{Fix}_{M/\sim}\sigma_i$, [/mm] für die einzelnen [mm] $\sigma_i$ [/mm] bestimmen?
Gruß
Differential
|
|
|
| |
|
So könnte man das auch verstehen. Allerdings werden die nötigen Rechnungen dadurch vermutlich schon sehr aufwendig. Das, was du Circular Shift nennst, entspricht ja dem Zykel [mm] $(123\dots 9)\in S_9$. [/mm] Nun ist es so, dass es in der [mm] $S_n$ [/mm] häufig schon genügt, neben [mm] $(123\dots [/mm] n)$ noch eine weitere Permutation zu haben, um ganz [mm] $S_n$ [/mm] zu erzeugen - beispielsweise gilt [mm] $\langle(123\dots n),(12)\rangle=S_n$. [/mm] Es wäre also gut möglich, dass wir für $9!$ verschiedene Permutationen [mm] $\pi$ [/mm] die Summe aller [mm] $|\operatorname{Fix}\pi|$ [/mm] berechnen müssten - das scheint mir selbst für gute Kopfrechner schwierig. Selbst, wenn die erzeugte Gruppe kleiner sein sollte, ist es m.E. nicht einfach, zu bestimmen, wie diese aussieht, oder auch nur welche Ordnung sie hat. Das Problem würde also sehr komplex, wenn ich nichts wichtiges übersehe.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
Hm, was schlägst du also vor? Warst du nicht ursprünglich der Ansicht, die Aufgabe sei ganz einfach ;) Oder habe ich das falsch interpretiert?
Ich mag solche Aufgaben grundsätzlich ja nicht so gerne, weil mir die Beschreibung zu schwammig ist und m.E. nach zu viel Spielraum lässt.
Wenn ich genau überlege könnte man das Rückwärtsdrehen auch durch eine Folge von Invertieren und Vorwärtsdrehen ersetzen. Weniger scheint mir nicht zu genügen. Wir hätten also
[mm] $G=\left\{\text{id}, (123456789), \begin{pmatrix} 1&2&3&4&5&6&7&8&9\\9&8&7&6&5&4&3&2&1 \end{pmatrix} \right\}$
[/mm]
Jetzt betrachten wir mal die Elemente von $M$, die durch die einzelnen Permutationen festgelassen werden:
(1) [mm] $\sigma=\text{id}\in G\Rightarrow \text{Fix}_{M/\sim}\sigma [/mm] = [mm] |M/\sim|=\frac{9!}{3!^3}$
[/mm]
(2) [mm] $\sigma=(123456789)\in G\Rightarrow \text{Fix}_{M/\sim}\sigma [/mm] = ?$
(3) [mm] $\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9\\9&8&7&6&5&4&3&2&1 \end{pmatrix}\in G\Rightarrow \text{Fix}_{M/\sim}\sigma [/mm] = ?$
Tja, bei (2), (3) habe ich einfach keine Ahnung, welche Anordnungen das sein sollen. Meiner Meinung nach, lassen die beiden Permutationen gar keine Anordnung fest.
Aber bevor ich mich wieder verzettele: Die Idee hinter dem was hier getan werden soll ist doch, dass wir alle Anordnungen die durch eine Folge von Permutationen aus $G$ ineinander überführt werden können, als gleich angesehen werden sollen. Wie spiegelt sich das jetzt in diem "Orbit-Counting Theorem" wieder?
Ich hoffe du hast noch eine Idee. So langsam verzweifle ich ein wenig an der Aufgabe.
Gruß
Differential
|
|
|
| |
|
Hey,
naja, wenn man Drehung/Spiegelung so interpretiert, wie ich es zunächst getan habe, ist es hinzukriegen. Ich kann dich gut verstehen, die schlimmsten Aufgaben sind die, wo man nicht weiß, wie die Aufgabenstellung gemeint ist. Das Problem ist hierbei, wie du es jetzt vorschlägst, dass $G$ keine Gruppe ist! Denn sonst müsste zum Beispiel auch [mm] $(123\dots 9)^2=(135792468)$ [/mm] und noch sehr sehr viele weitere Permutationen in $G$ liegen. Das ist das Problem, das ich in meiner Mitteilung meinte.
Liebe Grüße
UniversellesObjekt
|
|
|
| |
|
Du hast natürlich recht. Jetzt habe ich die Gruppenstruktur total aus den Augen verloren gehabt. Wenn wir aber einfach die Permutation $(198765432)$ zu $G$ hinzufügen, also
[mm] $G:=\left\{\text{id}, (123456789), (198765432), \begin{pmatrix} 1&2&3&4&5&6&7&8&9\\9&8&7&6&5&4&3&2&1 \end{pmatrix}\right\}$
[/mm]
dann müsste das aus meiner Sicht durchaus eine Gruppe sein. Zu jedem Element existiert ein Inverses in $G$, es gibt ein neutrales Element und Assoziativ sollte die Verknüpfung auch sein. Oder was benkde ich nicht?
Für den Fall, dass wir so nicht weiterkommen, würde ich gerne auf deine Interpretation zurückkommen. Doch warum denkst du, dass durch
[mm] $\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9\\9&8&7&6&5&4&3&2&1 \end{pmatrix}$
[/mm]
eine beliebige Drehung/Spiegelung modelliert ist?
Außerdem: Wie würde ich dann [mm] $\text{Fix}_{M/\sim}(\sigma)$ [/mm] bestimmen? Welche Anordnungen aus [mm] $M/\sim$ [/mm] werden von [mm] $\sigma$ [/mm] festgelassen?
Gruß
Differential
|
|
|
| |
|
Hi,
eine Gruppe haben wir immer noch nicht; siehe meine letzte Antwort. $(123456789)(123456789)=(135792468)$ liegt nicht in $G$.
> Für den Fall, dass wir so nicht weiterkommen, würde ich
> gerne auf deine Interpretation zurückkommen. Doch warum
> denkst du, dass durch
> [mm]\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9\\9&8&7&6&5&4&3&2&1 \end{pmatrix}[/mm]
>
> eine beliebige Drehung/Spiegelung modelliert ist?
weil mir nicht klar ist, was ich mir unter der Drehung/Spiegelung einer Kette vorzustellen habe. Das hier ist eine Spiegelung in der Hinsicht, dass ich an einer Achse, welche durch die mittlere Perle läuft, spiegele. Dasselbe Ergebnis erhalte ich, wenn ich die Kette um 180° drehe. Aber wie sonst kann ich den eine Kette drehen und so die Reihenfolge der Perlen verändern (auf diese kommt es ja an)? Das hier ist alles, was meiner Meinung nach den Namen Drehung/Spiegelung verdient.
Die Fixpunkte von [mm] $\sigma$ [/mm] sind einfach zu bestimmen. Versuche einfach mal, einen zu konstruieren, ich denke, dass du schnell dahinter kommst. Sich das dann formal zu überlegen, ist dann auch machbar.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
Ja, in Ordnung. Es muss gelten, dass das $i$-te Element der Anordnung die gleiche Farbe hat, wie das $(10-i)$-te Element. Jetzt muss ich also die Anzahl der Anordnungen berechnen, die diese Eigenschaft erfüllen.
Wenn du mich fragst, dann erfüllt diese Eigenschaft keine Anordnung, denn: Die Tupel $(1,9)$, $(2,8)$ und $(3,7)$ müssen von der gleichen Farbe sein. Nach dem einem Tupel die Farbe zugewiesen wurde, bleibt jeweils nur noch eine Perle dieser Farbe übrig, sodass keine zwei Tupel dieser Art der selben Farbe existieren können. Damit kann $(4,6)$ kein Tupel derart sein, dass $4$ und $6$ die gleiche Farbe haben.
Also ist die Anzahl dieser Möglichkeiten gleich Null, oder?
|
|
|
| |
|
Vielen Dank an dich, für die gute Unterstützung. Dann lass uns mal zusammentragen: Das Ergebnis ist dann also
[mm] $\frac{1}{2}\cdot \frac{9!}{3!^3}$,
[/mm]
um die Aufgabe endlich mal abzuschließen ;)
|
|
|
| |
|
Ja, vorausgesetzt, dass die Interpretation der Aufgabe richtig ist.
Liebe Grüße,
UniversellesObjekt
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
