| Themen-Übersicht |
WagW
Aktiv
Dabei seit: 15.02.2018
Mitteilungen: 247
 |  Themenstart: 2019-11-10 00:02
Hallo zusammen,
folgende Aufgabe:
Wir haben $n$-viele unterschiedliche Fächer und $k$-viele unterschiedliche Kugeln. Es müssen $m$-viele Fächer leer bleiben. Wie viele Möglichkeiten gibt es die Fächern mit den $k$-vielen Kugeln zu füllen?
Mein Ansatz ist:
Ich schaue zunächst wieviele Möglichkeiten es gibt $n-m$ bzw. $m$ viele Fächer auszuwählen: ${n\choose m}$. Dann schaue ich wie viele Möglichkeite es gibt die $n-m$ zu befüllenden Fächer so zu befüllen, dass mindestens $1$ Fach leer bleibt, mindestens $2$ Fächer leer bleiben, ..., mindestens $n-m$ Fächer leer bleiben. Unter Verwendeung des Inklusion-Exklusion Prinzips komme ich auf:
$$\sum_{q=0}^{n-m} {n-m\choose q} (-1)^q(n-m-q)^k.$$
Wenn ich nun die $n-m$ vielen Fächer einfach so befüllen würde, ohne das irgendwelche Restriktionen gelten würden, hätte ich $(n-m)^k$ Möglichkeiten. Von diesen muss ich ja jetzt alle Möglichkeiten abziehen, die leere Fächer enthalten. Meine Lösung wäre also:
$$(n-m)^k-{n\choose m} \sum_{q=0}^{n-m} {n-m\choose q} (-1)^q(n-m-q)^k.$$
Ist das korrekt?
viele Grüße
WagW
|
StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3748
Herkunft: Raun
| Beitrag No.1, eingetragen 2019-11-10 07:57
Hallo WagW,
beim Prinzip_von_Inklusion_und_Exklusion#Anwendung beginnt die Summe mit \(q=1\) und im Exponent des Faktors \(-1\) steht \(q+1\).
Viele Grüße,
Stefan
|
WagW
Aktiv
Dabei seit: 15.02.2018
Mitteilungen: 247
| Beitrag No.2, vom Themenstarter, eingetragen 2019-11-10 13:13
Hallo Stefan,
danke fürs drüber schauen.
Da bin ich mit dem Index und dem Faktor ${n\choose m}$ etwas durcheinander gekommen - hier noch mal neu:
$$
{n\choose m}\left((n-m)^k-\sum_{q=1}^{n-m} {n-m\choose q} (-1)^{q+1}(n-m-q)^k \right)= \\ {n\choose m}\sum_{q=0}^{n-m} {n-m\choose q} (-1)^{q+2}(n-m-q)^k.
$$
Bzw. hier kann ich anstatt des Exponenten $q+2$ ja auch einfach $q$ schreiben.
Stimmt das nun so?
viele Grüße
WagW
|
StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3748
Herkunft: Raun
| Beitrag No.3, eingetragen 2019-11-10 21:24
Der Vorfaktor \(\binom{n}{m}\) ist klar und im verbleibenden Rest ersetze ich zur besseren Übersicht \(n-m\) durch \(n\)
\(\displaystyle\sum_{q=0}^{n} \binom{n}{q} (-1)^q (n-q)^k\)
und WoframAlpha: sum(binom(n,q)*(-1)^q*(n-q)^k) for q=0 to n bietet hierfür als Ergebnis
\(n! S_{k;n}\)
mit den Stirling-Zahlen zweiter Art \(S_{k;n}\) und in diesem Link steht auch (mit umgedrehten Bezeichnungen) die Anzahl der Möglichkeiten, \(k\) unterscheidbare Bälle auf \(n\) unterscheidbare Fächer aufzuteilen.
|
WagW
Aktiv
Dabei seit: 15.02.2018
Mitteilungen: 247
| Beitrag No.4, vom Themenstarter, eingetragen 2019-11-11 00:20
Finde ich jetzt mnemonisch eher verwirrend wenn Du $m-n$ plötzlich durch $n$ ersetzen willst, da $n$ vorher ja schon eine eigene Bedeutung hatte.
viele Grüße
WagW
|
StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3748
Herkunft: Raun
| Beitrag No.5, eingetragen 2019-11-11 05:56
Ohne die Ersetzung ist vielleicht nicht so leicht zu sehen, dass es sich bei der Summe um die Stirlingzahlen handelt, wenn man sie auswendig kennt. Doch WolframAlpha schafft das auch:
binom(n,m)*sum(binom(n-m,q)*(-1)^q*(n-m-q)^k) for q=0 to n-m
mit dem Ergebnis
\(\binom{n}{m}(n-m)! S_{k;n-m}\).
Das Ersetzen war zur Lösungsfindung gedacht. Beim fertig Aufschreiben kann man das weglassen oder doppelte Bezeichnung vermeiden.
|
