Zeigen Sie, dass für n ≥ k 0 die Gleichung gilt?

Question

Sei \( S_{n, k} \) die Anzahl der Möglichkeiten, eine \( n \)-elementige Menge in \( k \) nichtleere Teilmengen zu1 zerlegen, also die Anzahl der \( k \)-Tupel \( \left(A_{1}, \ldots, A_{k}\right) \) so dass \( \bigcup_{i=1}^{k} A_{i}=\{1, \ldots, n\} \), für alle \( i \) gilt, dass \( A_{i} \neq \emptyset \), und für alle \( i \neq j \) gilt, dass \( A_{i} \cap A_{j}=\emptyset \). Zeigen Sie, dass für \( n \geq k>0 \) die Gleichung
\( S_{n, k}=\sum \limits_{i=0}^{k}(-1)^{k-i}\left(\begin{array}{l} k \\ i \end{array}\right) i^{n} \)
gilt. Überlegen Sie sich dazu zunächst, dass die entsprechende Anzahl ohne die Bedingung \( A_{i} \neq \emptyset \) einfach \( k^{n} \) ist, und benutzen Sie dann Inklusion-Exklusion.

Comments

Hast Du Dir die Sache mit dem k^n schon überlegt (letzter Satz)?

---

ja, schon. Aber ich komme nicht weiter.

Answer 1

Wir bezeichnen mit \(B_i\) die Tupel \((A_1, \ldots,A_k)\), wobei \(A_i=\emptyset\), ansonsten wie in der Aufgabe verlangt eine disjunkte Zerlegung von 1..n. Dann wollen wir von allen Tupeln - Gesamtzahl \(k^n\) - die Vereinigung \(\cup_{i=1}^nB_i\) ausschließen. Diese zählen wir durch I-E ab.Für die I-E-Formel benötigen wir:

$$\left| \cap\{B_j \mid j \in N \setminus I\}\right|, \quad N:=\{1, \ldots k\}, I \subset K$$

Das sind alle Tupel, bei denen nur die\(A_i\) mit \(i \in I\) "verwendet" werden, ihre Anzahl ist \(|I|^n\) (analog zu der Gesamtzahl \(k^n\)). Die Anzahl der Teilmengen \(I\) mit festem \(|I|\) ist natürlich \(\binom{k}{|i|]}\)

Comments

Vielen Dank <3