Forum:  Inklusion-Exklusion
Thema: Inklusions-Exklusions-Prinzip
Themen-Übersicht
WagW
Aktiv
Dabei seit: 15.02.2018
Mitteilungen: 161
Aus:
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: 3616
Aus: 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: 161
Aus:
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: 3616
Aus: 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: 161
Aus:
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: 3616
Aus: 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.







Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=244297=7020
Druckdatum: 2020-08-06 11:20