Wahrscheinlichkeitsrechnung - Auswahl einer Teilmultimenge

Aufrufe: 675     Aktiv: 22.01.2021 um 15:12
0

Anmerkung: Habe die Frage bereits gestellt, leider konnten mir potentielle HelferInnen durch eine eher unpräzise Fragestellung nicht wirklich helfen

Ich habe folgendes Problem, das ich eigentlich bereits schon mal gelöst habe, nur leider mittlerweile vergessen habe, wie es zu lösen ist.

Problem:

In einem Regal stehen 32 Bücher, wie viele Möglichkeiten gibt es genau 7 auszuwählen, wobei zwischen zwei ausgewählten immer mindestens ein Buch stehen bleiben muss. [EDIT: Wieviele Möglichkeiten gibt es, aus einem 32- bändigen Lexikon genau 7 Bücher auszuwählen, wobei zwischen zwei ausgewählten Bänden immer mindestens einer im Regal stehen bleiben soll?]

Idee

Es muss auf jeden Fall die Formel ((n + k - 1)! / (k)! * (n-k)!) zum Einsatz kommen (Auswahl einer Teilmultimenge - Kombination mit Wiederholung) Im Buch steht hierbei beispielsweise ein Beispiel: wie viele Möglichkeiten gibt es die Zahl 7 mit 4 Summanden darzustellen => Lösung:=> (k = Zahl, n = Summanden)=> ((7 + 4 - 1) / (7)! (4 - 1)!) = 120 Möglichkeiten - Analog dazu müsste es so funktionieren: B1 TRENNUNG B2 .... B32 (B = Buch) => also gibt es insgesamt eine Trennung weniger als Bücher => Es gibt 16 frei zu wählende Bücher und 15 Trennbücher => also könnte man aus den 16 wählen (also k, gleich der Zahl 7) und Positionen auf die, die 16 dargestellt werden gibt es 7 (=n)

Also müsste es (7 + 16 - 1)!/((16)!(7-1)!) sein = 74 613 Möglichkeiten, ich bin mir aber relativ sicher, dass dieser Ansatz falsch ist

Ich hoffe ihr könnte mir helfen, bin schon langsam wirklich am verzweifeln - vielen Dank :)

Diese Frage melden (1)
gefragt

Auszubildender, Punkte: 148

 
Kommentar schreiben
2 Antworten
0

Setze \(F(n,k)\) für die Anzahl der Möglichkeiten, aus \(n\) Gegenständen \(k\) wie gefordert auszuwählen. Dann gilt $$F(n,1)=n,\qquad F(n,k)=\sum_{i=2}^{n-2k+3}F(n-i,k-1),\ k>1$$ Die zweite Formel kommt wie folgt zustande: Sei \(i-1\) die Position des ersten ausgewählten Buches. Dann berechnen sich die Möglichkeiten für alle anderen Bücher mit \(F(n-i,k-1)\). Das kleinste mögliche \(i\) ist \(2\). Wäre \(i>n-2k+3\), müsste man danach \(k-1\) Bücher aus weniger als \(2k-3\) Büchern auswählen, das kann nicht funktionieren. So ergeben sich die Grenzen der Summe.

Der Computer gibt mir \(F(32,7)=657800\), wie auch pipifax in seinem Kommentar geschrieben hat. Ohne Computer wäre das sehr mühsam auszurechnen, ich weiß aber nicht, ob es eine einfachere Form gibt.

Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Was mich nur ärgert, ich habe es glaub ich schon einmal gelöst per Hand - nur leider wieder vergessen (bzw. schlauerweise so viel schon gelöst und mir vorgenommen, noch einmal alles durchzugehen - und die alten Sachen deswegen weggeworfen), aber vielleicht war die Lösung falsch :)   ─   infomarvin 22.01.2021 um 12:08
Ich habe doch noch eine geschlossene Form gefunden :) Man kann per Induktion zeigen, dass \(F(n,k)=\binom{n-k+1}{k}\) gilt. Vielleicht gibt es auch ein kombinatorisches Argument, wie man auf diese Formel kommt.   ─   stal 22.01.2021 um 14:41

Kommentar schreiben