Der Weihnachtsmann muss daher seine Helfer bestmöglich einsetzen, um all die Wünsche pünktlich erfüllen zu können. Eine Gruppe von 9 Wichteln soll in Teilgruppen zur Arbeit im Nord-, Ost-,Süd- und Westlager eingeteilt werden. Jede Teilgruppe muss aus mindestens einem Wichtel bestehen.
Aufgabe:
Wie viele mögliche Einteilungen gibt es?
70
770
7770
77770
777770
7777770
77777770
777777770
77777777770
Es gibt unendlich viele Einteilungen.
Antwort
Zerknirscht müssen wir schon bei der ersten Frage unseres Mathekalenders eine fehlerhafte Lösung eingestehen. Die richtige Antwort ist:
Es gibt 186480 Einteilungen.
Es tut uns ausgesprochen Leid. Der ausgelobte Preis geht dennoch an Matthias Fischer aus Kiel.
Als Entschuldigung für unseren Fehler und Anerkennung für Ihre zahlreichen Zuschriften ergänzen wir unsere vier Adventsfragen noch um eine zusätzliche Silvesterfrage. Den Preis stiftet unser Redaktionsleiter.
Freuen Sie sich also auf einen zusätzlichen Rätselspaß zum Jahresende. Auch dieser wird um 10:00 Uhr auf der Webseite des Deutschlandfunk-Mathekalenders erscheinen, allerdings am Montag, 31.12.. Über den Jahreswechsel hinweg haben Sie dann bis Neujahr, 8:00 Uhr, Zeit zu knobeln.
Die Redaktion
Und hier die korrekte
Lösung
In unserer unten stehenden Lösung haben wir übersehen, dass die Wichtelgruppen auch den vier Produktionsstätten zugeordnet werden müssen. Es wird zwar korrekt beschrieben, auf wie viele Arten die Wichtel in vier verschiedene Teilgruppen eingeteilt werden können, die jeweils mindestens aus einem Wichtel bestehen. Doch die anschließende Zuordnung zu den Arbeitsstätten fehlt noch.
Die Anzahl der möglichen Zuordnungen bei vier Produktionsstätten ist
4! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24
Beziehungsweise bei k Produktionsstätten
k! = k ⋅ (k-1) ⋅ ... ⋅ 1.
Unser Endergebnis muss also noch mit 24 multipliziert werden, wodurch sich die Zahl 186480 ergibt.
Die Aufteilung der Wichtel auf die Arbeitsgruppen funktioniert wie bereits beschrieben:
Wir lösen eine verallgemeinerte Form des Rätsels, nämlich den Fall, dass n Wichtel in k Teilgruppen eingeteilt werden sollen. Das machen wir nicht einfach, damit es möglichst kompliziert wird, sondern -- im Gegenteil -- es vereinfacht die nachfolgenden Erklärungen. Die Anzahl der Einteilungen bezeichnen wir mit A(n,k) . Wir suchen also A(9,4) .
Man wähle einen Wichtel aus, den wir im Folgenden Herrn F. nennen. Angenommen es wurde eine Einteilung vorgenommen, dann gibt es zwei Möglichkeiten:
(i) Herr F. bildet bereits eine Teilgruppe, er muss also alleine arbeiten.
(ii) Herr F. ist Mitglied einer größeren Teilgruppe, er muss also nicht alleine arbeiten.
In Fall (i) müssen wir das ursprüngliche Problem der Einteilungen für n-1 und k-1 lösen, schließlich ist Herr F. ja bereits eine Teilgruppe. Als nächstes ist also A(n-1,k-1) gesucht.
Im Fall (ii) müssen n-1 Wichtel in k Teilgruppen aufgeteilt werden. Denn wir wissen, dass Herr F. keine eigenständige Teilgruppe bildet. Wir suchen also A(n-1,k) und es gibt damit k ⋅ A(n-1,k) viele Teilgruppen dieser Art. Wir können Herrn F. nämlich zu einer beliebigen der k Teilgruppen hinzufügen, um die komplette Einteilung zu erhalten.
Damit ergibt sich die Formel
A(n,k) = A(n-1,k-1) + k ⋅ A(n-1,k)
Außerdem kann man sich leicht überlegen, dass für positive ganze Zahlen k und n die Gleichungen A(n,1) = 1 und A(k,k) = 1 gelten. Um unser ursprüngliches Problem zu lösen, müssen wir folgendermaßen rechnen:
A(9,4)=A(8,3)+4A(8,4)
=A(7,2)+3A(7,3)+4(A(7,3)+4A(7,4))
=A(7,2)+7A(7,3)+16A(7,4)
=A(6,1)+2A(6,2) + 7(A(6,2)+3A(6,3))+16(A(6,3)+4A(6,4))
=1+9A(6,2)+37A(6,3)+64A(6,4)
=1+9(A(5,1)+2A(5,2))+37(A(5,2)+3A(5,3))+64(A(5,3)+4A(5,4))
=1+9+55A(5,2)+175A(5,3)+256A(5,4)
=10+55(A(4,1)+2A(4,2))+175(A(4,2)+3A(4,3))+256(A(4,3)+4A(4,4))
=10+55+285A(4,2)+781A(4,3)+1024
=1089+285(A(3,1)+2A(3,2))+781(A(3,2)+3A(3,3))
=1089+285+1351A(3,2)+2343
=3717+1351(A(2,1)+2A(2,2))
=3717+1351 ⋅ 3
=7770
Die Zahlen A(n,k) heißen übrigens Stirling-Zahlen zweiter Art.