Das Krümelmonster besitzt 9 Kekse - Kombinatorik?
Das Krümelmonster besitzt neun verschiedene Kekse.
1 Wie viele Möglichkeiten hat es, diese in fünf Portionen aufzuteilen? (Die Portionen bestehen aus mindestens einem Keks und sind ungeordnet.)
2 Wie viele Möglichkeiten hat das Krümelmonster, die Kekse auf fünf nummerierte Teller zu legen, so dass kein Teller leer bleibt?
3 Nach dem fünfgängigen Menü entdeckt das Monster noch ganz unten in der Packung drei weitere verschiedene Kekse (Nachtisch). Wie viele Möglichkeiten gibt es, diese auf die Teller zu verteilen, so dass auf keinen Teller mehr als ein Keks gelegt wird?
Mfg1 Antwort
Hallo,
zu Aufgabe 1):
Da jede Portion mindestens einen Keks hat, kannst Du 5 der 9 Kekse auf jeden Teller verteilen, so daß noch 4 Kekse übrigbleiben, die nun nach Belieben verteilt werden dürfen.
Das sind k=4 Kekse auf n=5 Teller. Dann gibt es (n+k-1 über k) Möglichkeiten, also (8 über 4)=70 Möglichkeiten.
Herzliche Grüße,
Willy
Ja; es gibt kaum ein Gebiet, auf dem der 'gesunde Menschenverstand' so versagt wie bei der Stochastik.
aber die Kekse sind doch wohlunterscheidbar. Wie wählst du dann die 5, die du auf jeden der Teller verteilst ?
Um die Kekse voneinander zu unterscheiden, muss man einfach die Lösung mit 5! (5 Fakultät) mutliplizieren.
(Nachtrag: stimmt doch nicht so - man muss dann noch durch das Produkt der möglichen Anordnungen der Kekse je Teller teilen.)
-----
Und überhaupt - das Krümelmonster verteilt Kekse auf Teller!? Bin ich in einer Parallelsesamstraße gelandet oder was?
Dann mußt Du das weiterführen.
Es gibt 9!/4! Möglichkeiten, fünf bestimmte von neun Keksen auf die Teller zu verteilen.
Außerdem mußt Du die 70 restlichen Möglichkeiten auf Permutationen untersuchen.
Es gibt folgende Möglichkeiten der Verteilung der vier restlichen Kekse:
4 auf einen Teller, auf die anderen kein weiterer Keks.
Das sind 5 Möglichkeiten, weil es 5 Teller gibt.
3+1. Das sind zunächst 20 Möglichkeiten, multipliziert mit 4, weil jeder der vier Kekse dieser einzelne sein kann, macht 80.
2+2 10 Möglichkeiten (5 über 2) Es gibt aber noch 6 unterschiedliche Verteilungen, daher 6*10=60
2+1+1 30 Möglichkeiten (5 über 2) für die beiden Teller, die nichts mehr bekommen, mal 3 für die Kombinationen von 2;1;1.
Außerdem gibt es 12 Permutationen dieser Gruppen, macht 360.
1+1+1+1 5 Möglichkeiten, weil einer von 5 Tellern unbedacht bleibt. Außerdem 4!=24 Permutationen=120
Insgesamt hast Du dann (9!/4!)*(5+80+60+360+120)=9.450.000
Willy
sieht mir ziemlich fehleranfällig aus und sehr aufwendig, wie wäre es mit der Sterling Zahl zweiter Ordnung S_9,5 und dann rekursiv lösen? weil es ist ja eine Mengenpartition
Wenn Du weißt, wie das geht. Ich kenne dieses Verfahren nicht.
ich werd es mal berechnen und hier aufschreiben und dann mit deiner Lösung vergleichen
S_9,5 = S_8,4 + 5*S_8,5 = S_7,3+4*S_7,4+5*(S_7,4+5*S_7,5) = S_6,2+3*S_6,3+4*(S_6,3+4*S_6,4)+5*((S_6,3+4*S_6,4)+5*(S_6,4+5*S_6,5)) = 31+3*90+4*(90+4*65)+5*((90+4*65)+5*(65+5*15)) = 6951
Ab n=6 habe ich die Werte aus dem Sterling-Dreieck herausgelesen, aber von deinem Wert bin ich weit entfernt hmmm
Also die Definition der Sterling Zahl ist: Eine k-Partition einer n-elementigen Menge A ={a1,...,an} ist eine Zerlegung der Menge A in genau k nichtleere,disjunkte Mengen. Die Anzahl der k-Partitionen wird durch die so genannten Stirlingzahlen zweiter Art angegeben und mit S_n,k bezeichnet
und die Rekursionsformel lautet: S_n,k = S_n−1,k−1 + k*S_n−1,k.
Da traue ich eher meiner Methode.
Du kommst ja schon auf mehr Möglichkeiten, wenn Du nur überlegst, auf wie viele unterschiedliche Arten sich fünf der neun Kekse auf fünf Teller verteilen können:
Für den ersten Teller gibt es die Wahl zwischen 9 Keksen, bleiben für den zweiten acht, den dritten sieben, den vierten sechs und den letzten Teller noch fünf zur Auswahl.
Das macht 9*8*7*6*5=15120
Das mußt Du noch mit den zahlreichen Möglichkeiten multiplizieren, mit denen Du die restlichen vier Kekse verteilen kannst.
bei Wikipedia gibts auch ein größeres Dreieck S_9,5 = 6951 stimmt tatsächlich https://de.wikipedia.org/wiki/Stirling-Zahl
habe mich mit mehreren Kommilitonen unterhalten, die haben dasselbe raus, also die Kekse sind unterscheidbar, die Portionen jedoch nicht, es gibt so ein Urnen und Bälle Modell mit Formeln und für diesen Fall lautet die Formel eben Sterling Zahl zweiter Art, denn dieser Fall entspricht der Aufteilung der Menge der Kekse in 5 nicht-leere (surjektive) Teilmengen. Die Teilmengen entsprechen den Keksen,die in derselben Portion landen. mit n = 9 und k=5 ist das per Definition S_9,5 . Wir hatten das auch bewiesen,dass das so ist,also sollten wir es verwenden dürfen.
Dann vielleicht deswegen, weil es keine Rolle spielt, auf welchem Teller welche Keksdosis landet. In dem Fall kann es sein. Wenn Du zwischen den Tellern unterscheidest, kommst Du auf jeden Fall auf eine höhere Zahl.
Für die ersten fünf Kekse kommst Du dann nur auf 9 über 5 gleich 126 Möglichkeiten, weil es jetzt nur noch darum geht, welche der Kekse ausgewählt werden, nicht mehr, welcher Keks auf welchem Teller landet, solange nur jeder seinen Teller findet.
Zitat von wikipedia:
Die Stirling-Zahl zweiter Art S_n,k ist die Anzahl der k-elementigen Partitionen einer n-elementigen Menge, also die Anzahl der Möglichkeiten, eine n-elementige Menge in k nichtleere disjunkte Teilmengen aufzuteilen.
S_n,k ist auch die Anzahl der Möglichkeiten, n unterscheidbare Bälle auf k nicht unterscheidbare Fächer aufzuteilen, so dass mindestens ein Ball in jedem Fach liegt. Sind die Fächer unterscheidbar, so erhält man k!S_n,k Möglichkeiten, dies ist auch die Anzahl surjektiver Abbildungen einer n-elementigen Menge auf eine k-elementige Menge.
Das heißt bei (2) kommt dasselbe raus mit Vorfaktor k!=5! , da die Teller dann ja auch unterschieden werden.
Bleibt also nur noch (3)
wenn die Teller unterschieden werden komme ich auf 5! * 6951 = 834120 Möglichkeiten
6951 stimmt.
Ich habe es jetzt anders berechnet:
Es gibt folgende Möglichkeiten, 9 Kekse auf 5 Portionen zu verteilen ohne leere Mengen:
5+1+1+1+1
4+2+1+1+1
3+3+1+1+1
3+2+2+1+1
2+2+2+2+1
Da die Kekse unterscheidbar sind, gibt es für die erste Möglichkeit
9 über 5=126 Kombinationen
Die nächste: (9 über 4)*(5 über 2)=1260
Dann: (9 über 3)*(6 über 3)/2!, weil zwei Portionen mit gleicher Anzahl dabei sind, ergibt 840
(9 über 3)*(6 über 2)*(4 über 2)/2!=3780
(9 über 2)*(7 über 2)*(5 über 2)*(3 über 2)/4!=945
126+1260+840+3780+945=6951
Bei gleich großen Portionen muß man durch die entsprechende Fakultät teilen, um Doppelungen auszuschließen.
Bei einer Menge {1;2;3;4), die in 2*2 Partitionen aufgeteilt wird, gibt es {1;2}{3;4} - {1;3}{2;4} - {1;4}{2;3}, also (4 über 2)/2!=3 und nicht etwa 4 über 2=6 Möglichkeiten, wie ich zuvor immer berechnet hatte. Die anderen drei wären nur noch Vertauschungen von bereits Dagewesenem. Bei dieser Aufgabenstellung ist es nicht entscheidend, ob bestimmte Elemente in der ersten oder zweiten Partition vorkommen, sondern ob sie überhaupt vorkommen.
Was auf welchem Teller landet, bleibt unberücksichtigt.
Wieder was gelernt.
Willy
respekt,ich hätte gedacht es lässt sich nicht normal kombinatorisch lösen aufgrund dieser Bedingung >=1 Keks pro Portion und der Unterscheidbarkeit,aber so macht das Sinn :)
Ich hatte anfangs zwei Dinge nicht beachtet:
Die Teller selbst sind nicht numeriert. Ob also bei der Verteilung 5+1+1+1+1 die fünf Kekse auf dem ersten, zweiten usw. Teller liegen, ist unerheblich.
Das Schwerwiegendere aber war, daß es Doppelungen bei den Portionen gibt.
Nehmen wir an, Du teilst die Menge {a;b;c;d;e;f) in 2+2+2 Portionen auf.
Dann könntest Du meinen: Für die erste Portion hast Du die Auswahl von 2 aus 6 Keksen, also (6 über 2)=15; für die zweite sind es noch (4 über 2)=6 (die dritte ist dann festgelegt, weil nur noch zwei Kekse übrigbleiben). So kämst Du auf 15*6=90.
Diese 90 sind aber nur unter dem Aspekt unterschiedlich, daß die Reihenfolge der Portionen berücksichtigt wird.
Wenn Du meinetwegen in der ersten Portion die Kombination a;c hast, dann könnte die zweite aus b;d, die dritte schließlich aus e;f bestehen.
Unter den 90 Kombinationen käme aber auch b;d e;f und a;c vor, eine Permutation, insgesamt sechs Permutationen, die alle die gleichen Portionen, nur in unterschiedlichen Reihenfolgen, ergeben.
Ich muß also durch die Fakultät der Anzahl der gleich großen Portionen, hier also durch 3!=6 teilen.
Dann aber sind es nicht mehr 90, sondern nur noch 15 Aufteilungen, die wirklich unterschiedlich sind.
Bei unterschiedlich großen Portionen besteht das Problem nicht, weil zum Beispiel eine Zweiergruppe niemals mit einer Dreiergruppe identisch sein kann.
Erst, als ich auf diesen Trichter kam, hat die Sache funktioniert.
geiler Dialog... danke dafür xD !!