Lehrstuhl II für Mathematik Aachen, den 20.09.2000 der RWTH Aachen Prof. Dr. L. Volkmann

DIPLOMVORPRÜFUNG

Mathematik II (Diskrete Strukturen)

Aufgabe 15: (7 Punkte) Es sei n ≥ 3 eine natürliche Zahl. Bestimmen Sie alle t ∈ ℕ mit 1 ≤ t ≤ n, die folgende Kongruenz erfüllen:

(2^{t} − 1)^{2} ≡ 1 (mod 2^{n}).

Aufgabe 16: (8 Punkte) Es sei G ein schlichter und zusammenhängender Graph der Ordnung n(G) ≥ 3. Zeigen Sie: Gilt dm(G) = r(G), so besitzt G keine Brücke.

Aufgabe 17: (9 Punkte) Es sei G ein schlichter Graph der Ordnung n(G) ≥ 4 mit Maximal-

grad Δ(G) ≤ \frac{n(G)}{2}, und es sei M ein perfektes Matching von G mit d(x, G) + d(y, G) ≤ n(G) − 2 für jede Kante xy ∈ M. Zeigen Sie, daß der Komplementärgraph Ḡ Hamiltonsch ist.

Aufgabe 18: (8 Punkte) Es sei φ die Eulersche φ-Funktion.

a) Bestimmen Sie φ(2000).

b) Bestimmen Sie diejenige ganze Zahl x mit 0 ≤ x ≤ 1999, die folgende Kongruenz erfüllt:

(123)^{802} ≡ x (mod 2000).

Aufgabe 19: (9 Punkte) Die Folge (a_{n})_{n∈ℕ_{0}} sei rekursiv definiert durch a_{0} = 0, a_{1} = 1 und a_{n} = 2a_{n−1} − a_{n−2} + 2 für alle n ≥ 2. Bestimmen Sie mit Hilfe der erzeugenden Funktion die explizite Darstellung der a_{n}. Hinweis: Benutzen Sie die Reihendarstellungen aus den Beispielen 6.1 a) und 6.1 d).

Aufgabe 20: (9 Punkte) Bestimmen Sie für n ≥ 4 die Anzahl F (n, n − 3) der Permutationen aus S_{n} mit mindestens n − 3 Fixpunkten.

Gibt es mehr oder weniger als 2 ( \begin{matrix}n + 1 \\ 3 \end{matrix} ) solcher Permutationen?