Lösung zur Vordiplomklausur A ”Diskrete Strukturen“

Marc Ensenbach

7. September 2001

Ankreuzteil

Aufgabe A1

(1) Nein. Die gegebene Rekursionsformel ist die für die Stirlingzahlen zweiter Art.

(2) Ja. Die Stirlingzahl erster Art s_{n,k} gibt die Anzahl der Permutationen in S_{n} an, die aus k ziffernfremden Zyklen bestehen. Summiert man für festes n über alle möglichen k, so erhält man die Anzahl aller Permutationen in S_{n}, also n!.

(3) Ja. s_{n,n−1} ist die Anzahl der Permutationen in S_{n}, die aus n − 1 ziffernfremden Zyklen bestehen. Eine solche Permutation besteht aus n − 2 Einerzyklen und einem Zweierzyklus, und die Permutation ist durch die Angabe des Zweierzyklus bereits eindeutig bestimmt. Da es bei Zweierzyklen nicht auf die Reihenfolge der Zahlen ankommt, entspricht das Problem der Auswahl von zweielementigen Teilmengen der S_{n}, womit es genau \binom{n}{2} solche Zyklen gibt.

(4) 11. Mit der Rekursionsformel s_{n,k} = s_{n−1,k−1} + (n − 1)s_{n−1,k} für Stirlingzahlen erster Art erhält man s_{4,2} = s_{3,1} + 3s_{3,2} = 2 + 3 · 3 = 11.

Aufgabe A2

(1) Ja. 1 + x ist in ℚ[[X]] invertierbar, da der konstante Term von Null verschieden ist. Damit ist auch \frac{x}{1+x} = x\frac{1}{1+x} als Produkt zweier Elemente aus ℚ[[X]] in ℚ[[X]].

(2) Nein. x ist in ℚ[[X]] nicht invertierbar, da der konstante Term Null ist.

(3) Ja. x^{3}A = x^{3} ∑_{j=0}^{∞} a_{j}x^{j} = ∑_{j=0}^{∞} a_{j}x^{j+3} = ∑_{i=3}^{∞} a_{i−3}x^{i} mit der Indexverschiebung j ↦ i − 3.

(4) Nein. (1 + x)^{2} = 1 + 2x + x^{2} ≠ 1 + x^{2} = 1^{2} + 1^{2}x^{2}.

Aufgabe A3

(1) Nein. Die Elemente in K[x] mit Grad 0 sind gerade die Einheiten, und Einheiten sind nach Definition nicht irreduzibel.

(2) Ja. Ein Polynom der Form x + a kann nicht in zwei irreduzible Polynome zerlegt werden.

(3) Nein. x^{4} + x^{2} + 1 ∈ ℤ_{2}[x] hat in ℤ_{2} keine Nullstelle, ist aber nach (4) nicht irreduzibel.

(4) Nein. x^{4} + x^{2} + 1 = (x^{2} + x + 1)^{2}.

Aufgabe A4

(1) 16. Jedes Polynom g ∈ ℤ_{2}[x] kann mit Polynomdivision geschrieben werden als g = fq + r mit Grad r < Grad f. Da [g]_{f} = [fq + r]_{f} = [r]_{f} gilt, bilden die Polynome mit einem Grad kleiner Grad f ein Vertretersystem. Da es in ℤ_{2}[x] genau 2^{Grad f} Polynome mit einem Grad kleiner Grad f gibt, existieren hier 2^{Grad(x^{4}+1)} = 2^{4} = 16 Vertreterpolynome, womit |R| = 16 gilt.

(2) Nein. Nach Vorlesung ist R = K[x]/fK[x] für einen Körper K und ein Polynom f genau dann ein Körper, wenn f über K[x] irreduzibel ist. Da x^{4} + 1 = (x + 1)^{4} gilt, ist f nicht irreduzibel, also ist R kein Körper.

(3) Ja. Es gilt [x^{2} +x+1]·[x^{3} +x^{2} +1]_{f} = [x^{5} +x^{4} +x^{2} +x^{4} +x^{3} +x+x^{3} +x^{2} +1]_{f} = [x^{5} +x+1]_{f}. Da x^{5} + x + 1 = (x^{4} + 1)x + 1 ist, gilt [x^{5} + x + 1]_{f} = [1]_{f}, also ist [x^{2} + x + 1]_{f} das Inverse von [x^{3} + x^{2} + 1].

(4) 5. Da f = x^{4} + 1 = (x + 1)^{4} gilt, sind die Teiler von f genau die (x + 1)^{i}, i = 0; 1; …; 4.

Aufgabe A5

(1) Ja. Satz der Vorlesung.

(2) Nein. Dann wäre die Summe der Grade 7 · 3 = 21, was nicht möglich ist, da nach dem Handschlaglemma die Summe der Grade immer gerade ist.

(3) 15. Nach Vorlesung hat der vollständige Graph \binom{6}{2} = \frac{1}{2} · 6 · 5 = 15 Kanten.

Rechenaufgaben ohne Begründung

Aufgabe R1

(1) 60. Nach Vorlesung ist | Inj(\{1; 2; 3\}; \{1; 2; 3; 4; 5\})| = |\{1; 2; 3; 4; 5\}|\underline{|\{1;2;3\}|} = 5\underline{3} = 5·4·3 = 60.

(2) 14. Vorlesung: | Surj({1; 2; 3; 4}; {1; 2})| = |{1; 2}|! · S_{|{1;2;3;4}|,|{1;2}|} = 2!S_{4,2} = 2 · 7 = 14.

Aufgabe R2

(1) Die Zykeldarstellung ist klarerweise (1 7 2)(4 8 5 9 6).

(2) 12. Die Ordnung ist das positive kgV der einzelnen Zykellängen, sofern die Zykeln ziffernfremd sind, hier also 12 ∈ kgV(3; 4).

(3) Die Darstellung lautet (1 6 4)(2 5 7 3).

(4) Die Darstellung ist (2 5 7 3), da b^{27} = b^{2·12+3} = (b^{12})^{2} b^{3} = b^{3}.

Aufgabe R3 d = 1, a = x, b = x^{2} + x + 1. Nach dem Euklidischen Algorithmus ist x^{4} + 1 = (x^{3} + x^{2} + 1)(x + 1) + (x^{2} + x), x^{3} + x^{2} + 1 = (x^{2} + x)x + 1, x^{2} + x = 1 · (x^{2} + x), also ist 1 ein ggT von x^{4} + 1 und x^{3} + x^{2} + 1. Durch Rückwärtsauflösen erhält man 1 = (x^{3} + x^{2} + 1) − (x^{2} + x)x = (x^{3} + x^{2} + 1) − ((x^{4} + 1) − (x^{3} + x^{2} + 1)(x + 1))x = g − (f − (x + 1)g)x = g − (xf − (x^{2} + x)g) = (x^{2} + x + 1)g − xf = (x^{2} + x + 1)g + xf.

Aufgabe R4

(1) 40. φ(100) = φ(2^{2} · 5^{2}) = φ(2^{2}) · φ(5^{2}) = (2 − 1) · 2 · (5 − 1) · 5 = 2 · 4 · 5 = 40.

(2) 69. Nach dem Satz von Euler ist a^{φ(m)} ≡ 1 mod m für 1 ∈ ggT(a; m). Da 1 ∈ ggT(13; 100) ist, gilt 13^{162} = 13^{40·4+2} = (13^{φ(100)})^{4} · 13^{2} ≡ 13^{2} = 169 ≡ 69 mod 100.

Aufgabe R5

(1) 4. Es gilt immer dim C = l − Grad g, (l Codelänge), hier dim C = 7 − 3 = 4.

(2) 16. C ist ein ℤ_{2}-Vektorraum der Dimension 4, hat also |ℤ_{2}|^{4} = 2^{4} = 16 Elemente.

(3) 3. Nach einem Beispiel aus der Vorlesung ist die Minimaldistanz größer/gleich 3, und da der zu 1 gehörige Codierungsvektor (1; 1; 0; 1; 0; 0; 0), erhalten über die 7-Bit-Darstellung von 1 · g, vom Nullvektor die Distanz 3 hat, muß 3 auch die Minimaldistanz sein.

(4) 1. Da (1; 1; 0; 0; 0; 0; 0; 0) zu (1; 1; 0; 1; 0; 0; 0) die Distanz 1 hat, wird der gegebene Vektor zu (1; 1; 0; 1; 0; 0; 0) korrigiert. Nach (3) liefert die Decodierung dieses Vektors 1.

Aufgabe R6 {2; 4; 5}. Rekonstruiert man den Baum aus dem Prüfercode, so erhält man der Reihe nach die Kanten {1; 2}; {4; 3}; {5; 3}; {3; 2}; {2; 6}. Daher ist 3 mit den Knoten 4, 5 und 2 verbunden.

Aufgaben mit Lösungsweg

Aufgabe L1

Sei A = ∑_{n=0}^{∞} a_{n}x^{n}. Dann gilt A = a_{0} + a_{1}x + ∑_{n=2}^{∞} a_{n}x^{n}. Setzt man die Anfangsbedin-

gungen und die Rekursionsformel ein, erhält man A = 1 + x + ∑_{n=2}^{∞}(a_{n−1} + 2a_{n−2})x^{n} =

1 + x + ∑_{n=2}^{∞} a_{n−1}x^{n} + 2 ∑_{n=2}^{∞} a_{n−2}x^{n} = 1 + x + x ∑_{n=2}^{∞} a_{n−1}x^{n−1} + 2x^{2} ∑_{n=2}^{∞} a_{n−2}x^{n−2} =

1 + x + x ∑_{n=1}^{∞} a_{n}x^{n} + 2x^{2} ∑_{n=0}^{∞} a_{n}x^{n} = 1 + x + x ∑_{n=0}^{∞} a_{n}x^{n} − x + 2x^{2} ∑_{n=0}^{∞} a_{n}x^{n} = 1 + xA + 2x^{2}A, durch

Auflösen nach A folgt A = \frac{1}{1 − x − 2x^{2}} . Das reflektierte Polynom des Nenners lautet x^{2} − x − 2,

es hat die Nullstellen β = −1 und γ = 2. Damit läßt sich A darstellen als \frac{1}{(1 + x)(1 − 2x)}.

Nun setzt man mit Partialbruchzerlegung an: \frac{1}{(1 + x)(1 − 2x)} = \frac{B}{1 + x} + \frac{C}{1 − 2x} ⇔ 1 =

(1 − 2x)B + (1 + x)C = B − 2xB + C + xC = (B + C) + x(C − 2B). Durch Koeffizientenvergleich erhält man B+C = 1∧C−2B = 0 ⇔ C = 1−B ∧1−3B = 0 ⇔ B = \frac{1}{3} ∧C = \frac{2}{3}. Analog zum Beispiel der Fibonacci-Folge aus der Vorlesung erhält man a_{n} = Bβ^{n}+Cγ^{n} = \frac{1}{3}(−1)^{n}+ \frac{2}{3} ·2^{n}.

Aufgabe L2 Um die gesuchten n zu finden, bestimmt man diejenigen Primzahlpotenzen, deren φ-Funktionswert ein Teiler von 6 ist: φ(p^{m}) = (p − 1)p^{m−1} = 1 ⇔ p = 2 ∧ m = 1, φ(p^{m}) = 2 ⇔ (p−1 = 2∧p^{m−1} = 1)∨(p−1 = 1∧p^{m−1} = 2) ⇔ (p = 3∧m = 1)∨(p = 2∧m = 2), φ(p^{m}) = 3 ⇔ (p − 1 = 3 ∧ p^{m−1} = 1) ∨ (p − 1 = 1 ∧ p^{m−1} = 3), dieses Gleichungssystem hat keine Lösung, φ(p^{m}) = 6 ⇔ (p − 1 = 6 ∧ p^{m−1} = 1) ∨ (p − 1 = 3 ∧ p^{m−1} = 2) ∨ (p − 1 = 2 ∧ p^{m−1} = 3) ∨ (p − 1 = 1 ∧ p^{m−1} = 6) ⇔ (p = 7 ∧ m = 1) ∨ (p = 3 ∧ m = 2), da die zweite und vierte Gleichung keine Lösungen haben. Damit erhält man zunächst direkt φ(7) = 6 und φ(9) = φ(3^{2}) = 6, aus der Darstellung 6 = 6 · 1 erhält man φ(14) = φ(7^{1}) · φ(2^{1}) = 6 · 1 = 6 und φ(18) = φ(3^{2} · 2) = φ(3^{2}) · φ(2^{1}) = 6 · 1 = 6, aus den Darstellungen 6 = 3 · 2 und 6 = 3 · 2 · 1 erhält man keine weitere Lösungen, da φ(p^{m}) für Primzahlpotenzen p^{m} niemals 3 werden kann, wie oben gezeigt wurde. Damit lauten die Zahlen n mit φ(n) = 6: 7, 9, 14, 18, die ungeraden Lösungen sind 7 und 9. Durch Ausprobieren erhält man ℤ_{7}^{∗} = {[1]_{7}; [2]_{7}; [3]_{7}; [4]_{7}; [5]_{7}; [6]_{7}} = ⟨[3]_{7}⟩ = ⟨[5]_{7}⟩ und ℤ_{9}^{∗} = {[1]_{9}; [2]_{9}; [4]_{9}; [5]_{9}; [7]_{9}; [8]_{9}} = ⟨[2]_{9}⟩ = ⟨[5]_{9}⟩ = ⟨[8]_{9}⟩, also sind beide primen Restklassengruppen zyklisch, alle erzeugenden Elemente sind bereits angegeben.