Anzahl der Möglichkeiten in Mengen

Question

Aufgabe:

… Sei Sn,k die Anzahl der Möglichkeiten, eine n-elementige Menge in
k nicht-leere Teilmengen aufzuteilen, also z.B. S3,2 = 3, da {1, 2, 3} als {1, 2} ∪ {3},
{1, 3} ∪ {2} oder {2, 3} ∪ {1} geschrieben werden kann. Stellen Sie in Analogie zur
Rekursionsformel für Binomialkoeffizienten eine Rekursionsformel für Sn,k auf, und
geben Sie eine geschlossene Formel für Sn,3 an.

Answer 1

Hallo,

nimm an die Grundmenge sei \(X:=\{1, \ldots,n\}\) bzw \(Y:=\{1, \ldots,n+1\}\)

Sei \(\{A_1, \ldots A_k\}\) eine Zerlegung von Y, also eine Zerlegung, die für S(n+1,k) zählt. Dann muss in einer dieser Mengen n+1 enthalten sein, sagen wir in \(A_j\). Dann ist \(\{A_1, \ldots,A_j \setminus\{n+1\}, \ldots,A_k\}\) eine Zerlegung von X. Also kann ich auf diesem Weg aus jeder k-Zerlegung für Y eine k-Zerlegung für X gewinnen.

Du musst jetzt noch überlegen:

1. Jeweils k k-Zerlegungen von Y liefern dieselbe k-Zerlegung für X.

2. Was ist mit dem Sonderfall, dass \(A_j=\{n+1\}\), also nach dem Streichen nur die leere Menge übrig bleibt.

Gruß Mathhilf