Letzte Woche Freitag gingen Jay [W], Jay [M], Hubert [NAME VON DER REDAKTION GEÄNDERT] und ich nach der Schule türkisch essen. Als wir so durch die Gesprächsthemen zappten, kamen wir schließlich auf eines von Jay [W]’s Lieblingsthemen: Schokolade! Man erwähnte in der Runde eine Internetseite, auf der man sich Schokolade zusammenstellen und zuschicken lassen kann.
Natürlich fragt man sich da, wieviele Möglichkeiten man eigentlich hat. Auf der Seite werden “über 10.000.000.000 Möglichkeiten”, doch wir wollten es genau wissen.
Abgelenkt von Wochenende und anstrengender Arbeit (ja wirklich) hatte ich das Problem zunächst erst einmal in den Hintergrunf gestellt – heute jedoch wieder aufgegriffen.
Besessen von dem Gedanken das Problem ohne außenstehende Hilfe zu lösen stellte ich zunächst folgende Thesen auf:
Gegeben sind zunächst
- N Schokoladenzutaten gesamt
Es dürfen bis zu B Zutaten gewählt werden, aber mindestens A Zutaten müssen gewählt werden.
Wählt man genau eine Zutat, dann ist X1 = N denn man hat so genau so viele Möglichkeiten wie es Zutaten gibt. Wählt man genau zwei Zutaten, dann ergbit sich die Formel
X2 = (N-1) + (N-2) + (N-3) + … + (N-(N-1))
<=>
X2 = Σi=1N-1 (N-i)
[MAN MÖGE MIR DIE NICHT GANZ KONFORME NOTATION DER SIGMABEGRENZUNG VERZEIHEN]
Für X3 sieht das Ganze schon etwas komplizierter aus, ich hatte in der kurzen Zeit nicht genug derselben, selbst eine passende Formel aufzustellen.
1 2 3 4 5 6 7 8 9 ... N
A [x] [x] [x] [ ] [ ] [ ] [ ] [ ] [ ] ... [ ]
B [x] [x] [ ] [ ] [ ] [ ] [x] [ ] [ ] ... [ ]
C [x] [x] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ... [x]
D [x] [ ] [x] [x] [ ] [ ] [ ] [ ] [ ] ... [ ]
E [x] [ ] [x] [ ] [ ] [ ] [x] [ ] [ ] ... [ ]
F [x] [ ] [x] [ ] [ ] [ ] [ ] [ ] [ ] ... [x]
Nachdem ich diese Hilfe erstellt hatte wurde mir klar – das wird schwierig. Also habe ich doch den Google-Apparat angeschmissen und nach “Drei aus Zehn ohne zurücklegen” gesucht. Gefunden habe ich dann:
N! / (K! (N-K)!)
Der Binominalkoeffizent – DIE Formel für alle Fragen dieser Problematik! So langsam erinnerte ich mich wieder an den Stochastikunterricht!
Das musste ich jetzt nur noch erweitern um alle Möglichkeiten für die einzelnen Zutatenmengen auszusortieren:
X = Σi=AB N! / (i! * (N-i)!)
Endlich war die Formel komplett! Fluchs habe ich das Ganze mit Jay [M] in PHP implementiert: Klick
Und wieder sieht man die Ungenauigkeit der Schokoladenseite – sie werben mit über 10 Milliarden Sorten, aber es sind exakt 16.224.388.824.
Im nachhinein erscheint das Problem recht trivial – Der Binominalkoeffizient ist als solcher auch als N über K bekannt – und kann so in den Taschenrechner eingegeben werden. Aber immerhin weiß ich das jetzt auch wieder und werde es auch so schnell nicht wieder vergessen.
