Antwort mit KI erzeugt
Lösung:
Die Aufgabe besteht darin, die Anzahl der Möglichkeiten zu berechnen, \( n \) Platzkarten auf \( r \) Studenten so zu verteilen, dass jeder Student mindestens eine Karte erhält. Dieses Problem lässt sich mit Hilfe der Inklusion-Exklusion-Prinzip (auch als Prinzip von Sylvester bekannt) lösen.
Zunächst betrachten wir die gesamte Menge von Verteilungen ohne die Bedingung, dass jeder Student mindestens eine Karte erhalten muss. Jede der \( n \) Karten kann an einen von \( r \) Studenten gehen, daher gibt es insgesamt \( r^n \) mögliche Verteilungen.
Nun müssen wir die Anzahl der Verteilungen korrigieren, bei denen mindestens einer der Studenten keine Karte erhält. Um dies zu tun, definieren wir für jeden Studenten \( i \) eine Menge \( M_i \), die alle Verteilungen enthält, bei denen der \( i \)-te Student keine Karte erhält.
Die Mächtigkeit von \( M_i \) berechnet sich, indem wir den \( i \)-ten Studenten aus der Verteilung herausnehmen, womit \( (r-1)^n \) Verteilungen möglich sind, da nun jede Karte an einen der verbleibenden \( r-1 \) Studenten gehen kann.
Die Anzahl der Verteilungen, bei denen mindestens ein Student keine Karte erhält, ist die Vereinigung der Mengen \( M_i \) für \( i = 1, 2, \ldots, r \). Nach dem Prinzip von Inklusion-Exklusion ist die Mächtigkeit dieser Vereinigung:
\(
\sum \limits_{k=1}^{r}(-1)^{k+1}\left(\sum \limits_{1 \leq i_1 < i_2 < \cdots < i_k \leq r}\left|\bigcap \limits_{j=1}^{k}M_{i_j}\right|\right)
\)
Bei der Schnittmenge von \( k \) Mengen \( M_{i_1}, M_{i_2}, \ldots, M_{i_k} \), in der genau \( k \) spezifische Studenten keine Karte erhalten, haben wir \( (r-k)^n \) Möglichkeiten, da nun jede der \( n \) Karten an einen der verbleibenden \( r-k \) Studenten verteilt werden kann. Es gibt \(\binom{r}{k}\) Möglichkeiten, \( k \) Studenten aus \( r \) zu wählen, die keine Karte erhalten. Daher ist die obige Summe:
\(
\sum \limits_{k=1}^{r}(-1)^{k+1}\binom{r}{k}(r-k)^n
\)
Wir fügen die Fälle hinzu, in denen kein Student leer ausgeht, was der Gesamtzahl der Verteilungen \( r^n \) entspricht, und subtrahieren die obige Summe, um die Anzahl der Verteilungen zu korrigieren, in denen kein Student leer ausgeht:
\(
r^{n} - \sum \limits_{k=1}^{r}(-1)^{k+1}\binom{r}{k}(r-k)^n
\)
Um dies als eine einzige Summe darzustellen, bemerken wir, dass der Term für \( k=0 \) einfach \( r^n \) ist, wenn wir die Konvention \(\binom{r}{0}=1\) anwenden. Somit können wir die Formel als
\(
\sum \limits_{k=0}^{r}(-1)^{k}\binom{r}{k}(r-k)^{n}
\)
schreiben, was die gewünschte Lösung ist.
