Kombinatorik - Zusammenbauen eines Turmes aus verschiedenen Legosteinen

Aufrufe: 186     Aktiv: vor 1 Woche, 5 Tage

0

 

 

 

Problemstellung:


Ich beschäftige mich schon seit einiger Zeit mit dieser Frage. Es geht darum, einen Turm aus verschiedenen farbigen Legosteinen zusammenzubauen. Diese Legosteine können auch mehrmals vorkommen.

Die Anzahl der in den Turm passenden Steine entspricht der Zahl n und die Häufigkeit der verschiedenen Legosteine kann in einer Menge M angegeben werden, bei der jedes Element angibt, wie oft ein bestimmter Legostein vorkommt. 

Der Knackpunkt der ganzen Sache ist aber, dass die Summe aller vorhandenen Legosteine nicht der Höhe des Turmes n entsprechen muss. Es können einfach Steine über bleiben. Also handelt es sich nicht um eine Permutation. Die eigentliche Frage ist nun also eine allgemeine Gleichung dafür zu finden, die angibt, wie viele Möglichkeiten es denn nun gibt, den Turm zu bauen.

Beispiel:

Legosteine
                            
Rot:  4-Mal                
Grün: 2-Mal                 
Blau: 2-Mal                 
                            
Höhe des Turmes: 5

Schon hier gibt es 140 verschiedene Möglichkeiten den Turm zu bauen. Setzt man die Eingabe Werte in die normale Permutationsgleichung mit Wiederholung - ich dachte dass das evt. trotzdem zum Ergebnis führen könnte - ein, kommt 1.25 heraus, was ja nicht etwa die Lösung sein kann.

Ich meine die Gleichung

\(\frac{n!}{k_{1}! \cdot k_{2}! \cdot ... \cdot k_{s}!}\)

Eigene Ansätze:


Ich habe zunächst mal ein Computerprogramm entwickelt, das mir alle Möglichkeiten für verschiedene Eingaben angeben kann. Dann habe ich versucht Zusammenhänge zu finden. Zwischen der Anzahl an Möglichkeiten und den Anzahlen von erstmal zwei festgelegten verschiedenen Legosteinen.
Ich habe auch versucht logisch an die Frage heran zugehen - mir u.a. die Frage gestellt welche / wie viele  Steine übrig bleiben und was das über die Abweichung der wirklichen Anzahl an Möglichkeiten zum Ergebnis beim Einsetzen der Eingaben in die normale Permutations Gleichung ausmacht. Aber alles ohne Erfolg.

Ich hoffe ihr habt meine Fragestellung erstmal verstanden und wisst evt. wie man sie lösen kann.

 

 

 

 

gefragt vor 4 Monate, 3 Wochen
d
der mathematische boss,
Schüler, Punkte: 30
 
Kommentar schreiben Diese Frage melden
4 Antworten
0

Ich denke, dass die Anzahl der Möglichkeiten = 8*7*6*5*4 sind , da die Reihenfolge ja zählt und es ohne Zurücklegen ist

geantwortet vor 2 Wochen, 1 Tag
l
 

Danke für deine Antwort. Ich habe mir ebenfalls überlegt einfach n! zu benutzen, allerdings kann es bei dieser Aufgabenstellung auch mehrere Steine von einer Sorte (Beispiel 3 Grüne Legosteine) geben, die nicht mehr von einander zu unterscheiden sind. Dadurch funktioniert diese Formel nicht mehr. Trotzdem Danke!   -   der mathematische boss, vor 1 Woche, 6 Tage

Ja, stimmt, allerdings kann man ja mit Grün 1 und Grün 2 rechnen, dann würde der Ansatz stimmen, ansonsten ist die Aufgabe ganz schön schwer   -   [email protected], vor 1 Woche, 6 Tage

Weil wenn ich sag ich hab 10 Tulpen 5 Rote 2 gelbe und 3 orange, will die im Beet anordnen, sodass aller Tulpen jeder Farbe nebeneinander stehen hab ich:
5!*2!*3!*6 Möglichkeiten, weil für die 1. rote gibts ja 5 Möglichkeiten, deswegen hätt ich dasselbe auch für den Turm gesagt
  -   [email protected], vor 1 Woche, 6 Tage
Kommentar schreiben Diese Antwort melden
0

Ich denke, dass die Anzahl der Möglichkeiten = 8*7*6*5*4 sind , da die Reihenfolge ja zählt und es ohne Zurücklegen ist

geantwortet vor 2 Wochen, 1 Tag
l
 
Kommentar schreiben Diese Antwort melden
0

ziemlich sicher können dir dabei generating functions weiterhelfen (eventuell hypergraphs?)

https://math.stackexchange.com/questions/3527315/how-many-ways-can-we-select-3-elements-from-the-multiset-g-a-b-b-c-c-c?rq=1

hier ist ein ansatz mit generating functions, auch wenn das ergebnis nicht wirklich elegant ist. bei deren ansatz läuft das ziemlich auf eine indexschlacht hinaus.
gut möglich dass es simpler geht - mir kommt das problem (mit buchstaben und wörtern anstelle von legos und türmen) ziemlich bekannt vor. 

wenn du nichts hilfreiches zu den themen findest, feststeckst, oder einen besseren ansatz hast, schreib einfach nochmal :)

geantwortet vor 2 Wochen, 1 Tag
a
aufjedebewertungeinschnaps
Student, Punkte: 1.07K
 

Dankeschön für deine Antwort! Ich habe mir die Seite mal angeschaut und das geht schon in die richtige Richtung zur Lösung meiner Frage. Ich lese mich mal weiter durch und schreibe bei Neuigkeiten bzw. bei neugefundenen Ansätzen.   -   der mathematische boss, vor 1 Woche, 6 Tage

Ok, also ich habe mir die Antworten der Seite jetzt nocheinmal genau durchgelesen. Ich würde mir die komplexe Gleichung vom User InterstellarProbe einfach kopieren (ich kann sie hier leider nur schwer einfügen) und dann den letzten Teil

... (p+t-1-|A|-∑...) über (t-1)

mit der allgemeinen Gleichung für eine Kombination mit Reihenfolge n^k ersetzen. Es würde also im Endteil

... (p -|A| -∑...)^(t-1)

statt dem ursprünglichen Teil stehen.
Der Rest der Gleichung bleibt einfach gleich und wird kopiert. Das wäre doch dann die Lösung zu meiner Aufgabe.
Ist das prinzipiell richtig, oder hab ich noch einen Denkfehler?
  -   der mathematische boss, vor 1 Woche, 6 Tage

du liegst dabei vom prinzip her auf jeden fall richtig, dass du mit der summe von interstellarprobe noch nicht fertig wärst - auch wenn deine abänderung noch nicht ganz das gewünschte ziel erreichen würde
eigentlich müsste man ja irgendwie noch einen multinomialkoeefizienten einbauen, um die permutationen der bausteine zu beschreiben. wie man das genau macht, müsste ich selbst überlegen (bei so möglichkeiten ausrechnen ist das oft so fusselkram)

no offense aber ich geh davon aus, dass dir als schüler noch zu viel vorwissen fehlt um die aufgabe anständig bearbeiten zu können. (bei interstellarprobe wäre es in dem fall das inclusion exclusion thoerem aka siebformel)

wenn du trotzdem mehr über kombinatorik wissen möchtest, schau dir das mal an:
http://page.mi.fu-berlin.de/block/htw-lehre/wise2015_2016/bel_und_rend/skripte/GraphentheorieII.pdf
wenn du da die erste 5-7 seiten ließt bis zu den ersten propositionen, merkst du sicher schon ob das was für dich ist oder nicht (kann sein, dass ein paar definitionen nicht ganz schülergerecht sind, die ersten paar propositionen kann man aber auch verstehen, wenn man die nicht-schulgerechten definitionen erstmal einfach überspringt.
ist natürlich nur ein vorschlag, ignorier das einfach wenn du kein bock drauf hast haha

ich kann dir aber versprechen, dass es deutlich spannendere fragestellungen in der kombinatorik gibt als bloß die anzahl von möglichkeiten auszurechnen, siehe beispielsweise norine's conjecture.
  -   aufjedebewertungeinschnaps, vor 1 Woche, 5 Tage
Kommentar schreiben Diese Antwort melden
0

Hallo Zusammen!  Ein bisschen kann ich glaub ich auch helfen.

Mit folgendem Beispiel möchte ich einsteigen:

Man möchte 6 Tulpen in eine Reihe pflanzen und hat einen Samen für eine blaue, zwei Samen für rote und drei Samen für grüne Tulpen.

Dann hat man Grundsätzlich 6! = 6*5*4*3*2*1 =  720 Möglichkeiten. Weil einige Farben aber mehrmals vorkommen, muss man diese Zahl allerdings durch (1! * 2! 3!) = 12 dividieren, was: 720/12 = 60 Möglichkeiten ergibt. Das liegt daran, dass man die grünen Tulpen schon selber in 3!=6 verschiedenen Möglichkeiten anordnen kann, was aber optisch keine Unterschied macht. Soweit bist du ja schon gekommen. 

Wenn man jetzt aber beispielsweise nur 4 Tulpen betrachten will, was deinem n entspricht, muss man jetzt also irgendwie versuchen alle unterschiedlichen 4er Blöcke rauszufinden. In jedem 6er Block befinden sich ja 3 (3=6-4+1) vollständige 4er Blöcke (ohne abschneiden am Ende!), sodass das dann 60*3=180 Möglichkeiten wären. Jeder 4er Block kommt aber in zwei verschiedenen 6er Blöcken vor, Beispiel:

g r b g r g

g r  b g g r

Der 4er Block [g r b g] kommt im oberen und unteren vor, da nur die beiden letzten Tulpen tauschen, die nicht im Zifferblock enthalten sind. Das bedeutet wir müssten die 180 noch durch 2! dividieren: 180/2*1 = 90

Eine weiter Sache darf von uns auch nicht vernachlässigt werden, ein Beispiel:

g r  b g g r

g r g r  b g 

Auch in diesen beiden 6er Blöcken kommt unser 4er Block [g r b g] in beiden vor und wir dürfen ihn nicht doppelt zählen. Der 4er-Block kann also entweder vor oder nach den beiden einzelnen Tulpen kommen, sodass es für dieses auch nochmal 2!=2 Möglichkeiten der Anordnung gibt. 

Also müssen wir auch deswegen nochmal unsere Möglichkeiten halbieren, was dann 90/2 =45 Möglichkeiten ergibt. 

Veralgemeinern wir das doch nochmal: 

Wir wollen aus einer Menge mit p vielen Legosteinen einen Turm aus n vielen Legosteinen bauen wollen und  haben k viele Sorten unterschiedlicher Steine in den Mengen  k1, k2, … kk.

Es gilt also: p=  k1+k2 + ....+kk  

Die Anzahl der Türme, die gebaut werden, lassen sich also (vermutlich) so berechnen:

 

 

  Mit den Werten deines Beispiels eingesetzt kommt da 140 raus.

Ob die Formel stimmt, bin ich mir selbst aber nicht 100% sicher- hab das auch zum ertsen mal wirklich durchdacht. Vielleicht könnt ihr ja mal eure Ansichten teilen. 

Hab noch eine Frage: Wo hast du das Programm zum durchrechnen geschrieben und wie und womit?

Danke und viele Grüße!

 

 

 

 

geantwortet vor 1 Woche, 5 Tage
d
derpi-te verified
Schüler, Punkte: 839
 



Danke schonmal für deine Hilfe und die verständliche Erklärung!

Da ich mich nicht wirklich in dem Bereich Programmiersprachen auskenne, habe ich einfach ein Drag and Drop Programm mit dem Namen Scratch 2.0 verwendet. Dabei zieht man einfach nur vordefinierte Blöcke zusammen, wie z.B.
|Setze die Variable a auf 5| oder |Wiederhole ... 10 mal| und erstellt damit seinen Code.
Es ist eigentlich selbsterklärend, doch hat mich dann trotzdem viel Zeit gekostet, auch wenn ich Scratch schon vorher für andere ähnliche Aufgaben benutzt habe. Ich kann es dir aber jetzt nicht wirklich empfehlen, da vermehrt Bugs auftreten und die Engine nur sehr langsam Befehle ausführt.
Wenn dich das mehr interessiert dann schreib oder frag einfach nochmal.

Nun aber zum Thema, ich kann deinen Weg komplett nachvollziehen bis zu dem Zeitpunkt, in dem du die 4er-Blocks gebildet hast. Denn dann kannst du meiner Meinung nach nicht allgemein die Möglichkeiten durch (p-n)! dividieren.

Dazu ein simples Beispiel:

Turm Höhe n=2

Legosteine
Rot k(1)=2
Blau k(2)=2
Grün k(3)=1

p=5

Möglichkeiten:

Rot Rot
Rot Blau
Rot Grün

Blau Rot
Blau Blau
Blau Grün

Grün Rot
Grün Blau

Das sind 8 Möglichkeiten der Kombination. Setzt man die Werte allerdings in deine Gleichung ein, erhält man 10 Kombinationen.

Das Problem ist nachdem Bilden der verschiedenen 2er-Blöcke, können auch doppelt vorkommende nicht im 2er-Block vorhandene Legosteine vorkommen:
(In Klammern ist der 2er-Block)
...
(Rot Blau) Rot Blau Grün
(Rot Blau) Rot Grün Blau
(Rot Blau) Blau Rot Grün
(Rot Blau) Blau Grün Rot
(Rot Blau) Grün Rot Blau
(Rot Blau) Grün Blau Rot
...
(Rot Rot) Blau Blau Grün
(Rot Rot) Blau Grün Blau
(Rot Rot )Grün Blau Blau
...

Wie du siehst,gibt es nicht für jede Endkombination 6 Möglichkeiten der Permutation, also kannst du nicht einfach durch 6 teilen.

Und wie man das dann vollständig verallgemeinern will, ist wahrscheinlich ziemlich kompliziert.

Aber auf jeden Fall nochmal Danke für die Mühe und ebenfalls Viele Grüße
  -   der mathematische boss, vor 1 Woche, 5 Tage
Kommentar schreiben Diese Antwort melden