7 Kugel auf 11 Fächer verteilen?

Aufrufe: 126     Aktiv: vor 12 Stunden, 38 Minuten

0

Hallo, meine Überlegungen sind fortgeschritten und nun shclage ich mich mit folgendem Problem herum:

Angenommen ich habe im Stochastichen Modell 11 Fächer vor mir.

Und habe 7 Kugeln die ich irgendwie in die 11 Fächer verteilen kann.

 

Wie kann ich alle möglichen 11 Tupeln durchgehen wobei jedes davon eine Situation beschreibt wie die Kuuln verteilt wurden?

 

Also bspw. das Tupel (0,0,0,0,5,0,0,0,0,1,1) beschreibt dass 5 Kugeln in Fach 5, 1 Kugel in Fach 10 und 1 Kugel in Fach 11 gelandet sind.

Wie gehe ich hier systematisch alle solchen 11 Tupel durch, wobei wie erwähnt die Summe der "Fächerinhalte" eben 7 ergeben muss?

Wie mache ich das systematisch?

gefragt

Student, Punkte: 219

 
Kommentar schreiben
2 Antworten
0
Hallo,

Kombinatorik war nie mein Steckenpferd aber ich würde folgendermaßen vorgehen. 
Wir machen 2 Überlegungen. Einmal wie oft kann man die Zahl 11 durch 7 Zahlen aus $\{0,1,\ldots, 10,11 \}$ darstellen (hier ist die Reihenfolge egal). Und dann noch, wie viele Permutationen es pro Fall gibt. 
Wir haben 
$$ 11 = 11 + 0 + 0 + \ldots $$
und
$$ 11 = 10 + 1 + 0 + \ldots $$
und 
$$ 11 = 9 + 1 + 1 + 0 + \ldots $$
und 
$$ 11 = 9 + 2 + 0 + 0 \ldots $$
Man erkennt ab hier relativ schnell ein Muster, wie viele Fälle jeweils dazu kommen. 

Danach musst du dir also nur noch überlegen, wie viele Permutationen 11 Elemente haben. 

Was hälst du davon?

Grüße Christian
Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 29.28K

 

Macht Sinn.
ich ha e mir mittlerweile ein, hoffentlich richtig funktionierendes, java Programm dazu gebastelt.
Weil man vermutlich nciht umhin kommt, alle Fälle durchzugehen.

Wie ich vorgehe:
Ich habe ja 7 Variabeln, die je Werte 1-11 einnehmen.
Alles gleich wahrscheinlich.

Also suche ich alle möglichen 7 Tupel, eins davon ist bspw.
(1,4,2,7,10,5,11)

Weil es in meiner Aufgabe, die ich lösen will so ist dass die Bedingung gewissermassen kommutativ ist,
ist es egal wie genau die 7 zahlen in obigem Tupel angeordnet sind, die bedingung wird entweder erfüllt oder nicht.
(beim betrachten der Fälle muss man hal noch mit einem faktor x die zahl der zutreffenden fälle multiplizieren)
Kurzum, es kommt mir hier nur drauf an dass
je einmal die 1,2,4,5,7,10,11 vorkommen.
Davon ausgehend kann ich genauso gut ein 11 Tupel betrachten wobei die i'te Nummer angibt wie oft die zahl i vorkommt.
Obiges Tupel ist also in der neuen Notation:
(1,1,0,1,1,0,1,0,0,1,1)

Ich muss also alle alle möglichen 11 Tupel durchgehen, bei denen aber die Summe der Elemente 7 ergibt.
Entspricht grob dem Problem wie man 7 Bälle in 11 Fächer werfen kann (wobei hier die Reihenfolge wichtig ist!)


Wie löse ich das wieder?
Dazu habe ich eine recht logische Sache gefunden auf die man erst ma kommen muss:
Ich habe also 11 Boxen und 7 Bälle, die ich darin irgendwie verteilen muss.
Also kann ich hingehen und Bälle und Boxen in eine Reihe stellen dergestalt. dass die Menge an bällen zwischen 2 Boxen in die jeweilgie Box rehts kommt.
natürlich muss die 11. Box ganz rechts sein.
Daher betrachtet man das Problem dergestalt dass man guckt:
wie kann ich 11-1=10 boxen an (11+7)-1=17 positionen verteilen?

Um jede Möglichkeit 11 Boxen an je einer von 17 Positionen hinzusetzen, gehe ich alle möglichen Tupel durch.

Dies tue ich ähnlich wie bei einer 11 stelligen zahl,die ich von der kleinstmöglichen zahl ab immer um 1 erhöhe.
nur mit ein paar Einschränkungen:
das kleisnte Tupel ist ja
(1,2,3,4,5,6,7,8,9,10,11)

das größtmögliche Tupel ist
(6,7,8,9,10,11,12,13,14,15,16)

Anfangs setze ich mein tupel auf das kleisnte tupel.

der um eins erhöhen algorithmus geht dann ähnlich wie beim normalen addieren vor:
er guckt die 11te stelle.
ist sie kleiner als 16 (=11te stelle im max tupel), dann einfahc um 1 erhöhen.
geht das nicht, dann gehe zur 10ten stelle.
falls <15, erhöhen.
falls nicht geht, nächstniedrigere stelle.

Falls der Index hier <1 wird, abbrechen weil die Zahl schon max tupel entspricht und also nicht erhöht werden kann.

falls wir allerdings bei indexstelle c um 1 erjhöht haben, dann gehen hin und erhöhe die rechts davon befindlichen idnexstellen c+i um den wert i.
also die stelle direkt rechts um +1, 2 stellen rechts davon um +2 usw.

so in etwa.
So finde ich also alle 11 tupel im ltztgenannten sinne.
wenn ich nun also alle denkbaren positionen von 11 boxen an 11 möglichen orten habe (in form von passenden 11 Tupeln), dann kann ich diese ja,. unserem gedankengan hier rückwärts gehend, wieder in Tupel umrechnen die mir angeben wie viele kugeln in welcher box landen.
dies entspricht ja gerade der zwischenfrage wie oft jede zahl zwischen 1 und 11 vorkommt.

die häufigikeit jeder der zahlen 1-11 in meinem tupel zu wissen, reicht mir schon aus um die bedingung zu prüfen.
wird die bedingugn erfüllt, haben wir schon 1 güktiges tupel gefunden.
nun ist aber jede permutation(?) daovn auch eine lösung.

beschreibt nun unser tupel zum beispiel die lage dass
5 mal die zahl 3 und 2 mal die zahl 7 vorkommt, so müssen wir der anzahö an gültigen tupeln den ausdruck
7!/(5!*2!) hinzurechnen.

Im urnenmodell könnte mna das als "auf wie viele Arten kann ich 2 blaue und 5 grüne kugeln anordnen?" beschreiben.

insofern würden wir für dieses als gültig befundene tupel der gesamtzahl an gültigen tupeln den ausdruck 7!/(5!*2!) hinzuaddieren.


wenn fertig damit,. dann einfahc die gesamtzahl an gültigen tupels durch 11^7 teilen.

was dann die gewünschte wahrshceinlichkeit gibt :-)


klingt umständlich, ist es auch, hat keinen spaß gemacht zu progrmmieren, sollte aber hoffentlich funktionieren :-)
  ─   densch vor 4 Tagen, 19 Stunden

Ah ich sehe gerade ich habe die Boxen und Schachteln vertauscht. Also suchen wir alle Summen von 7 mit den Zahlen aus $\{0,1,2,3,4,5,6,7 \}$.
Ansonsten würde ich sagen ist unser erster Gedanke ja der selbe.
Das mit den Boxen und Kugeln macht für mich auf jeden Fall Sinn. Allerdings verstehe ich nicht warum $(1,2,3,\ldots , 10,11 ) $ das kleinste Tupel sein soll. Ich würde sagen ab jetzt kann man die Boxen und Kugeln als ununterscheidbar ansehen (weil die Anordnung der Kugeln angibt, wie viele drin sind und weil wir später noch die Permutationen betrachten). Würde es dann nicht eher Sinn machen beispielsweise die Boxen durch $0$ und die Kugeln durch $1$ darzustellen und dann wieder zu prüfen, wie viele Permutationen es gibt, wenn eine Box links bzw. rechts fest ist?
  ─   christian_strack vor 4 Tagen, 16 Stunden

Hier ist der Link wo das mit den Boxen und Kugeln vorkommt:
https://stackoverflow.com/questions/6508365/list-of-combinations-of-n-balls-in-m-boxes-in-c

Wie gesagt, die ursprünglich zu feinden Tupel sind ja sowas wie (1,11,2,3,11,7) oder so.
Weil es die von mir betrachtete Bedingung herkommt, reicht es wenn ich bei diesem Tupel nur gucke welche Zahl wie oft vorkommt (muss eben am ende berücksichtigen dass ggbfls. andere Anordnungen dieser Zahlen auch zutreffend sind)
Also schreibe ich das als Tupel wo die ite Stelle angibt wie oft die Zahl i vorkommt.

Tupel dieser Art haben eben die Besonderheit dass ihre Zahlen von 0-7 gehen und die Summe alller Elemente 7 ist.

Womti wir beim ball Box Problem sind.
Gegeben 11 Boxen, 7 Kugeln. Und ich verteile die Kugeln irgendwie auf die Boxen, dann kommt ein tupel raus, das eben erwähntem Tupel entspricht.
Oder so. ist einfahc nur sch.. ztu erklären das Ganze.
Jedenflls sind das Boxenproblem und das Tupelproblem mit den elekemtnsumme=7 äquivalent.

wenn die kugel verteilt sind und ich schreibe mir die 11 boxeninhalte als tupel hin, kommt gerade ein tupel mit den gewünschtne eigenschaften raus.

um nunin irgendeiner sinnhaften Art und Weise das mit den boxen durchzugehen, mache ich eben den Trick mit der Aneinanderreihung von kugeln und Boxen.

Und um es programmiertehcnishc einfacher zu machen, frage ich mich nur an welcher der 17 Positionen die 10 Boxen sind (alle anderen stellen sind dann zwangsläufig kugeln.)

Klar könnte man die 16 positionen auch durch 0en und 1en darstellen.
Aber wie geht man da dann systematisch wieder durch sodass genau 11 mal die 1 vorkommt?
Ist ja dann ziemlich gleich dem problem oben wo wir 7 kugeln in 11 boxen verteilen wollten und uns daher zu diesem Umweg entschieden haben.

Ich habe das hier nur so gemacht um das auch programmiert zu bekommen.

letztlich baue ich mir ein 11 tupel, schön aufsteigend sortiert, mit zahlen zwischen 1 und 17.
weil fakt ist, jede box kann nur an einer der 17 positionen sein und keine position kann von 2 boxen belegt werden (was eingangs mit unseren uzahlen nicht so war, da konnte 7 mal die 1 vorkommen)

darum ist es nur eine frage 1 verschiedene zahlen aus der menge 1-17 zu nehmen.

und alle kombinationen hierfür kriege ich durch stupides hochzählen.

Die wortwahl "kleinstes tupel" habe ich nur dher gewählt weil darin eben die kleisntmöglichemn zahlen aus 1-16 vorkommen.
Weil irgendwo muss man ja mal anfangen.
(1,2,3,.....,10) beschreibt eben die anordnung dass von links nahc rechts 10 boxen kommen , dann 7 kugeln und die letzte (programmiertechnisch unsichtbare) box.
rückverwandelt beschreibt das dann das tupel
(0,0,0,0,0,0,0,0,0,0,7)
welches widerum beschreibt dass 0 mal die 1, 0mal die 2, etc. 0 mal die 10 und genau 7 mal die 11 vorkommt.

kurzum, unsere variabeln a-g haben alle den wert 11.

so im prinzip ist es aufgebaut.
Nur da beim programmieren noch den DUrchblick zu behaltne ist hart. Und wird auch nicht besser dadurch dass arrays in java mit index 0 beginnen und daher die indexstellen statt 1-11 dann 0-10 sind und so :-/


Aber programmiertechnisch gehe ich erst alle möglichen boxenpositionetupel durch, werfe jedes dieser tupel in eine "process" methode, die für dieses spezielle tupel das rückumwandelt in das ausgangstupel wo die häufigkeit jeder der zahlen 1-11 damit beshcrieben wird, prüft ob damit die bedingung erfüllt wird.
und falls erfüllt, ist das der methode üergebene tupel gut und daher geht der gesamtcounter hoch.
um genau 7!/(fakultäten der einzelnen werte).


musste mir für den spaß auch eine eignee potenzmethode, fakultätsmethode und array-ausdrucen-methode bauen. weil bspw. math.pow nicht damit klar kommt wenn die basis eine kommazahl ist -.-
  ─   densch vor 4 Tagen, 15 Stunden

Ja das was auf Stackoverflow zu den Boxen und Bällen steht habe ich verstanden und es eine geniale Idee. Die Tupel die danach folgen habe ich missinterpretiert. Ich verstehe jetzt was du meinst.
Ich kann dir leider nicht viel zum programmieren sagen.
Wenn ich dich aber richtig verstehe, geht es dir um die Anzahl aller möglichen Kombinationen und nicht um eine Liste, die alle diese möglichen Tupel erzeugt oder?
Dann ist die Lösung aber viel einfacher.
Wir haben durch den Trick mit den Kugeln und den Boxen insgesamt 17 Positionen die variabel sind (die Box ganz rechts ist ja fest). Wenn wir von 17 unterscheidbaren Objekten die Anzahl aller Permutationen bestimmen, erhalten wir 17! ([Anzahl Kugeln + Anzahl Boxen -1]!)
Nehmen wir mal an, die Kugeln wären beschriftet. Nun macht es denke ich für deinen Fall keinen Unterschied, wenn in der ersten Box die Kugel 1 ist und in der zweiten der Rest oder ob in der ersten die Kugel 2 ist und in der zweiten wieder der Rest. In beiden Fällen ist in der ersten Box eine Kugel und in der zweiten sind 6. Sehe ich das richtig? Falls es einen Unterschied macht, solltest du mit 17! bereits fertig sein.
Wir können uns wieder die Anordnungen der Boxen und Kugeln angucken. Da es egal ist, welche Kugeln in welcher Box sind, müssen wir noch alle möglichen Permutationen der Kugeln berücksichtigen. Das machen wir, indem wir dadurch teilen. Da wir 7 Kugeln haben, können die Kugeln 7! mal vertauscht werden. Also haben wir insgesamt $\frac {17!} {7!} $ Möglichkeiten.
Diese Formel $\frac {n!} {k!}$ findet man auch, wenn man sich Permutationen mit einer Gruppe von Objekten anguckt, die identisch sind (Permutation mit Wiederholung).
  ─   christian_strack vor 4 Tagen, 13 Stunden

Doch, um die TUpel selbst geht es mir.
Weil ich für jedes Tuel prüfen muss ob es eine bestimmte Bedingung
(Also stark verinfacht geredet, wenn (a,b,c) das Tupel wäre, würde ich prüfen ob bspw. a+2b+0.3c>4. Nur wenn das Tupel auch diese Bedingung erfüllt, sit es relevant und die Zählervariable wird um eins erhöht. Daher sind die Tupel an sich für mich wichtig, nicht nur deren Anzahl. Daher habe ich das Problem ja dass ich jedes einzelne Tupel durchgehen muss und gucken muss ob es die Bedindung erfüllt. Klar könnte ich hier auch mt 7 Schleifen einfahc alle Tupels die möglich sind, durchgucken. Aber ich hoffe zumidnest das smein Algorithmus da effizienter sit au die eine oder andere Art. Vor Allem ist er, insofern ich ihn mal noch so anpasse dass 7 und 11 nicht fest vorgegeben sind, sondern bspw. beim programmaufruf als input eingegeben werden, hoffentlich unabhängiger.
Weil würde ich bspw. ein 15 Tupel, wo die zahlen aus 1-30 sind, machen wollen, müsste ich 15 shcleifen "hard coden" (was den code unflexibel macht) und müsste zudem auch 30^15 Tupel durchgehen, was Leistungstechnisch eventuell schwer wird für den Computer. Sprich ich will es so effizient wie möglich halten damit möglichst nur Tupel betrachtet werden die in Frage kommen. Und so wenig wie nötig geprüft werden muss)
  ─   densch vor 4 Tagen, 9 Stunden

Puuh ok. Was ist denn die genaue Eigenschaft? Ich weiß nicht ob ich dabei noch helfen kann, denn wie gesagt bin ich nicht sonderlich bewandert was programmieren angeht.   ─   christian_strack vor 3 Tagen, 18 Stunden

Also programmiertechnisch habe ich was gebaut was, hoffentlich, auch funktioniert.
Würde es an sich auch gerne hier Posten, habe aber keine Ahnung wie am Besten :-/
  ─   densch vor 1 Tag, 9 Stunden

Zur Bedingung:
Sowas wie (1+a)^a*(1+b)^b*(1+c)^c*(1+d)^d*(1+e)^e*(1+f)^f*(1+g)^g>10 oder so.
mein beispiel ist zwar etwas anders, aber hat das selbe prinzip.
Vor Allem die Eigenschaft dass ich links vom > Zeichen die "Reihenfolge" vertauschen kann ohne dass sich das Ergebnis ändert.
Also wenn ich bspw. (a-g)=(1,1,1,1,1,3,1) und (1,3,1,1,1,1,1) habe, dann sind das 2 verschiedene Tupel , müssen daher auch als 2 Tupel betrachtet werden.
Tatasache ist aber dass der Ausdruck auf der linken Seite wegen kommuntatitität und so genau das selbe Ergebnis bringt und daher wird auch von beiden die Bedingung erfüllt.
Kurzum: Habe ich das Tupel(1,1,1,1,1,3,1) betrahctet und herausgefunden , dass dieses die Bedingung erfüllt, dann erfüllen auch alle Vertquchungen (nennt man das Permutationen?) heirvon die Bedingung ohne dass die separat grprüft werden müssen.
Habe icbh also das gültige Tupel (1,1,1,1,1,3,1) gefunden, so habe ich insgesamt 7!/(6!*1!) (weil eben 6 einsen und 1 drei) gültige tupels gefunden.
Mein hübscher counter wird also um den wert erhöht und es geht zum nächsten "unique tupel" (welches also nicht nur eine permutation von was shcon betrahctetem ist).

Damit erspare ich mir (hoffentlich) einiges an computerrechenaufwand wenn ich diese eigenschaft ausnutze :-)

Nur das aufzählen ist ein problem denn:
Praktisch kan ja eine zahl mehrfahc vorkommen (die 1 kommt hier ja gleich 6 mal vor!)
Daher arbeite ich nicht direkt mit den einfachen tupeln, sondern frage mich:
ich habe 7 variabeln, mit den möglichen werten 1-11.
eigentlich reicht es ja zu betrachten, bei einem bestimmten tupel, wie oft die zahl 1, wie oft die 2, etc. vorkommt.
Diese einzelhäufigkeiten zusammen müssen halt wieder 7 ergeben.

Und nun in einem 11 tupel, dessen elemente in summe 7 ergeben müssen, alles durchzuzählen, mahce ich das mit den boxen und kugeln :-)

also 10 boxen (weil eben die 11. box immer ganz rechts ist, die hat keine freiheiten in dem sinne) und 7
kugeln.
Also auf welche arten kann man 10 boxen an 17 möglichen positionen platzieren?
hierzu baue ich mir ein 10 tupel wo jede stelle die position einer box angibt.
jede position sit einzigartig, also kommt in dem zehntupel jede zahl nur einmal vor.
10 zahlen ziehen ohne zurücklegen aus einem zahlenool 1-17. oder so.

DA lassen sich ale kombi simpel durhczählen und hochzählen.
von (1,2,3,4,5,6,7,8,9,10) bis zu (7,8,9,10,11,12,13,14,15,16,17).

so ähnlich läuft der algorithmus.
er geht letztlich alle box-positions-tupel durch, wandelt es dann in das tupel um das angibt wie viel kugeln zwischen linker wand-boxen-rechter wand liegen, wandelt das dann in das "wie oft kommt die zahl 1,2,2,...,10,11 vor, wobei summe=7" tupel um und nutzt die dort gegebenen zahlen direkt in der bedingung oben.

So in der Art läuft das in dem programm bzw. sollte es zumindest :-)
  ─   densch vor 1 Tag, 8 Stunden

Und was ist das eigentliche Ziel?

Ein Tupel ist übrigens so definiert, dass $(1,2)\neq (2,1)$ ist. Es ist also geordnet.
  ─   cauchy vor 1 Tag, 8 Stunden

Am Ende vom lied gehts mir drum die Frage zu klären, wenn ich eine Geldanlage habe, bei der nahc einem festen zeitraum das Grundkapital plus ein random betrag (der aber innerhalb bestimmer Grenzen ist, also diskrete Werte hat, gleichverteilt, blabla. Sagen wir eine der zahlen 1-11 eben) wieder zurückkommt,
wenn ich da einen geldbetrag nehme und den 7 mal reinstecke (investiere und reinvestiere),
mit welcher Wahrscheinlichkeit wird das, was rauskommt , größer als bspw. das 2 fache des Startkapitals sein?

ich gehe dabei daovn aus dass bei jeder INfestmentrunde der "Randomfaktor" eben random ist und unabhängig bon Vergangenheit und zulkunft.
darum nenne ich die 7 multiplikatoren in den 7 investmentsrunden a,b,c,d,e,f,g.

Im Prinzip könnte ich mir einfahc alle 11^7 tupel bilden, gucken für jedes einzelne ob das resultat größer ist und die anzahl an passenden tupeln durch 11^7 teilen um meine Wahrshcienlichkeit zu kriegen.

Da 11^7 schon goß ist und, wenn ich die anzahl an investmentrunden und den zahlenraum 87 und 1-11 in unserem beispiel) erweitere, habe ich da lächelrich viele Kombinationen und da streikt irgendwann der Computer.
Daurm will ich das intelligent angehen und beim tupelbilden und berechnen so wenig redundanz wie möglich machen.
Einfacher schritt dabei sit eeben die kommutativität auszunutzen :-)
  ─   densch vor 1 Tag, 8 Stunden

Kommentar schreiben

0
Mit Hilfe der Überlegungen aus den Kommentaren lässt sich allgemein der Ausdruck $$\binom{k+n-1}{n-1}$$ herleiten, wobei $n$ die Anzahl der Boxen (unterscheidbar) und $k$ die Anzahl der Kugel (nicht unterscheidbar) ist.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 14.91K

 

Aber haben wir hier nicht einfach eine Permutation mit Wiederholung (wie in meinem letzten Kommentar)? Warum wird zusätzlich noch durch $(n-1)!$ geteilt?
  ─   christian_strack vor 4 Tagen, 13 Stunden

Gut möglich. Die Formel mit dem 7!/(5!*2!) oder sowas stammt aus den Geschichten mit dem urnenmodell, mit ohne Widerholen und Reihenfolge.
kein Plan, welcher Fall das nochmal war, habe die Formeln rein durch Googeln gefunden. passt halt wenn man bspw. die Anzahl an Anordnungen will um 2 grüne und 3 blaue Kugeln anzuordnen.

Was Stochastik angeht, bin ich echt nicht auf dem Laufenden. Habe das in der Schule shcon nicht gemocht, Alles was über simple Wahrscheinlichkeiten a la Baumdiagramm hinausging mit irgendwelchen varianzen und "die Wahrshceinlichkeit dass in X% der Fälle über 97% der Fälle oberhalb von Mittelwert und Varianz liegen" und ähnlicher Quatsch waren mir zu blöd weil man sich da Kram zusammenrechnet der iN Realität durhc blanken zufall eh über den Haufen geschmissen wird.
Alles was über einfache Wahrsheinlichkeiten hinausgeht, sit meiner Meinung nahc mehr Esoterik und Rechnerei "just for the sake of it".

Während Analysis und Algebra da besser sind, klare Regeln, klares Ergebnis.
Da kommt hchstens was Anderes raus wenn man sich verrechnet hat.

Aber das ist jetzt eigentlich auch abseits vomThema, jedenfalls habe ich dadurch nur bedingt aufgepasst bei Stochastik in der Schule, geschwiegedenn weiß ich irgendwaswas über Schulstochastik hinausgeht :-)

Nach gut 10 jahren ist das bisschen Stochastikrestwissen auch ziemlich verkümmert und muss ergoogelt werden :-)
  ─   densch vor 4 Tagen, 9 Stunden

Der Ausdruck $\frac{7!}{5!\cdot 2!}=\frac{7!}{5!(7-5)!}=\binom{7}{5}$ gibt ja gerade die Anzahl der Möglichkeiten an, aus einer Menge von $7$ Elementen $5$ auszuwählen.
  ─   cauchy vor 4 Tagen, 9 Stunden

Zur Erläuterung der Formel in meiner Antwort: Wir stellen uns einfach vor, dass die Kugeln in einer Reihe liegen. Eine Box wird dann durch einen Querstrich zwischen den Kugeln gekennzeichnet. Durch die Anordnung der Kugeln und Striche erhält man dann die Aufteilung der Kugeln in die Boxen. Um also $n$ unterscheidbare Boxen zu modellieren müssen nur $n-1$ Striche eingefügt werden. Wir haben also insgesamt $k+n-1$ Objekte, $k$ Kugeln und $n-1$ Striche, für die $n$ Boxen. Da wir nur die Striche entsprechend anordnen müssen, müssen wir für diese also $n-1$ Positionen auswählen und erhalten somit den obigen Binomialkoeffizienten.   ─   cauchy vor 4 Tagen, 8 Stunden

kann sein. womit in meiner Aufgabe das Ganze ja nicht zwingend auf nur Kugeln mit 2 Farben aufgeteilt ist.

es kann auch 2 grüne, 2 rote, 1 blaue und 2 pinkne sein.
dann ist es entsprechend 7!/(2!*2!*1!*2!).
Ob das auch noch der Binomialkoefizient hergibt weiß ich nicht :-)
  ─   densch vor 4 Tagen, 3 Stunden

Wo kommen denn jetzt die verschiedenen Farben her? Das stand doch gar nicht zur Diskussion.   ─   cauchy vor 4 Tagen, 3 Stunden

Ich will das von dir nicht anzweifeln Cauchy, denn für Kombinatorik hatte ich immer mitunter die wenigste Intuition. Aber ich habe das Gefühl dass wir hier eine Permutation haben, die 2 Gruppen beinhaltet, von der eine Gruppe nicht-unterscheidbare Objekte beinhaltet (die Kugeln). Also haben wir eine Permutation mit Wiederholung in einer Gruppe. Wenn ich bei Wikipedia gucke, steht dort die Formel $\frac {n!} {k!}$ wobei $n$ die Gesamtzahl ist (hier also Kugeln + Boxen -1) und $k$ die Größe der Menge mit den nicht-unterscheidbaren Objekten (hier also die Kugeln).
Ist das nicht gerade der Fall den wir hier haben? https://de.wikipedia.org/wiki/Permutation#Permutation_mit_Wiederholung
  ─   christian_strack vor 3 Tagen, 18 Stunden

Wenn du die Striche (wie oben beschrieben) anordnest, sind die Striche ja ebenso nicht mehr unterscheidbar (ich kann die Striche ja beliebig vertauschen) Das, was unterscheidbar ist, ist die Tatsache, dass die Kugeln zwischen Strich 2 und 3 beispielsweise die Kugeln in Box 3 bezeichnen. Aber die Striche an sich sind nicht unterscheidbar. Insofern gilt nach deiner Formel bei $k+n-1$ Objekten, wovon einmal die $k$ Kugeln identisch und einmal die $n-1$ Striche identisch sind gerade (Permutation mit Wiederholung) $$\frac{(k+n-1)!}{k!(n-1)!}.$$ Man kann jetzt aber leicht nachrechnen, dass dieser Ausdruck mit dem obigen Binomialkoeffizienten übereinstimmt. :)   ─   cauchy vor 3 Tagen, 14 Stunden

Ach stimmt die Boxen sind ja auch nicht unterscheidbar. Dass war das was mir die ganze Zeit gefehlt hat :)   ─   christian_strack vor 3 Tagen, 9 Stunden

Vorsicht. Die Boxen sind unterscheidbar. Es macht einen Unterschied, ob ich sage, die Kugeln sind in Box 3 oder in Box 5. Aber die Modellierung mit Hilfe der Striche (als neue Objekte) macht die Striche unter sich natürlich nicht unterscheidbar. Nur die Zwischenräume, die dann jeweils den Boxen entsprechen, sind unterscheidbar, sind für die Berechnung aber nicht weiter relevant.   ─   cauchy vor 3 Tagen, 8 Stunden

Ja so hatte ich es auch verstanden. Ob in Box 3 oder 5 die Kugeln sind wird ja dadurch unterschieden, dass die Kugeln an einer anderen Stelle sind. Und genau deshalb hatte ich dsa auch nicht auf dem Schirm. Danke :)   ─   christian_strack vor 2 Tagen, 21 Stunden

hier scheint es etwas chaotishc zuzugehen da alle möglichen Sachen durcheinander kommen.
Am Ende kommt es drauf an bei einem gegebenen 7 tupel (wie bspw. (1,2,1,7,5,1,9) nur drauf an wie oft die zahl 1, wie oft die zahl 2, ..., wie oft die zahl 11 vorkommt. Weil meine zu prüfende tupelbedingung gwissermassen "kommutativ" und ein vertauschend er zahlen das erfüllen der bedingung nicht beeinflusst)
Die summe der häufigkeiten muss natürlich 7 betragen weil duh.

nehmen wir also für jede der zahlen 1-11 eine box und für jede der 7 variabeln eine kugel, dann ignorieren wir zuerst mal eine box, weil wir die 11. box per definition immer ganz rechts hinstellen.
und die restlichen 10 boxen sollen auf (10+7)=17 mögliche positionen verteilt werden. wobei keine 2 boxen die selbe position haben können trivialerweise.
Natürlich kann man nun für eine bestimmte anordnung die 10 boxpositionen in einem 10 tupel aufschreiben wo die ite stelle angibt auf welch der 17 positionen sich die ite box befindet.


ich habe übrigens mittlerweile ein programm fertig, welches hoffentlich das gewünscht berehcnet. Kann man das hier irgendwie hochladen oder so?
  ─   densch vor 1 Tag, 8 Stunden

konkret: welche box wo steht ist sehr wichtig.
die kugel hingegen sind vertauschbar da am ende vom lied nur wichtig ist wie viele kugeln sich bspw. zwischen box 2 und 3 befinden.


  ─   densch vor 1 Tag, 8 Stunden

Der, der hier für Chaos sorgt, bis wohl du selbst. Was genau ist jetzt das Ziel? Möchtest du alle möglichen Verteilungen haben oder geht es dir nur um die Anzahl der möglichen Verteilungen?   ─   cauchy vor 1 Tag, 8 Stunden

Immer noch die Vrteilungen selbst.
Anzahl der Tupel ist einfach 11^7, das wäre ja auch easy zu machen :-)
  ─   densch vor 1 Tag, 8 Stunden

Die Anzahl ist nicht $11^7$, da ja viele davon gar nicht relevant sind.

Ich weiß nicht, mit welchem Programm du arbeitest, aber viele Programmiersprachen bieten es bereits an, sämtliche Permutationen einer Menge auszugeben.
  ─   cauchy vor 1 Tag, 8 Stunden

Java.
Wenn ich 7 Variabeln habe und jede davon 11 mögliche Zahlen annimmt, sind es 11^7 verschiedene Tupel.

Wie viele davon natürlich meine willkürliche Bedingung erfüllen, werde ich wohl nicht rausfinden ohne sie der Reihe nahc durchzutesten :-/
  ─   densch vor 1 Tag, 6 Stunden

Wie viele es sind, steht genau in der obigen Formel. Daher frage ich ja, ob du wirklich alle Tupel brauchst oder dich nur die Anzahl interessiert. Wären in deinem Fall 19448 Möglichkeiten.   ─   cauchy vor 1 Tag, 6 Stunden

wie komsmt du auf die zahl? :O   ─   densch vor 1 Tag, 3 Stunden

Formel steht oben und habe ich in einen der Kommentare erläutert.   ─   cauchy vor 1 Tag, 2 Stunden

hm, macht eigentlich sinn.
10 boxen und 7 kugeln. kugeln sind vertauschbar, boxen hingegen nicht. Dass es dafür eine simple Formel gibt, macht eigentlich schon Sinn :-)

Vermutlich zeigt sich da meine Unkenntnis aber müsste eigentlich die ANzahl an Kugel Boxen Anordnungen nicht über 17!/7! bestimmbar sein?
weil kugeln+boxen=17 (die 11. box ignorieren wir ja wie schon erwähnt).
und wir haben halt 10 einzigartige boxelemente sowie 7 identische kugelobjekte, insofern müsste es
17!/(7!* 1!^10) sein, was sich zu 17!/7! verienfacht.
Oder denke ich da mal wieder verkehrt? :-)
  ─   densch vor 14 Stunden, 56 Minuten

Du liest meine Kommentare nicht. Auch das hab ich dem Christian bereits erläutert. Wenn man die Boxen als Striche identifiziert, sind sie untereinander wieder austauschbar, weshalb man zusätzlich noch durch $10!$ dividieren muss. Das liefert dann aber wieder den von mir bereits erwähnten Binomialkoeffizienten. Schau da nochmal in die obigen Kommentare.   ─   cauchy vor 12 Stunden, 38 Minuten

Kommentar schreiben