Induktives Definieren, TU Dortmund

Question

Aufgabe:

1. Geben Sie eine induktive Definition für die Anzahl der Partitionen einer n-elementigen Menge
mit genau k Partitionsklassen an (1 ≤ k ≤ n). Erklären Sie Ihre Definition (ohne formalen
Beweis).
2. Bestimmen Sie die Anzahl aller Partitionen für eine 5-elementige Menge. Erläutern Sie Ihr
Vorgehen.

Problem/Ansatz:

Hallo, wie löse ich am besten diese Aufgabe? Vielen Dank im voraus.

Answer 1

Aloha :)

Ich hoffe, dass ich die Aufgabe richtig verstanden habe...

zu 1) Gegeben ist eine n-elementige Menge. Die Anzahl $\binom{n}{k}$ ihrer k-elementigen Teilmengen (Partitionsklassen) definieren wir wie folgt:$$\binom{n+1}{k}\coloneqq\binom{n}{k}+\binom{n}{k-1}\quad;\quad\binom{n}{0}\coloneqq1\quad;\quad\binom{n}{n}\coloneqq1\quad;\quad 1\le k\le n$$Erläuterung:

a) Aus n Elementen gibt es genau eine Möglichkeit, kein Element auszuwählen, nämlich die leere Menge. Daher wurde $\binom{n}{0}\coloneqq1$ definiert.

b) Aus n Elementen gibt es genau eine Möglichkeit, alle Elemente auszuwählen, nämlich die ganze Menge. Daher wurde $\binom{n}{n}\coloneqq1$ definiert.

c) Wird eine n-elementige Menge um ein neues Element erweitert und möchte man dort k Elemente auswählen, müssen wir genau zwei Fälle unterscheiden. (a) Das neue Element wird nicht ausgewählt, dann müssen alle k Elemente aus den n alten Elementen ausgewählt werden. Dafür gibt es $\binom{n}{k}$ Möglichkeiten. (b) Das neue Element wird ausgewählt, dann müssen aus den n alten Elementen nur noch (k-1) ausgewählt werden. Dafür gibt es $\binom{n}{k-1}$ Möglichkeiten. Daher die Definition von oben.

zu 2) Wir überlegen uns zuerst eine wichtige Rechenregel:$$\binom{n}{k}=\binom{n}{n-k}$$Wir können k Elemente aus n markieren und diese herausnehmen. Wir können aber auch k Elemente aus n markieren, diese liegenlassen und stattdessen die (n-k) anderen herausnehmen. Die Anzahl der Möglichkeiten ist in beiden Fällen dieselbe.

Für den Fall n=5 brauchen wir ein paar Vorbereitungen:$$\binom{2}{1}=\binom{1}{1}+\binom{1}{0}=1+1=2$$$$\binom{3}{1}=\binom{2}{1}+\binom{2}{0}=2+1=3\;;\;\binom{3}{2}=\binom{3}{1}=3$$$$\binom{4}{1}=\binom{3}{1}+\binom{3}{0}=3+1=4\;;\;\binom{4}{2}=\binom{3}{2}+\binom{3}{1}=6\;;\;\binom{4}{3}=\binom{4}{1}=4$$Damit sind wir am Ziel:

$$\binom{5}{1}=\binom{4}{1}+\binom{4}{0}=4+1=5$$$$\binom{5}{2}=\binom{4}{2}+\binom{4}{1}=6+4=10$$$$\binom{5}{3}=\binom{5}{2}=10$$$$\binom{5}{4}=\binom{5}{1}=5$$$$\binom{5}{5}=1$$