Anordnen von Objekten mit vorgegebener Mindestanzahl?
Hallo zusammen,
ich habe eine Frage zu folgenden Aufgaben:
Lukas kauf Fleisch für einen Grillabend. Die Metzgerei bietet Schweine-, Rinder- und Lammsteaks an. Lukas möchte 12 Steaks kaufen. Bestimmen Sie die Anzahl der Möglichkeiten, wenn Lukas
a) Steaks von zwei verschiedenen Fleischsorten kaufen möchte und dabei von jeder mindestens 3 Stück
b) von jeder der 3 Fleischsorten jeweils mindestens 3 Steaks kaufen möchte.
Mein Ansatz:
a)
Lukas kann aus 3 Sorten 2 wählen. Es gibt also erstmal Möglichkeiten die Fleischsorten zu wählen. Soweit kein Problem.
Nun kann er aus den Fleischsorten A und B auswählen
(3A/9B); (4A/8B); (5A/7B); (6A/6B); (7A/6B); (8A/6B); (9A/3B)
Das sind 7 Möglichkeiten, die ich zwar so durch überlegen zusammenbekomme. Wie kann ich diese jedoch rechnerisch bestimmen?
Insgesamt müssten es ja dann 7 * 3 = 21Möglichkeiten sein.
b)
Gleicher Ansatz wie bei A, jedoch wird es hier schon sehr mühsam alles aufzuschreiben. Wenn die Bedingung mindestens 3 Fleischsorten nicht wäre, könnte man einfach 3^12 machen, jedoch ist die Bedingung mindestens mein Problem.
Danke für Eure Antworten!
1 Antwort
3^12 würde auch nicht gehen, wenn Anzahlen 0 erlaubt wären - die Reihenfolge der Fleischsorten ist ja egal.
Um bei 0 anzufangen, kann man erst mal 3 Stück von jeder Fleischsorte kaufen und sich dann um die Variationen kümmern. Dann hätte man noch 12 - 3 * 3 Steaks frei wählbar.
Das Problem ist verwandt mit "Partitionen" (meine Recherche führt u. A. auf https://de.wikipedia.org/wiki/Stirling-Zahl#Stirling-Zahlen_zweiter_Art) und mit Multinomialkoeffizienten, aber beides passt nicht so richtig.
-----
Wir können die Anzahlfunktion rekursiv definieren:
f(k; n) sei die Anzahl der Möglichkeiten, n Elemente auf k Sorten/Kisten/... aufzuteilen (jeweilige Mindestanzahl 0).
(Hier hätten wir dann f(3; 12 - 3 * 3) = f(3; 3))
-----
Für die Rekursion:
Wenn wir für die erste Sorte/Kiste genau j Elemente nehmen (0 <= j <= n), bleibt für den Rest
f(k-1; n-j)
Insgesamt also
f(k; n) = Summe {j von 0 bis n} f(k-1; n-j)
-----
Damit die Rekursion nicht unendlich "tief" wird, brauchen wir ein Rekursionsende.
Ein Rekursionsende ist bei n = 0 erreicht - dann müssen alle Kisten leer bleiben und wir haben offensichtlich genau eine Möglichkeit:
f(k; 0) = 1 (für alle k > 0)
In diesem Fall gilt das auch für k = 0:
f(0; 0) = 1
Aber für n > 0 ist
f(0; n)
nicht definiert; damit haben wir für k = 1, n > 0 genau eine Möglichkeit: alle n Elemente in die erste/einzige Kiste / aus der ersten/einzigen Sorte, also
f(1; n) = 1 für n > 0
-----
Wenn man ein paar Dutzend Funktionswerte aufschreibt oder etwas herumrechnet, kommt man vielleicht auch auf eine Formel, die Multinomialkoeffizienten o. Ä. verwendet.
Hab das mal gemacht - es kommt was überraschend Einfaches raus.
f(k; n) = Binomialkoeffizient(n+k-1; n)
(Anfänge - f(k; 0) und f(0; n) - wie oben)