Unterscheidbare Bälle in unterscheidbaren Urnen bestimmter Größe

Neue Frage »

PeterMuellerr Auf diesen Beitrag antworten »
Unterscheidbare Bälle in unterscheidbaren Urnen bestimmter Größe
Angenommen, wir haben unterscheidbare Urnen der Größe Bälle je Urne und unterscheidbare Bälle. Auf wie viele Arten lassen sich
  1. alle Bälle auf die Urnen verteilen,
  2. höchstens Bälle auf die Urnen verteilen?

Die Reihenfolge, in der die Bälle eingelegt werden, spielt keine Rolle.

Anmerkung. In meiner Anwendung gilt ; diese Voraussetzung könnte hypothetisch helfen.
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? verwirrt
PeterMuellerr Auf diesen Beitrag antworten »

@HAL 9000 Ja. Maximal Bälle je Urne.
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

.
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?
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.
 
 
PeterMuellerr Auf diesen Beitrag antworten »

Ungefähr b=14000, m=100, u=5700.
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.

------------------------------------------


Zitat:
Original von PeterMuellerr
Ungefähr b=14000, m=100, u=5700.

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. unglücklich
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. .
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 .
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »