Kombinatorik?
Aus vier Obstsorten (Äpfel, Birne, Kiwi, Nektarine) soll ein Obstkorb zusammengestellt werden, der insgesamt 12 Obstteile und mindestens zwei Äpfel und eine Nektarine enthält.
Wie viele Möglichkeiten der Zusammenstellung des Obstkorbes gibt es? Begründen Sie Ihr Ergebnis.
4 Antworten
Zunächst: Jede Lösung enthält mindestens 2 Äpfel und mindestens 1 Nektarine. Wir erhalten also dieselbe Anzahl von Lösungen, wenn wir von jeder Lösung 2 Äpfel und 1 Nektarine entfernen.
Die modifizierte Aufgabenstellung lautet: "... der insgesamt 9 Obstteile enthält".
Da es auf die Reihenfolge nicht ankommen soll, reicht es nicht, 4^9 zu berechnen.
Wir füllen die Plätze von unten in der angegebenen Reihenfolge (Apfel, Birne, Kiwi, Nektarine).
Fangen wir an mit 9 Äpfeln, das ist 1 Möglichkeit.
Dann folgen 8 Äpfel, und 1 Stelle mit einer der anderen Früchte. Das sind 3 Möglichkeiten.
Dann 7 Äpfel, und 2 Stellen mit einer Auswahl aus 3 Früchten. Wir können alle beide mit Birnen füllen - 1 Möglichkeit -, 1 Stelle mit Birne und 1 Stelle mit 1 der zwei verbleibenden Sorten, 0 Stellen mit Birnen und 2 Stellen mit einer Auswahl aus 2 Sorten.
Etc.
Entweder probierst du alle diese Möglichkeiten aus oder du suchst eine Funktion, die diese Zahlen beschreibt. Das Problem ist verwandt mit der Einteilung einer Menge in Partiionen, aber wir erlauben maximal 4 Partitionen, und es kommt auf die Reihenfolge an, also bräuchten wir eine modifizierte Version hiervon - die ich aber nicht gefunden habe.
Also überlegen wir:
Wir wollen 9 Plätze mit 4 Sorten füllen.
Für die erste Sorte, Äpfel, können wir 0 bis 9 Plätze belegen. Da es hier auf die Reihenfolge nicht ankommt, haben wir für diese Plätze nur 1 Möglichkeit; mehrere Möglichkeiten gibt es höchstens, wenn wir die übrigen Plätze mit den übrigen 3 Sorten belegen.
Also:
f(9,4) = f(9,3) + f(8,3) + f(7,3) + ... + f(0,3)
allgemeiner für p Plätze und s Sorten:
f(p,s) = f(p,s-1) + f(p-1,s-1) + f(p-2,s-1) + ... + f(0,s-1)
Um 0 Plätze mit egal wie vielen Sorten zu belegen, haben wir immer genau 1 Möglichkeit:
f(0,s) = 1
Um mindestens einen Platz mit 0 Sorten zu belegen, haben wir keine Möglichkeit:
f(p,0) = 0, falls p > 0
Die ersten Funktionswerte kannst du in eine Tabelle eintragen. Entweder gehst du jetzt bis f(9,4) von Hand hoch oder du schaust schon vorher nach, ob du auf eine geschlossene Formel kommst.
Die beiden Äpfel und die eine Nektarine sind schon klar.
Es bleiben also noch 9 Obststücke aus 4 Sorten auszuwählen.
Dafür gibt es 4^9 = 262144 Möglichkeiten.
------
Nachtrag: Diese Antwort ist falsch. Danke an LUKEars für den Hinweis.
Und hier die korrigierte Antwort.
9 ist in vier Summanden zu zerlegen:
9 0 0 0 (4)
8 1 0 0 (12)
7 2 0 0 (12)
7 1 1 0 (12)
6 3 0 0 (12)
6 2 1 0 (24)
6 1 1 1 (4)
5 4 0 0 (12)
5 3 1 0 (24)
5 2 2 0 (12)
5 2 1 1 (12)
4 4 1 0 (12)
4 3 2 0 (24)
4 3 1 1 (12)
4 2 2 1 (12)
3 3 3 0 (4)
3 3 2 1 (12)
3 2 2 2 (4)
In Klammern steht die Anzahl der Permutationen für den jeweiligen Fall.
In der Summe sind es dann wirklich 220.
dürft ihr ein Computer Programm schreiben, das die Möglichkeiten ausprobiert?
#include <stdio.h>
int main() {
int C = 0;
for (int a=2; a<=11; a++) {
for (int n=1; n<=12-a; n++) {
for (int b=0; b<=12-a-n; b++) {
int k = 12-a-n-b;
if (k >= 0) {
C++;
printf("C=%u a=%u b=%u k=%u n=%u\n",C,a,b,k,n);
}
}
}
}
return 0;
}
Mein Computer sagt, dass es 220 Möglichkeiten gibt...
Nein, eben nicht. Vergiss mal die drei
"Pflichtstücke", die zählen nicht.
Jetzt stell dir die 9 beliebigen als Stellen
einer Zahl vor, für jede Stelle gibt es 4 Ziffern.
Daraus kannst du 4^9 Zahlen bilden, so wie du aus
3 Stellen zu 10 Ziffern 10^3 Zahlen bilden kannst.
Ich sage mal es gibt 15 Möglichkeiten.
Und da man sein Ergebnis begründen soll ........ folgende Überlegung:
• ein Obstkorb soll aus vier verschiedenen Früchten sein, d. h. alle vier Sorten müßen zwingend drin vorkommen.
• "mindestens zwei Äpfel und eine Nektarine" sollen dabei sein; eine einzelne Nektarine steht aber im Widerspruch zur vorherigen Bedingung, da sie darin bereits enthalten ist; weshalb ich diese Formulierung als verbindliche Dreiergruppe begreife [Apfel, Apfel, Nektarine; (AAN)], die neben der verlangten, noch zwei weitere Male vorkommen kann.
Daraus ergibt sich, daß fünf Früchte feststehen (AAN) (B)irne (K)iwi und noch sieben weitere hinzukommen sollen.
• AAN - AAN - [B oder K] = 2 Möglichkeiten
• AAN - [B und/oder K (in Summe 4)] = 5 Möglichkeiten
• [B und/oder K (in Summe 7)] = 8 Möglichkeiten
Macht 2+5+8=15 Möglichkeiten.
alle vier Sorten müßen zwingend drin vorkommen.
dann gäb aber die Forderung nach mindestens einer Nektarine keinen Sinn... oder?
Ne wir dürfen keine Programme benutzen