Aufgabe:
Sei \(\Omega= \{1, . . . , n\} \) und sei \( G := \text{Sym}(\Omega) \). Zeigen Sie:
(a) Erzeugen \( \pi_1, \pi_2 \in G \) dieselbe zyklische Untergruppe von \( G \), so gilt \( f(\pi_1) = f(\pi_2) \).
(b) Sei \( \pi ∈ G \) von Ordnung \( m \). Die Anzahl der Bahnen von \( \langle\pi\rangle \)auf \( \Omega \) ist
$$\frac{1}{m}\sum_{d\mid m}f(\pi^d)\varphi\left(\dfrac{m}{d}\right)$$.
Definition einer Bahn:
Es sei \( \triangleright \) die (Links-)Operation einer Gruppe \( (G,∗) \) auf einer Menge \( X \). Für jedes \( x \in X \) nennt man dann
\( G\triangleright x:=\{g\triangleright x\mid g\in G\} \)
die Bahn.
Ansatz:
Für \( \pi \in \text{Sym}(\Omega) \) betrachtet man die Wirkung von \( \langle \pi \rangle \) auf \( \Omega \). Mit dem Lemma von Burnside: $$\#\text{Anzahl Bahnen}=\frac{1}{m}\sum_{k=1}^m\left|\operatorname{Fix}(\pi^k)\right| \space \space (1)$$, wobei \( \operatorname{Fix}(\pi^k)=\{i\in\Omega\mid\pi^k(i)=i\} \) ist kann man diese Summe die gegeben ist mit Permutationstheorie so umformen, dass die gewünschte Summe aus (b) rauskommt.
Wenn \( \text{ggt}(k,m) =d \), dann legt \( \pi^k \) die gleiche Anzahl von Elementen von \( \Omega \) fest wie \( \pi^d \). Aber es gibt \( \varphi (\frac{m}{d}) \) Elemente mit \( k\in\{1,\dots,m\} \), so dass \( \text{ggt}(k,m)=d \). Dann ergibt sich:
$$ \sum_{k=1}^m\left|\operatorname{Fix}(\pi^k)\right| = \sum_{d,\space d \mid m}\varphi\biggl(\frac{m}{d}\biggr)\left|\operatorname{Fix}(\pi^d)\right| \space \space (2) $$.
Nun wird \( (2) \) in \( (1) \) eingefügt und man erhält die Formel aus (b) (es gilt \( f(\_) = \left|\operatorname{Fix}(\_)\right| \) ).
Kontext: Da ich gerade für eine Mathe Klausur (Diskrete Mathematik) lerne schaue ich mir ein paar Altklausuren an, wobei diese Aufgabe aus einer der Klausuren ist. Danke im voraus!
