G. Nebe, M. Künzer 21.08.2006

Diskrete Strukturen, SS 06

Lösung zur Scheinklausur

Aufgabe 1

(1) Wir haben (\begin{matrix}4+4−1 \\ 4−1 \end{matrix}) = 35 Möglichkeiten.

(2) Wir erhalten ((1, 3, 2) ∘ (1, 4, 3) ∘ (1, 3))^{2} = (1, 3, 4, 2)^{2} = (1, 4)(2, 3), und dieses Element hat Ordnung 2.

(3) Wir müssen die Anzahl der fixpunktfreien Permutationen in S_{5} bestimmen. Diese ergibt sich zu

5! · ∑_{i=0}^{5} \frac{(−1)^{i}}{i!} = 5! (\frac{1}{0!} − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!} + \frac{1}{4!} − \frac{1}{5!}) = 44 .

(4) Da 91 = 7 · 13 in eine gerade Zahl paarweise verschiedener Primfaktoren zerfällt, ist μ(91) = 1. Aufgabe 2 Wir kürzen u(X) := X, v(X) := X^{2} + X + 1 und w(X) := X^{3} + X + 1 ab. Zwischenergebnisse sind

\begin{aligned}1 & = & u(X) · (X^{4} + X^{3}) & + & v(X)w(X) · 1 \\ 1 & = & v(X) · (X^{3} + X^{2} + X + 1) & + & u(X)w(X) · X \\ 1 & = & w(X) · (X + 1) & + & u(X)v(X) · X \end{aligned}

Somit erfüllt

f̃(X) := 1 · v(X)w(X) · 1 + 1 · u(X)w(X) · X + X^{2} · u(X)v(X) · X = X^{6} + X^{5} + X^{3} + X^{2} + 1

die verlangten Kongruenzen. Polynomdivision durch u(X)v(X)w(X) liefert dann die Lösung

f(X) = X^{3} + X^{2} + X + 1 ,

die die Gradbedingung erfüllt. Aufgabe 3

(1) Es ist ^{b}a = (1, 6, 5, 4, 3, 2) = a^{−1} = a^{5}. Also ist jedes Element von G von der Form a^{i}b^{j} mit 0 ≤ i ≤ 5 und 0 ≤ j ≤ 1. Somit wird

G = {a^{0}, a^{1}, a^{2}, a^{3}, a^{4}, a^{5}, a^{0}b, a^{1}b, a^{2}b, a^{3}b, a^{4}b, a^{5}b}
= {id, (1, 2, 3, 4, 5, 6), (1, 3, 5)(2, 4, 6), (1, 4)(2, 5)(3, 6), (1, 5, 3)(2, 6, 4), (1, 6, 5, 4, 3, 2) ,
(2, 6)(3, 5), (1, 2)(3, 6)(4, 5), (1, 3)(4, 6), (1, 4)(2, 3)(5, 6), (1, 5)(2, 4), (1, 6)(2, 5)(3, 4)} .

Man kann auch einen Baum erstellen. Der Aufwand dafür ist etwas größer.

(2) Nach dem Lemma von Burnside ergibt sich die Anzahl der Bahnen von G auf A_{m} zu

\frac{1}{12} (\underbrace{1 · m^{6}}_{zu id} + \underbrace{2 · m^{1}}_{zu (1, 2, 3, 4, 5, 6) etc.} + \underbrace{2 · m^{2}}_{zu (1, 3, 5)(2, 4, 6) etc.} + \underbrace{4 · m^{3}}_{zu (1, 4)(2, 5)(3, 6) etc.} + \underbrace{3 · m^{4}}_{zu (2, 6)(3, 5) etc.}) .

Insbesondere ergibt sich die gefragte Anzahl der Bahnen von G auf A_{3} zu 92. Aufgabe 4 Minimale aufspannende Teilgraphen sind die folgenden.

[figure: 1; 0.2; 2; 0.1; 0.1; 4; 3; 1; 0.2; 2; 0.1; 0.1; 4; 3; 1_{0.2}  2_{0.1} 4  _{0.1}  3; 1; 0.2; 2; 0.1; 4; 0.1; 3; 1; 0.2; 2; 0.1; 4; 0.1; 3]

Verlangt war, einen von diesen anzugeben.

Aufgabe 5

(1) Eine Erzeugermatrix von (C|C′) ist gegeben durch

(\begin{matrix}1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{matrix}) .

(2) Der Minimalabstand ist gegeben durch d((C|C′)) = min{2d(C), d(C′)}. Wir erkennen direkt, daß d(C) = 1 und d(C′) = 2. Also ist d((C|C′)) = min{2, 2} = 2.

Den Minimalabstand aus einer Prüfmatrix für (C|C′) abzulesen, ist möglich, aber aufwendiger.

Aufgabe 6

(1) Es sind mit γ^{9} und γ^{13} auch (γ^{9})^{4} = γ^{36} = γ^{6} und (γ^{13})^{4} = γ^{52} = γ^{7} Nullstellen von f(X). Wegen deg f = 4 ist die Menge der Nullstellen von f(X) in F_{16} damit zu {γ^{6}, γ^{7}, γ^{9}, γ^{13}} bekannt.

(2) Es ist γ eine primitive 15-Einheitswurzel (da γ^{3} ≠ 1 und γ^{5} = γ^{2} + γ ≠ 1), und deren 2 aufeinanderfolgende Potenzen γ^{6}, γ^{7} sind Nullstellen von f(X). Also beträgt der designierte Minimalabstand 2 + 1 = 3.

Aufgabe 7

(1) Die Prüfmatrix ist nur bis auf eine Permutation der Zeilen bestimmt. Wir können geschickterweise folgende nehmen.

(\begin{matrix}1 & 0 \\ 0 & 1 \\ 1 & β^{0} \\ 1 & β^{1} \\ 1 & β^{2} \\ 1 & β^{3} \\ 1 & β^{4} \\ 1 & β^{5} \\ 1 & β^{6} \end{matrix} )

Denn dann liefern die Erzeugnisse der Zeilen gerade alle eindimensionalen Teilräume von F_{8}^{1×2}. Dazugehörend erhalten wir die Prüfmatrix

(\begin{matrix}1 & β^{0} & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & β^{1} & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & β^{2} & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & β^{3} & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & β^{4} & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & β^{5} & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & β^{6} & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

(2) Die Länge von C beträgt N = 9, der Minimalabstand d = 3 (wie bei allen Hammingcodes). Die Singleton-Schranke besagt nun, daß die Dimension von C nicht über N − d + 1 = 7 liegen sollte. Nun ist die Dimension von C gerade k = 7, d.h. die Singleton-Schranke wird angenommen.

Aufgabe 8

Die Aussage ist falsch. Z.B. ist 2^{3} ein Teiler von |S_{4}|, ohne daß S_{4} ein Element der Ordnung 2^{3} enthält. In der Tat müßte es hierzu ein Element in S_{4} geben, welches in Zykeldarstellung einen Zykel der Länge 8 aufweist, was wegen 8 > 4 nicht möglich ist.