Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Inklusion-Exklusion » Inklusions-Exklusions-Prinzip
Druckversion
Druckversion
Autor
Universität/Hochschule J Inklusions-Exklusions-Prinzip
WagW
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.02.2018
Mitteilungen: 161
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-11-10


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3616
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-11-10


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
WagW
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.02.2018
Mitteilungen: 161
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-11-10


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3616
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-11-10


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
WagW
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.02.2018
Mitteilungen: 161
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-11-11


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3616
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-11-11


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.






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
WagW hat die Antworten auf ihre/seine Frage gesehen.
WagW hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]