Unterscheidbare Bälle in unterscheidbaren Urnen bestimmter Größe |
08.11.2021, 19:14 | PeterMuellerr | Auf diesen Beitrag antworten » | ||
Unterscheidbare Bälle in unterscheidbaren Urnen bestimmter Größe
Die Reihenfolge, in der die Bälle eingelegt werden, spielt keine Rolle. Anmerkung. In meiner Anwendung gilt ; diese Voraussetzung könnte hypothetisch helfen. |
||||
08.11.2021, 19:31 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Deine Formulierung ist nicht zweifelsfrei deutlich, daher meine Nachfrage: Soll "Urne der Größe " bedeuten, dass maximal Bälle in die Urne passen? |
||||
08.11.2021, 19:51 | PeterMuellerr | Auf diesen Beitrag antworten » | ||
@HAL 9000 Ja. Maximal Bälle je Urne. |
||||
08.11.2021, 20:25 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Hmm, ich fürchte, das wird in keine einfache Formel münden: Man summiert über alle Tupel von ganzen Zahlen mit Summe sowie die Anzahl . Ohne die Beschränkung kommt einfach heraus, aber mit... Beim gleichen Problem mit ununterscheidbaren Bällen kommt man noch mit einer einfachen Summe aus, nämlich . Aufgabe b) kann man in ähnlicher Weise wie a) lösen, indem man eine fiktive -te Urne hinzunimmt - welche keine Größenbeschränkung (wie bei den anderen Urnen) aufweist - die dafür gedacht ist, die "Restbälle" aufzunehmen, welche in den ersten Urnen keinen Platz gefunden haben. Bei ununterscheidbaren Bällen wäre hier dann die Lösungsanzahl . |
||||
08.11.2021, 21:15 | PeterMuellerr | Auf diesen Beitrag antworten » | ||
Ich verstehe. Wie geht man denn alle solche Partitionen, also alle Tupel von nichtnegativen ganzen Zahlen mit Summe sowie () programmatisch am besten durch? |
||||
08.11.2021, 21:49 | HAL 9000 | Auf diesen Beitrag antworten » | ||
In welchen Größenordnungen bewegen sich denn bei dir? Könnte wichtig sein für die Frage, ob es überhaupt Sinn macht, das algorithmisch anzugehen. |
||||
Anzeige | ||||
|
||||
08.11.2021, 21:52 | PeterMuellerr | Auf diesen Beitrag antworten » | ||
Ungefähr b=14000, m=100, u=5700. |
||||
08.11.2021, 21:58 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Oje, verdammt groß - und es geht WIRKLICH um unterscheidbare Bälle??? Man kann den Summationsaufwand weiter vermindern: Es genügt -Tupel mit zu betrachten, wenn man die Anzahl zusätzlich noch mit der Anzahl der Permutationen von multipliziert, das ist nun gerade , wobei die auftretenden Vielfachheiten unter den Zahlen angeben. Wie man das algorithmisch organisiert? Ja, herausfordernd, aber mit etwas eigener Mühe möglich. ------------------------------------------
Zur Überbrückung hier schon mal die Anzahl bei ununterscheidbaren Bällen, gemäß der oben angegebenen Formel 92049581910728288379464381735383706922715570668083206263908833822060303867 58060004769052329119361620827810207778164748185515579378790601152434089336 89484776791046992683866205867086329111941994819248693486446727640635228848 80859858194200064535101223309775535563869619197123711921699441656775627571 74045971837785328979570812264293169125790022237385234203911755104665258434 41291599891299483851595659426406479358885988828130760373373475741217872380 43129355314221700430412062115529660795889835596517679185358722810430436462 78357593382517189053631241315254354388361376061794287547378627851694663803 02055176007384988867283680117045319198291709017823889609100077084463463166 55347648677961157774473603025880583666413808754420683757754250276687680573 68370930296363918310119003624276700082546897276909466698892721895118566644 90489486379329242000178776566568622105979122112447918854126659850019997214 43297530424544979624140390666636708523143053929906996095626505108476457319 03488743865169876112591407665405837092128468640153809406236994022745110550 13884201742057405157619430685218637100085555120594375117380927199497066944 14514593259654288431907209102961412121280212175546933241926973497866069575 82287186392718471887857347261545219878089766728519670794047256987923894355 52117045010635130467527068879615086940756052952577489939364391250868156457 79611048876649593982477132178748199218309104292359069825992230160573041608 06371555901599211365090425065877538699820858586335085989398248566244088890 98231412146767018029680897279812815976672158087692116612270302290301067219 32080851164590951320598443376655982902770375136479036508033927045360581800 82266384278122728474019196758465290969466594043092714402844859567085132074 49908443449434018882269090989308976470473734408522516251790882564358898480 81669514846853287694686233218417349573807979327484067043881186050526870920 71748767575268805544483150713932815167200482405841815686152721690787773792 95525722433864742651979575942167478537393003188381912487812902967598420144 50119466384193059473588069809135777886775836025084391587544449233118830562 47381936945260896030719309341557626115988026090305764152094128412832353007 06803945807719755772750903613715745268701467704246440867550461081798571701 98025162351323729905974381540425010426289956462044434747359940413706213677 72985998820803611213977061063103620609724167654172603617798940674408477673 73218763452419984242558060688655849060028671053051964719465035512322557355 52979370995248223303204186081352495891623793365095737994214647382667639586 29434649779577873098155931580337237055575870458007752305882230073408462620 16682265747824271792836839857674180511365060094645521497966850105336321795 69115755366528416449881770334342677027168137945250723702735393433181878401 84767608448145290036898481701362448777221661093344256207677997322900866730 68710539235344196230050748921309972941329333457260813757030751235668443729 07439783775961789478052306581104617060772263845251964153064731036954035797 26495927800469937162374307314026999042888275275017688678731765421062292856 58461881563355965856971439687211774202083948415371794987638122576043414333 25261639699267611113113258080826638464777482848439332787500049351433321831 43367221995577464763883078382146534102758336967777760682604165577062111155 75205548760315259193081104258150046451501954439840856162807148392712277820 17021518793562863397585299792334020303584848285512636334198674251641126946 33734026088804243879688816123634682860356021653615937715170642363517329345 80118205055696507091438471984567382747993096844905106661690083384861068887 68299633247772117823377691292340840584086809780992680548398467910726593106 20444737053942235805302784242089414556697877920818747966791340463530428692 76737928157488855559235753109636831472874544662145217097334562611649112618 00382750449935047045107697244918627904327690424201869414289831473593482116 39077173329876991063427373123056941589394462143179980824353620686674710712 59896547197440686055487697744618525858915586736832925550756782559414533906 43332836332841234384170959442155217077828133775749148883983299411462924512 73598674548518598495091135534484366986954569446538111629784857456349022936 50578037960638071412099089386033000780376093878381654463103494109638670607 30184258932652518894676732847777506015184577340123994945951297649121624319 57945386920752253233659857632231251941406538139952415994942482337130952951 28568966019621213220906961898084188723160089177127291946495567519522439491 15023362842746566589062831390299436079226470767931466564122738438116796690 00799359103670609287410483355376130765422724074568805341656620321442160355 61005093926492021337131528992638982565230732124603207571864525331043843439 63276705638669955985989701199901225062355605004406879979241080916578553933 64509813137599857897609816407931714037516889680749740292579982915354704114 90606469252623991419218993965363416815239933327982506950532459154254380325 64928402085038706824807076335258707129124487148943519496357766009755228474 33383952962858134979286142285651799351092783096337854286278292911556762232 67155177794874921964713413433546520312274262156420445761093035627765935597 09265619307346864279851933375623354932 Und leider ist das auch die Fallzahl, über die man ohne weitere Maßnahmen im Fall der unterscheidbaren Bälle summieren müsste - undurchführbar. |
||||
09.11.2021, 04:11 | PeterMuellerr | Auf diesen Beitrag antworten » | ||
In meiner Anwendung geht es um etwas anderes als Bälle, aber die genaue Problemstellung ist zu spezifisch und würde uns zu weit führen, hier also unerklärbar. Lass uns einfachheitshalber über unterscheidbare Bälle und unterscheidbare Urnen wie immer reden. Ja, unterscheidbare. Ja, ich sehe, dass die Zahl astronomisch groß wird. Das ist sehr gut; das erwartete ich auch irgendwie. Die Frage ist nun: wie groß? Eine gute untere Schranke oder eine Approximation der Form wäre nicht schlecht. Dabei darf man einen Fehler von, sagen wir, maximal in begehen, also, z.B. . |
||||
09.11.2021, 07:57 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Naja, eine obere Schranke habe ich ja genannt: , das ist einfach die, wenn man die Urnengröße ignoriert. Ist vermutlich auch gar keine so schlechte Schätzung für die Gesamtanzahl bei deiner speziellen Parameterkombination, da dort die durchschnittliche Urnenbelegungszahl weit unterhalb der Urnengröße liegt: , eine stolze Anzahl. ------------------------------------------------------------- Machen wir doch eine einfache Abschätzung auch nach unten: Sei ... Menge der Konfigurationen, wo Urne mehr als Bälle enthält. Dann ist Wegen kann man dann deine gesuchte Anzahl insgesamt eingrenzen durch . Hab es mal vom CAS durchrechnen lassen: Für ist , d.h. um ca. 118 Zehnerpotenzen niedriger als unser . Folglich kann man getrost sagen , und für das von dir gesuchte mit gilt dann . Aufgabe b) mit "höchstens" Bällen ändert kaum was am Szenario: Hier ist dann , also ca. 12mal mehr Möglichkeiten als bei a). P.S.: Bedenklich wird diese simple Approximation "ignoriere " erst dann, wenn dieses größenordnungsmäßig an heranrückt: Für statt 100 bekommen wir bereits , also ungefähr 30% des Wertes von . |
||||
09.11.2021, 16:12 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ich hab mal noch etwas Energie in die Abschätzungen für den Fall reingesteckt: Wir waren oben bei mit Das sind verdammt viele Binomialkoeffizienten mit großen zu berechnen, da muss sich ein genau rechnendes CAS ganz schön abplagen, und die meisten Summanden tragen fast nichts bei zur Summe. Daher schätzen wir mal geeignet ab: Für gilt , d.h., im Fall können wir abschätzen Das bedeutet insgesamt: Gilt , so können wir die gesuchte Anzahl abschätzen gemäß . Wem auch noch der Binomialkoeffizient mit dem großen ein Dorn im Auge ist, der kann auch noch etwas grober via dann abschätzen . Selbst die "grobe" Abschätzung ganz am Ende genügt vollkommen, um das gesuchte im Parameterfall auf mehr als 100 führende Stellen genau einzugrenzen. EDIT (10.11.21): Da Peter Muellers Anforderungen nun mehr als deutlich erfüllt worden sind, hätte ich mir schon noch eine kleine Rückmeldung gewünscht. Naja, dann eben nicht. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |