Anzahl der Ereignisse mit allen Elementen der Grundmenge bei k mal Ziehen mit Zurücklegen mit Reihenfolge?

Question

Aufgabe:

Wie berechne ich bei k-maligem Ziehen aus einer n großen Grundmenge mit Zurücklegen mit Beachtung der Reihenfolge die Anzahl der Ereignisse, die alle n Elemente der Grundmenge mindestens einmal enthalten?

Ich weiß, dass die Anzahl möglicher Ereignisse bei k-maligem Ziehen aus einer n großen Grundmenge n^k ist und dass für k<n es logischerweise immer 0 ist und dass wenn k=n ist es einer Variation ohne Wiederholung also n! entspricht, aber wie berechnet man es verallgemeinert für jegliche n und k?

Und wie muss ich außerdem k in Abhängigkeit von n wählen, um mit einer Wahrscheinlichkeit von x (z. B. 90%) bei k-maligem Ziehen aus einer n großen Grundmenge bei Gleichverteilung alle n Elemente der Grundmenge zu ziehen?

Comments

Ich kenne das Problem gut, da ich mich schon zweimal damit beschäftigt habe, da 2 Abiturschüler darüber in der Mündlichen Prüfung einen Vortrag halten durften. Daher erstmal eine Bitte an dich wie ich auch die Abiturienten gebeten habe.

Beschäftige dich mit dem Sammelbilderproblem oder dem Problem der vollständigen Serie.

Dieses Problem findest du bei Wikipedia unter https://de.wikipedia.org/wiki/Sammelbilderproblem

In der Linkliste bei Wikipedia findest du auch Links zu sehr detaillierte Vorrechnungen. Allerdings würde ich grundsätzlich erstmal dazu raten das Problem zu versuchen selbst anzugehen. Z.B. mithilfe eines Würfels. Wie oft müsste ich einen Würfel werfen, damit alle Augenzahlen mit einer Wahrscheinlichkeit von z.B. 90% wenigstens einmal gefallen sind.

Es gibt durchaus mehrere Möglichkeiten dies zu lösen. Ich selber finde das Konzept der Markov-Kette recht gut. Aber das ist Geschmackssache.

---

Das Gegenereignis wäre "nur verschiedene n" = n!

-> n^n-n!

Ginge es nicht auch so?

---

Ginge es nicht auch so?

Leider nicht. Das wäre dann auch wohl zu einfach.

Was ist wenn bei einem Würfel 1, 1, 1, 1, 1, 2 geworfen wird. Man hat zwar keine keine Serie aber auch nicht alles verschiedene.

---

Wie müsste das Gegenereignis formulieren?

Dass jeweils ein Element nicht vorkommt???

---

Das Ereignis war ja es kommen alle n Elemente vor. das muss durchaus auch mehrfach sein wenn k > n ist.

Das Gegenteil wäre mind. eines der n Elemente kommt nicht vor.

Und du ahnst es schon, Es könnten halt auch mehrere Elemente nicht vorkommen.