n Gutscheine auf r Studenten verteilen

28.10.2010, 23:20

Zitrone21

n Gutscheine auf r Studenten verteilen

Hallo zusammen. Ich höre nun Stochastik in der zweiten Uniwoche und komme leider eher schlecht als recht mit dem Skript zurecht. (Es wird thematisch viel hin und her gesprungen, Notationen sind unklar und leider fehlt ein roter Faden in der Vorlesung ; Dies ist aber ein anderes Thema)

Die Aufgabe:
Es werden n Gutscheine zufällig an r Studenten (n $\begin{eqnarray*} \geq \end{eqnarray*}$ r) verteilt. Sehen Sie die Gutscheine als unterscheidbar an.

a) Zeigen Sie: Es gibt
$\begin{eqnarray*} \sum\limits_{k=0}^r (-1)^k * \begin{pmatrix} r \\ k \end{pmatrix} * (r - k)^n \end{eqnarray*}$
verschiedene Möglichkeiten, die Gutscheine zu verteilen, wenn jeder Student mindestens einen Gutschein bekommen soll.
b) Wie groß ist die Wahrscheinlichkeit unter der Gleichverteilungsannahme, dass nicht jeder Student einen Gutschein erhält?

Hinweis: Betrachen Sie die Mengen $\begin{eqnarray*} M_k \end{eqnarray*}$ = {Der k-te Student erhält keinen Gutschein.} und verwenden Sie das Ein- und Ausschlusprinzip der Kombinatorik.

Die Aussage vom Ein- und Ausschließungsprinzip habe ich verstanden. Dies hier steht als Definition im Heft. Ich denke, das ist Anzuwenden:
$\begin{eqnarray*} | \bigcup ^n_{i=1} A_i | = \sum\limits_{k=1}^n (-1)^{k+1} \sum\limits_{1 \leq i_1 < i_2 < ... < i_k \leq n} |A_{i_1} \cap A_{i_2} \cap ... A_{i_k} | \end{eqnarray*}$

Ich habe mir schon einige Ansätze überlegt, aber keinen davon könnte ich so begründen, dass er Sinn macht. Ich bin über jegliche Hilfe dankbar

29.10.2010, 00:36

René Gruber

Auf diesen Beitrag antworten »

Der Hinweis ist doch perfekt, wenn du dir mal über die inhaltliche Bedeutung der Vereinigung $\begin{eqnarray*} \bigcup\limits_{k=1}^r M_k \end{eqnarray*}$ Gedanken machst, d.h., was diese Vereinigung mit den Problemstellungen a) und b) zu tun hat.

29.10.2010, 08:17

Zitrone21

Auf diesen Beitrag antworten »

Wenn ich alle $\begin{eqnarray*} M_k \end{eqnarray*}$ vereinige, habe ich die Anzahl aller ungünstigen Kombinationen.

Ich könnte nun die Anzahl aller Kombinationen berechnen ( das müsste $\begin{eqnarray*} r^n \end{eqnarray*}$ sein ( Ziehen mit Zurücklegen unter Beachtung der Reihenfolge) und davon die Vereinigung der $\begin{eqnarray*} M_k \end{eqnarray*}$ abziehen. Wenn ich das aufschreibe, dann hänge ich aber genau an der Stelle wo ich das Ein- und Ausschlussprinzip verwenden muss, da ich ja keinen einzigen Wert für den Betrag von den einzelnen Mengen können. Welche Tricks muss ich denn da anwenden?

29.10.2010, 08:44

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Zitrone21
da ich ja keinen einzigen Wert für den Betrag von den einzelnen Mengen können

Hier fehlt wohl was im Teilsatz - aber ich kann mir denken, was du meinst.

Was kennzeichnet Gutscheinverteilungen, die in $\begin{eqnarray*} M_k \end{eqnarray*}$ liegen? Nach Festlegung erstmal, dass der $\begin{eqnarray*} k \end{eqnarray*}$ -te Student keinen Gutschein erhält - anders formuliert: Dass sämtliche $\begin{eqnarray*} n \end{eqnarray*}$ Gutscheine nur an die restlichen $\begin{eqnarray*} (r-1) \end{eqnarray*}$ Studenten verteilt werden, damit kann man die Mächtigkeit $\begin{eqnarray*} |M_k| \end{eqnarray*}$ berechnen.

Diese Überlegungen konsequent fortgesetzt kommt man auch auf die Mächtigkeiten der benötigten Durchschnitte diverser $\begin{eqnarray*} M_k \end{eqnarray*}$ .

29.10.2010, 12:02

Zitrone21_Gast

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber

Was kennzeichnet Gutscheinverteilungen, die in $\begin{eqnarray*} M_k \end{eqnarray*}$ liegen? Nach Festlegung erstmal, dass der $\begin{eqnarray*} k \end{eqnarray*}$ -te Student keinen Gutschein erhält - anders formuliert: Dass sämtliche $\begin{eqnarray*} n \end{eqnarray*}$ Gutscheine nur an die restlichen $\begin{eqnarray*} (r-1) \end{eqnarray*}$ Studenten verteilt werden, damit kann man die Mächtigkeit $\begin{eqnarray*} |M_k| \end{eqnarray*}$ berechnen.

Das bedeutet ja quasi, das die Anzahl der Elemente in $\begin{eqnarray*} M_k \end{eqnarray*}$ für alle k gleich sein müssen, da sich ja quasi nur die Position von k verändert. Disjunkt sind die $\begin{eqnarray*} M_k \end{eqnarray*}$ jedoch nicht, da z.b. für k = 1 die Kombination besteht, das der erste und der zweite Student keine Karte bekommt, bei k = 2 ich jedoch auch konstrurieren kann, das der erste und zweite keine Karte bekommt.

Wenn ich $\begin{eqnarray*} n \end{eqnarray*}$ Gutscheine auf $\begin{eqnarray*} (r-1) \end{eqnarray*}$ Studenten verteilen will, dann wähle ich das kombinatorische Modell Ziehen mit Zurücklegen unter Berücksichtigung der Reihenfolge, da die Karten ja unterscheidbar seien sollen. Dies entspricht: $\begin{eqnarray*} (r-1)^n \end{eqnarray*}$ (Ich zeihe $\begin{eqnarray*} n \end{eqnarray*}$ -mal aus $\begin{eqnarray*} (r-1) \end{eqnarray*}$ Studenten, auf die ich die Karten verteilen will

Zitat:

Diese Überlegungen konsequent fortgesetzt kommt man auch auf die Mächtigkeiten der benötigten Durchschnitte diverser $\begin{eqnarray*} M_k \end{eqnarray*}$ .

Bewege ich mich mit meinen Gedanken überhaupt in die richtige Richtung? Wüsste nach meinen Überlegungen nun nicht weiterzumachen

29.10.2010, 13:21

René Gruber

Auf diesen Beitrag antworten »

Bisher alles richtig, vielleicht helfen dir noch ein paar Anfangsgedanken zum Durchschnitt zweier solcher Mengen auf die Sprünge:

$\begin{eqnarray*} M_k\cap M_l \end{eqnarray*}$ enthält nun die Gutscheinverteilungen, wo weder Student $\begin{eqnarray*} k \end{eqnarray*}$ noch Student $\begin{eqnarray*} l \end{eqnarray*}$ einen Gutschein erhält. Im Fall $\begin{eqnarray*} k\neq l \end{eqnarray*}$ werden alle $\begin{eqnarray*} n \end{eqnarray*}$ Gutscheine also an nur noch $\begin{eqnarray*} (r-2) \end{eqnarray*}$ Studenten verteilt, d.h. $\begin{eqnarray*} |M_k\cap M_l| = (r-2)^n \end{eqnarray*}$ .

Wie das dann beim Durchschnitt von drei oder mehr $\begin{eqnarray*} M_k \end{eqnarray*}$ weitergeht, kannst du dir sicherlich jetzt denken.

29.10.2010, 20:24

Zitrone21

Auf diesen Beitrag antworten »

Alles klar, vielen Dank dir

Neue Frage »

Antworten »

n Gutscheine auf r Studenten verteilen

Verwandte Themen