Binomialkoeffizient / Kombinatorik

[Doppelposter]

Hallo zusammen,

ich stehe vor folgender Frage:

Ich teile einen Tag in 1/4-Stundenblöcke, also 96. Nun möchte ich wissen, wie viele Möglichkeiten es gibt, diese 1/4-Stundenblöcke mit einer Aktivität zu füllen. Begonnen werden soll immer am Anfang einer vollen Stunde, und dann beliebig lang, bis insgesamt vier Stunden Aktivität erreicht sind.

Beispiel einer Möglichkeit:

1. Stunde: Aktivität 1, Aktivität 2, Aktivität 3, Aktivität 4 -> volle Stunde.

2. Stunde: Aktivität 1, keine Aktivität, keine Aktivität, kein Aktivität -> 1/4 Stunde

3. Stunde: Aktivität 1, Aktivität 2, Aktivität 3, Aktivität 4 -> volle Stunde.

4. Stunde: Aktivität 1, Aktivität 2, Aktivität 3, keine Aktivität 4 -> 3/4 Stunde.

Wie kann ich das berechnen? Hilft mir die Kombinatorik da weiter?

[Monger]

Rucksackproblem. Ist NP-unvollständig. Gibt also auch mathematisch meines Wissens keine eindeutige Lösung.

[Matrix316]

Ist das nicht Wahrscheinlichkeitsrechnung? Sowas wie (((2^4)-1)^4)-1 oder in der Art?

[Korfox]

@Matrix316: Du beziehst die 96 Slots nicht mit ein.
@Monger: Sicher, dass das das Rucksackproblem ist? Hier sind doch alle Slots gleichgroß und der Rucksack wird immer voll, ich muss nur insgesamt 16 Viertelstunden verteilen...

@Doppelposter: Lange her, keine Formel im Kopf...

Du kannst einfach 16 Slots Aktivität 1 machen und dann 80 Slots nichts. Dann kannst du anfangen den letzten Aktivitätstlot immer um eins zu verschieben - das geht weiter 97 Mal.
Dann verschiebst du den vorletzten Slot und hängst den letzten wieder direkt an und kannst 78 Mal verschieben...
So kannst du weitermachen, bis die letzten 16 Slots mit Aktivität 1 gefüllt sind.

Jetzt ersetzt du den letzten der Slots mit Aktivität 2 und fängst von vorne an. Bis alle Aktivitäten Aktivität 2 sind.
Dann durch 3.
Dann durch 4.
Und so weiter und so fort.

Dürften im Endeffekt zwei Aufgaben sein: Wie viele Möglichkeiten habe ich, 4 Aktivitäten mit Zurücklegen auf 16 Slots zu verteilen (nPr?) und wieviele Möglichkeiten habe ich ohne Zurücklegen 16 auf 96 zu verteilen (nCr?) und daraus das Produkt.

[Matrix316]

Mir war nicht ganz klar, will er den ganzen Tag ausfüllen oder nur vier Stunden?

Und ich hab mir die Fragestellung noch mal durchgelesen und das ist mir zu kompliziert. ;) "Mit jeder vollen Stunde beginnen und dann beliebig lange bis 4 Stunden erreicht sind..." Häää? ;)

[Doppelposter]

Mir war nicht ganz klar, will er den ganzen Tag ausfüllen oder nur vier Stunden?

Und ich hab mir die Fragestellung noch mal durchgelesen und das ist mir zu kompliziert. ;) "Mit jeder vollen Stunde beginnen und dann beliebig lange bis 4 Stunden erreicht sind..." Häää? ;)

Vier Stunden pro Tag.

Man soll nur zur vollen Stunde mit einer Aktivität beginnen. Und nicht z. B. nach einer "leeren" Viertelstunde (zum Beginn einer vollen Stunde) mit dem ersten Block Aktivität beginnen.

[Spasstiger]

Dürften im Endeffekt zwei Aufgaben sein: Wie viele Möglichkeiten habe ich, 4 Aktivitäten mit Zurücklegen auf 16 Slots zu verteilen (nPr?) und wieviele Möglichkeiten habe ich ohne Zurücklegen 16 auf 96 zu verteilen (nCr?) und daraus das Produkt.
Guter Ansatz. Teil 1 ist aber nicht nPr (Permutation), sondern einfach 4^16. Bei Teil 2 müsste man noch die Fälle abziehen, bei denen eine volle Stunde nicht mit einer Aktivität beginnt oder eine Aktivität nach einer Pause nicht zur vollen Stunde beginnt. Produkt aus Teil 1 und Teil 2 sollte dann passen.

Zu Teil 2: Pro Stunde gibt es fünf Möglichkeiten: 0, 1, 2, 3 oder 4 zusammenhängende Aktivitätsblöcke. Es gibt also 5^24 mögliche Kombinationen von Aktivitätsblöcken in 24 Stunden mit stündlichen Beginn zur vollen Stunde. Davon werden die gesucht, die in Summe 16 Aktivitätsblöcke zu je 15 min ergeben.

[Doppelposter]

Bei Teil 2 müsste man noch die Fälle abziehen, bei denen eine volle Stunde nicht mit einer Aktivität beginnt oder eine Aktivität nach einer Pause nicht zur vollen Stunde beginnt.

Und wie berechne ich diese Fälle?

[Spasstiger]

Und wie berechne ich diese Fälle?
Das ist die Frage. ;)
Ich habe Teil 2 mal in meinen numerischen Löser/Simulator von Würfelproblemen gefüttert und komme größenordnungsmäßig auf 3*10^10 Möglichkeiten. Insgesamt für das Problem (Produkt aus Teil 1 und Teil 2) über 10^20 Möglichkeiten.

Spielt es denn überhaupt eine Rolle, welche Aktivitäten in den Aktivitätsblöcken ausgeführt werden? Wenn nein, vereinfacht sich das Ergebnis Teil 1 zur Anzahl 1.

[Doppelposter]

Spielt es denn überhaupt eine Rolle, welche Aktivitäten in den Aktivitätsblöcken ausgeführt werden? Wenn nein, vereinfacht sich das Ergebnis Teil 1 zur Anzahl 1.

Nein, bzw. die "Aktivität" ist immer die selbe.

[PC-Kurbel]

Mathe Captain hier: Du musst dich genauer ausdrücken. Sonst wirst du nicht glücklich, weil jeder etwas anderes interpretiert und eine andere Aufgabe löst/bearbeitet. Deswegen erst einmal ein paar Nachfragen:


Muss eine Stunde mit einer Aktivität beginnen oder kann sie auch komplett leer sein? Falls die Antwort ja ist, braucht man keine 24 Stunden, sondern nur 16 Stunden.
In deinem Beispiel werden nur 3 Stunden Aktivität erreicht oder zählt jede Stunde, wo mindestens 1/4 Stunde Aktivität enthalten ist, als komplett aktive Stunde?


Ich gehe jetzt einfach mal von der Antwort (1.) "kann leer sein" und (2.) "nein" aus. Ansonsten kann man meinen Ansatz auch modifizieren und kommt dann zu einem etwas anderen Ergebnis.

So, ich teile meine Lösung mal in Schritte ein:

Der schwere Teil: Man überlegt sich zuerst alle Kombinationen von Stunden, sodass die Anzahl der Aktivitäten pro Stunden absteigend sortiert ist. Also nicht so wie in deinem Beispiel sondern zum Beispiel so:
1. Stunde: 4 Aktivitäten,
2. Stunde: 4 Aktivitäten,
3. Stunde: 3 Aktivitäten,
4. Stunde: 2 Aktivitäten,
5. Stunde: 2 Aktivitäten,
6. Stunde: 1 Aktivität,
Diese Anzahl kann man mit der sogenannten Partitionsfunktion berechnen. Die Kombinatorik hilft also! :wink: Hier ist der Link zur Wikipedia:
Partitionsfunktion (https://de.wikipedia.org/wiki/Partitionsfunktion)
Tip: Weiter unten im Artikel gibt es die Variante mit "Partitionen mit vorgegebenem kleinsten Summanden". Das kann man dann auch für größten Summanden umdrehen (bei dir wäre er 4, weil man pro Stunde maximal 4 Aktivitäten hat). Ich glaube das einfachste und schnellste wird sein, alle Partitionen zum Beispiel in der Form (4,4,3,2,2,1) per Hand (bzw. Computerprogramm) hinzuschreiben. Das dauert wohl ein paar Minuten, aber dann steht es auch da.
Für jede Partition macht man nun das Folgende:
Man "mischt" diese durch und bestimmt die Kombinationen. Ich mache das mal anhand des obigen Beispiels. Dort sind ja 6 Stunden, wo etwas passiert. Die Zahlen 1,2,3,4,5,6 kann man auf 6! = 1*2*3*4*5*6 = 720 verschiedene Möglichkeiten aneinander reihen. Wenn man aber zum Beispiel die 1. und die 2. Stunde vertauscht, dann merkt man das ja nicht, weil sie ja die gleiche Anzahl an Aktivitäten enthalten. Daher teilt man nun die "nutzlosen" Vertauschungen wieder heraus. In dem Beispiel gibt es zweimal die 4, also teilt man 720 durch 2! = 1*2 = 2. Die 2 taucht auch zweimal auf, also teilt man noch einmal durch 2! und erhält (720/2)/2 = 180 Kombinationen. Für (An-)Zahlen, die einzeln auftreten teilt man 1! = 1 heraus. Man kann es sich also sparen. Bei dreifach auftretenden Zahlen eben 3! = 1*2*3 =6 und so weiter.
Abschließend muss man für jede dieser Kombinationen auf die 24 Stunden verteilen. (Ich hatte ja angenommen, dass es inaktive Stunden gibt, weil sonst die 96 Blöcke keinen Sinn ergeben). In der Partition von oben gibt es 6 Stunden, mit mindestens einer Aktivität. Also muss man die Anzahl der Möglichkeiten bestimmen, aus der Menge {1,2,3,...,24} eine 6-elementige Teilmenge auszuwählen. Das kann man ganz einfach mit dem Binomialkoeffizient (24 über 6) = 134.596 berechnen.
Damit erhält man für die Aktivitätsverteilung bzw. Partition aus dem ersten Schritt insgesammt 180 * (24 über 6) = 24.227.280 Möglichkeiten.

Fazit: Tja, also ich denke, ich würde einfach eine Tabelle mit den ganzen Partitionen aus Schritt 1 machen. Dann schreib für jede Partition die Anzahl der Kombinationen für das Druchmischen rechts daneben. Daneben dann den Wert für den Binimialkoeffizienten für die leeren Zeilen. Anschließend die beiden Werte in jeder Zeile multiplizieren und den ganzen Rotz aufaddieren. Das wäre eigentlich Idealer Stoff für ein Computerprogramm. Falls du eine Formel willst:

Summe_{(i_1,...,i_k) \in P(16) | i_j<= 4} (k! / Produkt_{m=1}^4 (#{i_j = m})! ) * (24 über k)

Das sieht ohne Formeleditor wirklich grausam aus...

Ich hoffe ich konnte helfen. Ich beneide dich um diese "Aufgabe" nicht.

Viele Grüße
PC-Kurbel

[Matrix316]

Hmmm, wo lernt man denn Partitionsfunktionen?

Spielt es eigentlich eine Rolle, dass immer die nächste Viertelstunde mit Aktivität gefüllt werden soll?

Im Prinzip hat man ja pro Stunde nur 3 Slots zu berechnen, also quasi 2^3 weil die erste Viertelstunde ist immer 1 (also quasi sind das ja Bits im Endeffekt ;)) und die folgenden 1 oder 0. Und dann muss man das nur hoch 4 rechnen, weil man die Wahrscheinlichkeit für 4 Stunden berechnen müsste. Im Prinzip würde auch dann 2^12 gehen, was das gleiche wie 2^3^4 ist. ;)

Also quasi 4096 Varianten für 4 Stunden.

Und wenns nur 4 Stunden in 24 sind, müsste man das Ergebnis mal 24 rechnen - oder mal 20, wenn die Aktivität nicht zum nächsten Tag überwechseln darf. Wenn ich um 23 Uhr starte, habe ich ja keine 4 Stunden mehr für den Tag.

Oder denk ich zu einfach? ;)

EDIT: Die Reihenfolge hat doch Auswirkungen. ;) Tricky Tricky...;) Aber vielleicht ist das garnet so kompliziert wie man meint. Im Prinzip hat jede Stunde folgende Optionen 1000 oder 1100 oder 1110 oder 1111 -> das sind quasi 4 Varianten pro Stunde und in 4 Stunden wären es 4^4 oder 4x4 (dieses hoch oder mal ist das verwirrendste an der Stochastik ;)) Kombinationen, oder?