Zeigen Sie, dass die Anzahl der Partitionen

Question

Aufgabe:

Sei S(n, m) die Anzahl der Partitionen einer n-elementigen Menge in m nichtleere
Teilmengen. Zeigen Sie, dass
S(n + 1, m + 1) = S(n, m) + (m + 1) · S(n, m + 1)
für alle n, m ≥ 0.

Problem/Ansatz:

Hey, hat jemand eine Idee, wie man das zeigen kann. Ich stehe leider völlig auf dem Schlauch bei der Aufgabe.

Answer 1

Gesucht ist die Anzahl der (m+1)-Partitionen der Menge \(B:=\{1,2,...,n,n+1\}\). Wir erhalten alle diese Partitionen aus Partitionen von \(A:=\{1,2,...,n\}\). Und zwar auf folgenden Wegen:

1. Für jede m-Partition \(\{A_1, ...,A_m\}\) von A erhalte die (m+1)-Partition\(\{\{n+1\},A_1,...,A_m\}\) von B. Das liefert S(n,m) Partitionen.

2. Für jede (m+1)-Partition \(\{A_1, ...,A_k, ...A_{m+1}\}\) von A bilde die (m+1)-Partition

$$\{A_1, ...,A_k \cup \{n+1\}, ...A_{m+1}\}$$

von B - d.h. man wählt eine der Mengen aus und ergänzt sie durch das Element \(n+1\). Man hat (m+1) Möglichkeiten, k zu wählen, insgesamt also \((m+1)S(n,m+1)\)

Gruß Mathhilf