G. Nebe, M. Künzer Abgabe am 04.11.04.

Algebra I, WS 04/05

Lösung 3

Aufgabe 13.

(1) Im folgenden beschreiben wir die Schritte des Bahnenalgorithmus. In der Praxis empfiehlt es sich, sich den Graphen schrittweise aufzubauen.

(a) Die folgende Lösung ist nicht eindeutig. Zur Unterscheidung schreiben wir die auftretenden Urbildfunktionen w_{i} mit i dem jeweiligen Element der base. Schritt I. Betrachte die Bahn G · 3. Schreibe a := (1, 2, 3) und b := (3, 4, 5). Schritt 1. Kandidaten K = {3} mit w_{3}(3) = 1. Schritt 2. Kandidaten K = {1, 4} mit w_{3}(1) = a und w_{3}(4) = b. Dem Erzeugendensystem S_{3} von Stab_{G}(3) wird nichts hinzugefügt. Schritt 3. Kandidaten K = {2, 5} mit w_{3}(2) = a^{2} und w_{3}(5) = b^{2}. Wegen ba3 = 1 = a3 wird a^{−1}ba = (2, 4, 5) zu S_{3} hinzugefügt. Wegen ab3 = b3 wird b^{−1}ab = (1, 2, 5) zu S_{3} hinzugefügt. Schritt 4. Kandidaten K = ∅. Wegen a^{3}3 = 3 wird a^{3} = 1 zu S_{3} hinzugefügt. Wegen ba^{2}3 = 2 = a^{2}2 wird a^{−1}ba^{2} = (1, 4, 5) zu S hinzugefügt. Wegen ab^{2}3 = 5 = b^{2}3 wird b^{−2}ab^{2} = (1, 2, 4) zu S_{3} hinzugefügt. Nun ist (1, 4, 5) = (^{(1,2,5)}(2, 4, 5))^{−1} und (1, 2, 4) = (^{(2,4,5)}(1, 2, 5))^{−1}, und so Stab_{G}(3) = ⟨S⟩ = ⟨(2, 4, 5), (2, 1, 5)⟩. Schritt II. Betrachte die Bahn Stab_{G}(3) · 2. Schreibe c := a^{2}ba = (2, 4, 5) und d := b^{2}a^{2}b = (2, 1, 5). Schritt 1. Kandidaten K = {2} mit w_{2}(2) = 1. Schritt 2. Kandidaten K = {4, 1} mit w_{2}(4) = c und w_{2}(1) = d. Dem Erzeugendensystem S_{2} von Stab_{G}(3, 2) wird nichts hinzugefügt. Schritt 3. Kandidaten K = {5} mit w(5) = c^{2}. Wegen dc2 = 4 = c2 wird c^{−1}dc = (5, 1, 4) zu S_{2} hinzugefügt. Wegen cd2 = 1 = d2 wird d^{−1}cd = (5, 4, 1) zu S_{2} hinzugefügt. Wegen d^{2}2 = c^{2}2 wird c^{−2}d^{2} = (1, 4, 5) zu S_{2} hinzugefügt. Schritt 4. Kandidaten K = ∅. Wegen c^{3}2 = 2 wird c^{3} = 1 zu S_{2} hinzugefügt. Wegen dc^{2}2 = 2 wird dc^{2} = (1, 5, 4) zu S_{2} hinzugefügt. Insgesamt wird Stab_{G}(3, 2) = ⟨S_{2}⟩ = ⟨(1, 4, 5)⟩. Schritt III. Betrachte die Bahn Stab_{G}(3, 2) · 1. Schreibe e := c^{2}dc = aba^{2} = (1, 4, 5). Hier müßte man auf die Produktdarstellung von c und d in a und b zurückgreifen, wenn nicht die einfachere Darstellung aba^{2} = (1, 4, 5) bereits in Schritt I aufgetaucht wäre. Schritt 1. Kandidaten K = {1} mit w_{1}(1) = 1. Schritt 2. Kandidaten K = {4} mit w_{1}(4) = e. Dem Erzeugendensystem S_{1} von Stab_{G}(3, 2, 1) wird nichts hinzugefügt. Schritt 3. Kandidaten K = {5} mit w_{1}(5) = e^{2}. Dem Erzeugendensystem S_{1} wird nichts hinzugefügt. Schritt 4. Kandidaten K = ∅. Wegen e^{3}1 = 1 wird e^{3} = 1 zu S_{1} hinzugefügt. Insgesamt wird Stab_{G}(3, 2, 1) = ⟨S_{1}⟩ = 1. Wir erhalten als base das Tupel (3, 2, 1) und als strong generators die folgende Tafel.

w_{3}(1) = a = (1, 2, 3)  w_{2}(1) = b^{2}a^{2}b = (1, 5, 2)  w_{1}(1) = 1  = id
w_{3}(2) = a^{2} = (1, 3, 2)  w_{2}(2) = 1  = id  w_{1}(4) = aba^{2} = (1, 4, 5)
w_{3}(3) = 1 = id  w_{2}(4) = a^{2}ba = (2, 4, 5)  w_{1}(5) = ab^{2}a^{2} = (1, 5, 4)
w_{3}(4) = b = (3, 4, 5)  w_{2}(5) = a^{2}b^{2}a = (2, 5, 4)
w_{3}(5) = b^{2} = (3, 5, 4)

(b) Wegen der Indizes G ≥^{5} Stab_{G}(3) ≥^{4} Stab_{G}(3, 2) ≥^{3} Stab_{G}(3, 2, 1) = 1 ist |G| = 5 · 4 · 3 = 60.

(c) Es ist (1, 3, 5)3 = 5, also (1, 3, 5) in G genau dann, wenn w_{3}(5)^{−1}(1, 3, 5) = (1, 4, 5) in Stab_{G}(3). Nun ist 2(1, 4, 5) = 2, also (1, 4, 5) in Stab_{G}(3) genau dann, wenn w_{2}(2)^{−1}(1, 4, 5) = (1, 4, 5) in Stab_{G}(3, 2). In der Tat ist (1, 4, 5) = e = aba^{2}. Rückwärts gerechnet erhalten wir

(1, 3, 5) = w_{3}(5)(1, 4, 5) = b^{2}aba^{2} .

An dieser Stelle empfiehlt sich als Probe ein direktes Nachrechnen.

(2) Sei G = ⟨(1, 2, 3, 4, 5, 6), (1, 4)⟩ ≤ S_{6}.

(a) Schritt I. Betrachte die Bahn G · 1. Schreibe a := (1, 2, 3, 4, 5, 6) und b := (1, 4). Sei S_{1} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{1} unterschlagen wir. Schritt 1. Kandidaten K = {1} mit w_{1}(1) = 1. Schritt 2. Kandidaten K = {2, 4} mit w_{1}(2) = a und w_{1}(4) = b. Schritt 3. Kandidaten K = {3, 5} mit w_{1}(3) = a^{2}, w_{1}(5) = ab. Ergänze S_{1} um a^{−1}ba = (3, 6). Schritt 4. Kandidaten K = {6} mit w_{1}(6) = a^{2}b. Ergänze S_{1} um a^{−2}ba^{2} = (2, 5). Wir erhalten Stab_{G}(1) = ⟨S_{1}⟩ = ⟨a^{−1}ba, a^{−2}ba^{2}⟩ = ⟨(2, 5), (3, 6)⟩. Schritt II. Betrachte die Bahn Stab_{G}(1) · 2. Sei S_{2} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{2} unterschlagen wir. Schritt 1. Kandidaten K = {2} mit w_{2}(2) = 1. Schritt 2. Kandidaten K = {5} mit w_{2}(5) = a^{−2}ba^{2}. Ergänze S_{2} um a^{−1}ba. Schritt 3. Kandidaten K = ∅. Wir erhalten Stab_{G}(1, 2) = ⟨S_{2}⟩ = ⟨a^{−1}ba⟩ = ⟨(3, 6)⟩. Schritt III. Betrachte die Bahn Stab_{G}(1) · 3. Sei S_{2} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{2} unterschlagen wir. Schritt 1. Kandidaten K = {3} mit w_{3}(3) = 1. Schritt 2. Kandidaten K = {6} mit w_{3}(6) = a^{−1}ba. Schritt 3. Kandidaten K = ∅. Wir erhalten Stab_{G}(1, 2, 3) = ⟨S_{3}⟩ = ⟨∅⟩ = 1. Wir erhalten als base das Tupel (1, 2, 3), und als strong generators die folgende Tafel.

w_{1}(1) = 1 = id  w_{2}(2) = 1  = id  w_{3}(3) = 1  = id
w_{1}(2) = a = (1, 2, 3, 4, 5, 6)  w_{2}(5) = a^{−2}ba^{2} = (2, 5)  w_{3}(6) = a^{−1}ba = (3, 6)
w_{1}(3) = a^{2} = (1, 3, 5)(2, 4, 6)
w_{1}(4) = b = (1, 4)
w_{1}(5) = ab = (1, 5, 6)(2, 3, 4)
w_{1}(6) = a^{2}b = (1, 6, 2, 4, 3, 5)

(b) Wegen der Indizes G ≥^{6} Stab_{G}(1) ≥^{2} Stab_{G}(1, 2) ≥^{2} Stab_{G}(1, 2, 3) = 1 ist |G| = 6 · 2 · 2 = 24.

(c) Es ist (1, 2)1 = 2, und also (1, 2) in G genau dann, wenn w_{1}(2)^{−1}(1, 2) = (1, 6, 5, 4, 3, 2)(1, 2) = (2, 6, 5, 4, 3) in Stab_{G}(1). Nun ist (2, 6, 5, 4, 3)2 = 6, und also wegen Stab_{G}(1) · 2 = {2, 5} in der Tat (2, 6, 5, 4, 3) nicht in Stab_{G}(1). Folglich ist (1, 2) ∉ G.

(d) Zur Berechnung des Zentrums wenden wir den verfeinerten Bahnenalgorithmus auf die Operation von G auf sich selbst via Konjugation an. Beachte, daß Stab_{G}(a, b) = Z(G), da ein Element, das mit a und b vertauscht, auch mit jedem Element von ⟨a, b⟩ = G vertauscht. Schritt I. Betrachte die Bahn ^{G}(1, 4). Sei S_{(1,4)} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{(1,4)} unterschlagen wir. Schritt 1. Kandidaten K = {(1, 4)}. Schritt 2. Kandidaten K = {(2, 5)}. Ergänze S_{(1,4)} um b. Schritt 3. Kandidaten K = {3, 6}. Ergänze S_{(1,4)} um a^{−1}ba. Schritt 4. Kandidaten K = ∅. Ergänze S_{(1,4)} um a^{3}. Wir erhalten Stab_{G}((1, 4)) = ⟨S_{(1,4)}⟩ = ⟨(1, 4), (2, 5), (1, 4)(2, 5)(3, 6)⟩ = ⟨(1, 4), (2, 5), (3, 6)⟩. Schritt II. Betrachte die Bahn ^{G}(1, 2, 3, 4, 5, 6). Sei S_{(1,2,3,4,5,6)} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{(1,2,3,4,5,6)} unterschlagen wir. Schritt 1. Kandidaten K = {(1, 2, 3, 4, 5, 6)}. Schritt 2. Kandidaten K = {(1, 5, 6, 4, 2, 3), (1, 5, 3, 4, 2, 6), (1, 2, 6, 4, 5, 3)}. Schritt 3. Kandidaten K = ∅. Schritt 3. Kandidaten K = {3, 6}. Ergänze S_{(1,4)} um a^{−1}ba. Schritt 4. Kandidaten K = ∅. Ergänze S_{(1,2,3,4,5,6)} um a^{3}. Wir erhalten Z(G) = Stab_{G}((1, 4), (1, 2, 3, 4, 5, 6)) = ⟨S_{(1,2,3,4,5,6)}⟩ = ⟨(1, 4)(2, 5)(3, 6)⟩.

Beachte, daß das Verfahren an dieser Stelle nicht fortgesetzt werden kann - über den Kern der Operation, welcher hier das Zentrum der Gruppe darstellt, sagt der verfeinerte Bahnenalgorithmus nichts. Nur sind wir hier in der glücklichen Lage, als Zentrum eine zyklische Gruppe vorzufinden, welche von einem Element der Ordnung 2 erzeugt wird, und haben somit |Z(G)| = 2. Wir bemerken noch, daß die vorstehende Berechnung des Zentrums wegen der Indizes G ≥^{3} Stab_{G}((1, 4)) ≥^{4} Stab_{G}((1, 4), (1, 2, 3, 4, 5, 6)) ≥^{2} 1 auch nochmals |G| = 3 · 4 · 2 = 24 liefert. Eine base und strong generators erhalten wir mit dieser Rechnung allerdings nicht. Auch zur Feststellung, ob und wie ein gegebenes Element von S_{6} sich in G befindet, taugt diese Rechnung nur bedingt - man muß dazu alle Elemente des Zentrums kennen. Dies ist hier zwar der Fall, im allgemeinen erfordert dies aber eine weitere Untersuchung.

(3) (a) Lösungsweg 1. Wir betrachten die Operation auf F_{5}^{2}. Schritt I. Betrachte die Bahn G · (\begin{matrix}1 \\ 0 \end{matrix}). Sei S_{( \begin{matrix}1 \\ 0 \end{matrix} )} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{( \begin{matrix}1 \\ 0 \end{matrix} )} unterschlagen wir.

Schritt 1. Kandidaten K = \{(\begin{matrix}1 \\ 0 \end{matrix})\}. Schritt 2. Kandidaten K = \{(\begin{matrix}1 \\ −1 \end{matrix}) , (\begin{matrix}0 \\ 1 \end{matrix})\}. Schritt 3. Kandidaten K = \{(\begin{matrix}0 \\ −2 \end{matrix}) , (\begin{matrix}−1 \\ 1 \end{matrix}) , (\begin{matrix}1 \\ 1 \end{matrix})\}.

Schritt 4. Kandidaten K = \{(\begin{matrix}−2 \\ −2 \end{matrix}) , (\begin{matrix}−2 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 2 \end{matrix}) , (\begin{matrix}2 \\ 0 \end{matrix})\}. Ergänze S_{( \begin{matrix}1 \\ 0 \end{matrix} )} um ba^{3}bab = (\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix}).

Schritt 5. Kandidaten K = \{(\begin{matrix}−2 \\ 2 \end{matrix}) , (\begin{matrix}2 \\ 2 \end{matrix}) , (\begin{matrix}2 \\ −2 \end{matrix})\}. Schritt 6. Kandidaten K = \{(\begin{matrix}0 \\ −1 \end{matrix}) , (\begin{matrix}−1 \\ 0 \end{matrix})\}. Schritt 7. Kandidaten K = \{(\begin{matrix}−1 \\ −1 \end{matrix})\}. Damit bekommen wir Stab_{G}((\begin{matrix}1 \\ 0 \end{matrix})) und die Indizes G ≥^{16} Stab_{G}((\begin{matrix}1 \\ 0 \end{matrix})) ≥^{2} 1, also |G| = 16 · 2 = 32. Lösungsweg 2. Da nach dem Zentrum gefragt ist, kann man auch die Operation von G auf sich via Konjugation zu betrachten. Schritt I. Betrachte die Bahn ^{G}(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}). Sei S_{( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )} unterschlagen wir.

Schritt 1. Kandidaten K = \{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})\}. Schritt 2. Kandidaten K = \{(\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix})\}. Ergänze S_{( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )} um b = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}).

Schritt 3. Kandidaten K = \{(\begin{matrix}0 & −1 \\ −1 & 0 \end{matrix}) , (\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix})\}. Schritt 4. Kandidaten K = ∅. Ergänze S_{( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )} um aba = (\begin{matrix}0 & 2 \\ 2 & 0 \end{matrix}).

Damit bekommen wir Stab_{G}((\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})) = ⟨(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , (\begin{matrix}0 & 2 \\ 2 & 0 \end{matrix})⟩. Schritt II. Betrachte die Bahn ^{G}(\begin{matrix}1 & 1 \\ −1 & 1 \end{matrix}). Sei S_{( \begin{matrix}1 & 1 \\ −1 & 1 \end{matrix} )} das zu bildende Erzeugendensystem des Stabilisators. Wirkungslose Ergänzungen zu S_{( \begin{matrix}1 & 1 \\ −1 & 1 \end{matrix} )} unterschlagen wir.

Schritt 1. Kandidaten K = \{(\begin{matrix}1 & 1 \\ −1 & 1 \end{matrix})\}. Schritt 2. Kandidaten K = \{(\begin{matrix}1 & −1 \\ 1 & 1 \end{matrix})\}. Ergänze S_{( \begin{matrix}1 & 1 \\ −1 & 1 \end{matrix} )} um bc = (\begin{matrix}2 & 0 \\ 0 & 2 \end{matrix}). Schritt 3. Kandidaten K = ∅. Damit bekommen wir Z(G) = Stab_{G}((\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , (\begin{matrix}1 & 1 \\ −1 & 1 \end{matrix})) = ⟨(\begin{matrix}2 & 0 \\ 0 & 2 \end{matrix})⟩. Es handelt sich um ein Element der Ordnung 4, so daß sich |Z(G)| = 4 ergibt. Ferner wird auch auf diesem Wege G ≥^{4} Stab_{G}((\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})) ≥^{2} Stab_{G}((\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , (\begin{matrix}1 & 1 \\ −1 & 1 \end{matrix})) ≥^{4} 1, also |G| = 4 · 2 · 4 = 32.

(b) Siehe Lösungsweg 2 unter (a).

Aufgabe 14.

(1) Folgendes sind die Konjugiertenklassen von G, wie man mit dem Bahnenalgorithmus bestätigt.

{ id }
{ (1, 2, 3, 4, 5, 6), (1, 6, 5, 4, 3, 2) }
{ (1, 6)(2, 5)(3, 4), (1, 2)(3, 6)(4, 5), (1, 4)(2, 3)(5, 6) }
{ (1, 3, 5)(2, 4, 6), (1, 5, 3)(2, 6, 4) }
{ (1, 4)(2, 5)(3, 6) }
{ (2, 6)(3, 5), (1, 5)(2, 4), (1, 3)(4, 6) }

Beobachte hierbei, daß Konjugiertenklassen von S_{6}, geschnitten mit G, im allgemeinen in eine disjunkte Vereinigung von Konjugiertenklassen von G zerfallen. Man hätte sich auch auf die erstgenannte Einteilung von G beziehen können, das hätte aber eventuell zu Mißverständnissen Anlaß gegeben.

Die Fixpunkte sind diejenigen Abbildungen f, die auf einem Zykel konstant sind. So läßt z.B. (2, 6)(3, 5) = (1)(2, 6)(3, 5)(4) gerade m^{4} Abbildungen konstant, nämlich diejenigen mit f(2) = f(6) und f(3) = f(5). Der Exponent ist durch die Anzahl der Zykel bestimmt, so man die Zykel der Länge 1 mitzählt.

Mit Burnsides Lemma wird also die Anzahl a(m) der Bahnen, d.h. der Perlenkettenfärbungen, zu

a(m) = \frac{1}{12}(m^{6} + 3m^{4} + 4m^{3} + 2m^{2} + 2m^{1}) .

Wie folgt hieraus, daß a(m) für alle m ∈ Z einen ganzzahligen Wert annimmt?

Also z.B. a(0) = 0, a(1) = 1, a(2) = 13, a(3) = 92, a(4) = 430, a(5) = 1505, a(6) = 4291, …

(2) Seien n, m ≥ 0. Von der Menge [1, n] in die Menge [1, m] gibt es gerade

f(n, m) := ∑_{k∈[0,m]}(−1)^{m−k} (\begin{matrix}m \\ k \end{matrix}) k^{n}

surjektive Abbildungen, wie man mit Induktion nach m folgendermaßen sieht. Die Anzahl der Surjektionen von [1, n] nach [1, m] ist gleich der Anzahl der Abbildungen von [1, n] nach [1, m], also m^{n}, minus der Summe der surjektiven Abbildungen in eine echte Teilmenge von [1, m], summiert über diese Teilmengen. Das ergibt

f(n, m) = m^{n} − ∑_{l∈[0,m−1]} (\begin{matrix}m \\ l \end{matrix}) f(n, l)
= m^{n} − ∑_{l∈[0,m−1]} ∑_{k∈[0,l]}(−1)^{l−k} (\begin{matrix}m \\ l \end{matrix}) (\begin{matrix}l \\ k \end{matrix}) k^{n}
= m^{n} − ∑_{l∈[0,m−1]} ∑_{k∈[0,l]}(−1)^{l−k} (\begin{matrix}m \\ k \end{matrix}) (\begin{matrix}m−k \\ l−k \end{matrix}) k^{n}
= m^{n} − ∑_{k∈[0,m−1]} ∑_{l∈[k,m−1]}(−1)^{l−k} (\begin{matrix}m \\ k \end{matrix}) (\begin{matrix}m−k \\ l−k \end{matrix}) k^{n}
= m^{n} − ∑_{k∈[0,m−1]} (\begin{matrix}m \\ k \end{matrix}) k^{n} (∑_{l∈[0,m−k−1]}(−1)^{l} (\begin{matrix}m−k \\ l \end{matrix}))
= m^{n} − ∑_{k∈[0,m−1]} (\begin{matrix}m \\ k \end{matrix}) k^{n}( − (−1)^{m−k} + \underbrace{∑_{l∈[0,m−k]}(−1)^{l} (\begin{matrix}m−k \\ l \end{matrix})}_{= 0} )

= m^{n} + ∑_{k∈[0,m−1]}(−1)^{m−k} (\begin{matrix}m \\ k \end{matrix}) k^{n} .

Zurück zum eigentlichen Problem. Die Konjugiertenklassen von H sind die folgenden, wie man mit dem Bahnenalgorithmus bestätigt.

{ id }
{ (1, 3, 6, 4), (2, 3, 5, 4), (1, 4, 6, 3), (1, 2, 6, 5), (2, 4, 5, 3), (1, 5, 6, 2) }
{ (1, 6)(3, 4), (2, 5)(3, 4), (1, 6)(2, 5) }
{ (1, 2, 4)(3, 6, 5), (1, 3, 5)(2, 6, 4), (1, 2, 3)(4, 6, 5), (1, 4, 5)(2, 6, 3),
(1, 4, 2)(3, 5, 6), (1, 5, 3)(2, 4, 6), (1, 3, 2)(4, 5, 6), (1, 5, 4)(2, 3, 6) }
{ (1, 2)(3, 4)(5, 6), (1, 6)(2, 4)(3, 5), (1, 5)(2, 6)(3, 4), (1, 6)(2, 3)(4, 5), (1, 4)(2, 5)(3, 6), (1, 3)(2, 5)(4, 6) }

Eine Element aus H fixiert eine Abbildung, falls diese auf seinen Zykeln konstant ist. Mit obiger Formel für die Anzahl der Surjektionen und Burnsides Lemma erhalten wir somit für die Anzahl a′(m) der Bahnen, d.h. der Würfelfärbungen,

a′(m) := \frac{1}{24}(f(6, m)+6f(3, m)+3f(4, m)+8f(2, m)+6f(3, m)) = \frac{1}{24} ∑_{k∈[0,m]}(−1)^{m−k} (\begin{matrix}m \\ k \end{matrix}) (k^{6} +3k^{4} +12k^{3} +8k^{2}) .

Also a′(0) = 0, a′(1) = 1, a′(2) = 8, a′(3) = 30, a′(4) = 68, a′(5) = 75, a′(6) = 30, a′(7) = 0, …

Aufgabe 15.

(1) Aussage ist richtig. In der Tat ist Fix_{M}(^{g}x) = g Fix_{M}(x), da ein Element m ∈ M in der linken Seite enthalten ist genau dann, wenn gxg^{−1}m = m, d.h. genau dann, wenn xg^{−1}m = g^{−1}m, d.h. genau dann, wenn g^{−1}m ∈ Fix_{M}(g), d.h. genau dann, wenn m ∈ g Fix_{M}(x), d.h. genau dann, wenn m in der rechten Seite enthalten ist. Und die Multiplikation mit g ist eine Bijektion von M in sich, ändert also die Elementzahl nicht.

(2) Die Aussage ist richtig. Denn mit Burnsides Lemma und mit (1) wird

|G\M| = \frac{1}{|G|} ∑_{y∈G} | Fix_{M}(y)|
= \frac{1}{|G|} ∑_{x∈ConjCl(G)} ∑_{y∈^{G}x} | Fix_{M}(y)|
= \frac{1}{|G|} ∑_{x∈ConjCl(G)} ∑_{y∈^{G}x} | Fix_{M}(x)|
= \frac{1}{|G|} ∑_{x∈ConjCl(G)} |^{G}x|| Fix_{M}(x)|
= ∑_{x∈ConjCl(G)} \frac{| Fix_{M} (x)|}{|C_{G}(x)|} .

(3) Die Aussage ist richtig. Denn da die Anzahl der G-Bahnen der G-Menge G/U gleich 1 ist, wird mit Burnsides

Lemma

1 = \frac{1}{|G|} ∑_{x∈G} | Fix_{G/U}(x)|
= \frac{1}{|G|} ∑_{x∈G} |\{gU : xgU = gU\}|
= \frac{1}{|G|} ∑_{x∈G} |\{gU : g^{−1}xgU = U\}|
= \frac{1}{|G|} ∑_{x∈G} |\{gU : ^{g^{−1}}x ∈ U\}| .

(4) Die Aussage ist falsch. Sind z.B. G = S_{3}, U = ⟨(1, 2)⟩ und M = G/U = {U, (1, 2, 3)U, (1, 3, 2)U} mit |M| = 3, so zerfällt M × M nur in die 2 Bahnen

\begin{matrix}\{(U, U), ((1, 2, 3)U, (1, 2, 3)U), ((1, 3, 2)U, (1, 3, 2)U)\}, \\ \{(U, (1, 2, 3)U), (U, (1, 3, 2)U), ((1, 2, 3)U, (1, 3, 2)U), ((1, 2, 3)U, U), ((1, 3, 2)U, U), ((1, 3, 2)U, (1, 2, 3)U)\} , \end{matrix}

wie man mit dem Bahnenalgorithmus bestätigt.

(5) Aussage ist richtig. In der Tat ist Fix_{M×M}(x) = Fix_{M}(x) × Fix_{M}(x), und dementsprechend | Fix_{M×M}(x)| = | Fix_{M}(x)|. Burnsides Lemma gibt nun

|G\(M × M)| = \frac{1}{|G|} ∑_{x∈G} | Fix_{M×M}(x)| = \frac{1}{|G|} ∑_{x∈G} | Fix_{M}(x)|^{2} .

www2.math.rwth-aachen.de:8008