Fakultät für Mathematik 6. Mai 1998 Universität Regensburg

Übungen zur Vorlesung Einführung in die Wahrscheinlichkeitstheorie

Blatt 1: Kombinatorik

Aufgabe 1: (Einfache Urnenmodelle)

In einer Urne befinden sich m ≥ 1 paarweise verschiedene Kugeln, aus denen Stichproben bestehend aus je n ∈ {1, …, m} Kugeln gezogen werden. Geben Sie in den folgenden Fällen eine Menge an, die die möglichen Versuchsergebnisse beschreibt, und bestimmen Sie die Anzahl der möglichen Versuchsergebnisse.

a) Geordnete Stichproben mit Rücklegen.

b) Geordnete Stichproben ohne Rücklegen.

c) Ungeordnete Stichproben mit Rücklegen.

d) Ungeordnete Stichproben ohne Rücklegen.

Aufgabe 2: (Eigenschaften von Binomialkoeffizienten)

Seien m, n ∈ ℕ. Beweisen Sie die folgenden Formeln.

a) \binom{m}{n} = \binom{m}{m−n}

b) \binom{m}{n} = \binom{m−1}{n} + \binom{m−1}{n−1}

c) ∑_{n=0}^{m} \binom{m}{n} = 2^{m}

d) ∑_{n=0}^{m}(−1)^{n}\binom{m}{n} = 0 für m ≥ 1

e) ∑_{n=0}^{m} n \binom{m}{n} = m 2^{m−1}

Aufgabe 3: Seien k, ℓ, m, n ∈ ℕ mit k ≤ ℓ + m. Beweisen Sie die Formel

∑_{n=0}^{m} \binom{m}{n}\binom{ℓ}{k − n} = \binom{ℓ + m}{k}

Aufgabe 4: (Siebformel) Beweisen Sie Satz 1.10 der Vorlesung.

Sei M eine Menge, seien r, n ∈ ℕ_{+}, und seien N_{1}, …, N_{r} ⊆ M Teilmengen. Ferner sei eine Funktion f : 𝔓(M) ⟶ ℝ gegeben mit f(A ∪ B) = f(A) + f(B) für disjunkte Teilmengen A, B ∈ 𝔓(M). Schließlich sei

S_{n} = {x ∈ M | x ∈ N_{i} für genau n Indizes 1 ≤ i ≤ r}

Dann gilt

f(S_{n}) = ∑_{i=n}^{r}(−1)^{i−n}\binom{i}{n} ∑_{\{j_{1},...,j_{i}\}⊆\{1,...,r\} i−elementigeTeilmenge} f(N_{j_{1}} ∩ ⋯ ∩ N_{j_{i}})

Aufgabe 5: (Das 8-Damenproblem)

a) Wie viele Möglichkeiten gibt es, acht Türme so auf ein Schachbrett zu stellen, daß sich keine zwei gegenseitig bedrohen?

b) Schreiben Sie ein Maple-Programm Rooks(), das die Möglichkeiten in a) alle berechnet und ihre Summe ausgibt. Repräsentieren Sie dazu jedes Feld als Paar (i, j) mit 1 ≤ i, j ≤ 8 und jede Lösung von a) als array(1..8, 1..2). Die Summe ist komponentenweise zu bilden, und die Felder (i, j) jeder Lösung sind nach aufsteigendem i anzuordnen.

c) Schreiben Sie ein Maple-Programm Queens(), das alle Möglichkeiten berechnet und ausgibt, acht Damen so auf ein Schachbrett zu stellen, daß sich keine zwei gegenseitig bedrohen. Hinweise: Verwenden Sie a). Schreiben Sie erst ein Programm DiagCheck(F eld1, F eld2), das prüft, ob sich zwei Damen diagonal bedrohen. Letzteres ist genau dann der Fall, wenn F eld1 − F eld2 ein Vielfaches von (1, 1) oder (1, −1) ist.