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

DIPLOMVORPRÜFUNG Mathematik II (Diskrete Strukturen)

Aufgabe 12: (9 Punkte)

Es sei p eine Primzahl, a ∈ ℕ und m = ∑_{i=0}^{p−2} a^{i}. Für welche a mit 1 ≤ a ≤ p ist p ein Teiler

von m ?

Aufgabe 13: (8 Punkte) Beweisen oder widerlegen Sie die folgenden Aussagen.

a) Liegt jede Ecke eines Turniers T_{n} der Ordnung n auf einem orientierten Kreis der Länge > \frac{n}{2}, dann hat T_{n} einen orientierten Hamiltonkreis.

b) Liegt jede Ecke eines Turniers T_{n} der Ordnung n auf einem orientierten Kreis der Länge ≥ \sqrt{2n}, dann ist T_{n} stark zusammenhängend.

Aufgabe 14: (8 Punkte) Es sei G ein schlichter, Eulerscher Graph und μ(G) sein Index.

a) Zeigen Sie, dass es eine Menge K′ ⊆ K(G) von \frac{Δ(G)}{2} verschiedenen Kanten gibt, so dass G \ K′ = (E(G), K(G) \ K′) zusammenhängend ist.

b) Ist es möglich, dass μ(G) < \frac{Δ(G)}{2} gilt? (Begründen Sie Ihre Antwort!)

c) Bestimmen Sie alle schlichten, Eulerschen Graphen G mit μ(G) = 1.

Aufgabe 15: (8 Punkte) Es seien k und n zwei natürliche Zahlen mit k ≤ n. Eine k-Zahlpartition der Zahl n ohne Wiederholung ist eine Darstellung von n als Summe von k paarweise verschiedenen natürlichen Zahlen. Wird die Anordnung der Summanden nicht berücksichtigt, so bezeichnen wir die Anzahl der verschiedenen k-Zahlpartitionen von n ohne Wiederholung mit w(n, k).

a) Bestimmen Sie w(n, 2) für n ≥ 2.

b) Bestimmen Sie (ohne Beweis) für festes gegebenes k ∈ ℕ alle n ≥ k mit w(n, k) = 1.

c) Es sei n = 2t^{2} + 2t − 2 mit t ∈ ℕ. Für welche t gilt w(n, 2t) ≥ 2 ? (Begründung mit b) oder direkt.)

Aufgabe 16: (8 Punkte) Die Folge (a_{n})_{n∈ℕ_{0}} sei rekursiv definiert durch a_{0} = 0, a_{1} = 2 und a_{n} = a_{n−1} + 2a_{n−2} für alle n ≥ 2. Bestimmen Sie mit Hilfe der erzeugenden Funktion die explizite Darstellung der Folgenglieder a_{n}.

Aufgabe 17: (9 Punkte)

a) Wieviele ungeordnete 3-Zahlpartitionen p(100, 3) gibt es?

b) Wieviele verschiedene natürliche Zahlen n ≥ 1 000 000 gibt es, die die gleichen Ziffern wie die Zahl 6 111 670 besitzen?

c) Es sei μ die Möbiussche μ-Funktion. Berechnen Sie ∑_{d/1092} 2(1 + μ(d)).