Bei einer 24er Kiste Bier und 4 Sorten Bier, wie viele Kombinationsmöglichkeiten gibt es, einen Kasten zusammenzustellen?
Also immer gefüllt mit 24 Flaschen, aber mal mit einer Sorte, zwei, drei, oder vier Sorten und allen möglichen Kombinationen. Eine Flasche einer Sorte, alle anderen in der zweiten usw.
1 Antwort
Da gibt's einen Trick:
|Pils|Radler|Weizen|Bock|
|----|------|------|----|
0 5 12 19 24
Du brauchst drei Zahlen zwischen 0 und 24 (hier: 5, 12, 19), um eine Kiste eindeutig zu beschreiben. Die Reihenfolge ist egal und Doppelte sind erlaubt (falls eine Sorte nicht vorkommt).
Das ist immer noch nicht einfach zu zählen, aber wenn Du jetzt noch eine Flasche jeder Sorte pro forma hinzunimmst (also 28 Flaschen, wobei jede Sorte mindestens einmal vorkommen muss), rechnet es sich leichter:
|Pils |Radler |Weizen |Bock |
|-----|-------|-------|-----|
0 6 14 22 28 (EDIT: Zahlen korrigiert)
Das sind nun drei Zahlen zwischen 1 und 27 ohne Zurücklegen, also einfache Schulmathematik:
In der ersten Tabelle bedeuten z.B. (0, 0, 0) = nur Bock, und (10, 10, 24) = 10 Pils+14 Weizen.
Den Trick habe ich nicht verstanden, das Ergebnis habe ich mit
program test;
var a,b,c,z: integer;
begin
z:=0;
for a := 0 to 24 do
for b:=0 to 24-a do
for c:=0 to 24-a-b do
z:=z+1;
writeln(z);
end.
als korrekt verifiziert.
Danke. Kontrolle ist immer gut.
Den Trick habe ich nicht verstanden
Ich versuch's nochmal:
- Ich habe 27 Felder nebeneinander. Auf jedes passt eine Flasche.
- Darauf verteile ich 3 Dummy-Flaschen (macht 27 über 3 Möglichkeiten).
- Jede Verteilung impliziert genau eine Befüllung der Kiste: Die Felder vor dem ersten Dummy sind für Pils, die Felder zwischen dem ersten und zweiten Dummy für Radler usw.
In Deinem Programm könntest Du ebenso über a=1..25, b=(a+1)..26, c=(b+1)..27 iterieren. Das Ergebnis ist natürlich dasselbe. Aber nach dieser Umformung sieht man leichter, dass (a, b, c) eine Auswahl „3 aus 27“ ist, und dafür kennt man eine geschlossene Formel.
Beinhaltet das auch Kisten mit nur einer Sorte oder zwei Sorten?