Antworte auf:  Inklusions-Exklusions-Prinzip von WagW
Forum:  Inklusion-Exklusion, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3639
Herkunft: Raun
 Beitrag No.5, eingetragen 2019-11-11 05:56    [Diesen Beitrag zitieren]

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.





WagW
Aktiv
Dabei seit: 15.02.2018
Mitteilungen: 194
Herkunft:
 Beitrag No.4, eingetragen 2019-11-11 00:20    [Diesen Beitrag zitieren]

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: 3639
Herkunft: Raun
 Beitrag No.3, eingetragen 2019-11-10 21:24    [Diesen Beitrag zitieren]

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: 194
Herkunft:
 Beitrag No.2, eingetragen 2019-11-10 13:13    [Diesen Beitrag zitieren]

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: 3639
Herkunft: Raun
 Beitrag No.1, eingetragen 2019-11-10 07:57    [Diesen Beitrag zitieren]

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: 194
Herkunft:
 Themenstart: 2019-11-10 00:02    [Diesen Beitrag zitieren]

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


 
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]