Die Mathe-Redaktion - 06.12.2019 06:14 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 385 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
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: 139
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



  Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3373
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



  Profil  Quote  Link auf diesen Beitrag Link
WagW
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.02.2018
Mitteilungen: 139
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



  Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3373
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



  Profil  Quote  Link auf diesen Beitrag Link
WagW
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.02.2018
Mitteilungen: 139
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



  Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3373
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.






  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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]