UNIVERSITÄT DES SAARLANDES FACHRICHTUNG 6.1 – MATHEMATIK Prof. Dr. Jörg Eschmeier Dipl.-Math. Michael Wernet �

Übungen zur Vorlesung Mathematik für Informatiker I

Wintersemester 2011/2012

Blatt 2 Abgabetermin: Freitag, 04.11.2011

Aufgabe 5 (1+2+2=5 Punkte)

Seien n, k, r, s ∈ ℕ natürliche Zahlen. Zeigen Sie:

(i) \binom{n}{k + 1} = \binom{n}{k}\frac{n − k}{k + 1} .
(ii) ∑_{k=0}^{n} k\binom{n}{k} = n2^{n−1}.
(iii) \binom{r + s}{n} = ∑_{k=0}^{n} \binom{r}{k}\binom{s}{n − k}.

Aufgabe 6 (2+2=4 Punkte)

Seien M, N endliche Mengen. Wieviele injektive Abbildungen von M nach N gibt es? Wieviele surjektive Abbildungen von M nach N gibt es, wenn N zwei, drei oder vier Elemente hat?

Aufgabe 7 (2+2+2=6 Punkte)

Gegeben seien eine Abbildung f : M → N und Teilmengen A, B ⊂ M, C, D ⊂ N. Zeigen Sie:

(a)

f(A ∪ B) = f(A) ∪ f(B).

(b)

f^{−1} (C ∪ D) = f^{−1} (C)∪ f^{−1} (D).

(c) Bleiben die Aussagen richtig, wenn man überall ”∪”durch ”∩”ersetzt?

Aufgabe 8 (1+1+1+1=4 Punkte)

Seien f : X → Y und g : Y → Z Abbildungen. Man beweise oder widerlege durch ein Gegenbeispiel:

(a) Ist g ∘ f injektiv, so ist f injektiv.

(b) Ist g ∘ f injektiv, so ist g injektiv.

(c) Ist g ∘ f surjektiv und ist g injektiv, so sind g und f surjektiv.

(d) Ist g ∘ f surjektiv, so ist auch f surjektiv.

(bitte wenden)

Hinweis:

Bitte geben Sie Ihre Lösungen zu den Übungsblättern vor der Vorlesung ab. Die Abgabe erfolgt in die Briefkästen im Untergeschoss von Gebäude E2 5 vor dem Zeichensaal in das Fach ihres jeweiligen Übungsgruppenleiters. Sie können (und sollen) in Gruppen von bis zu 3 Personen abgeben. Diese sollten zusammen mit Ihnen in einer Übungsgruppe sein. Um zu den Klausuren zugelassen zu werden, müssen Sie mindestens 50% der Gesamtpunkte aller Übungen erzielen, sowie regelmäßig und aktiv an den Übungen teilnehmen. Wenn Sie sich noch nicht für die Übungen angemeldet haben oder bei sonstigen Fragen oder Problemen bezüglich der Übungen wenden Sie sich bitte an Karin Mißler (Zimmer 4.18, Email: missler@math.uni-sb.de) oder Michael Wernet (Zimmer 4.15, Email: wernet@math.uni-sb.de).

Die Übungsblätter finden Sie auch auf unserer Homepage:

http://www.math.uni-sb.de/ag/eschmeier/lehre