Heute Abend nahm mich meine Verlobte zum Abendessen mit, um meinen Geburtstag zu feiern. Während wir unterwegs waren, hörte ich Happy Birthday vor 5 verschiedenen Gästen (einschließlich mir) in einem Restaurant mit 50 Personen. Das hat mich gewundert - das ursprüngliche Geburtstagsproblem (Finden der Wahrscheinlichkeit, dass zwei Personen in einem Raum Ndenselben Geburtstag haben) ist sehr einfach und unkompliziert. Aber wie sieht es aus, wenn die Wahrscheinlichkeit berechnet wird, dass mindestens keine NPerson denselben Geburtstag hat?

Falls Sie sich fragen, beträgt die Wahrscheinlichkeit, dass mindestens 5 von 50 Personen denselben Geburtstag haben, ungefähr 1/10000.

Die Herausforderung

Gegeben zwei ganze Zahlen Nund k, wo N >= k > 0, die Wahrscheinlichkeit, dass mindestens ausgebenk eine Gruppe von NPersonen denselben Geburtstag hat. Um die Dinge einfach zu halten, nehmen Sie an, dass es immer 365 mögliche Geburtstage gibt und dass alle Tage gleich wahrscheinlich sind.

Für k = 2diese auf die ursprüngliche Geburtstags Problem siedet, und die Wahrscheinlichkeit ist 1 - P(365, N)/(365)**N(wo P(n,k)ist die Anzahl der k-Länge Permutationen aus n Elementen gebildet ). Für größere Werte kkann sich dieser Wolfram MathWorld-Artikel als nützlich erweisen.

Regeln

• Die Ausgabe muss deterministisch und für die von Ihnen gewählte Sprache so genau wie möglich sein. Dies bedeutet keine Monte-Carlo-Schätzung oder Poisson-Näherung.
• Nund kist nicht größer als die größte darstellbare Ganzzahl in der von Ihnen gewählten Sprache. Wenn Ihre gewählte Sprache kein festes Maximum für Ganzzahlen hat (abgesehen von Speicherbeschränkungen), dann Nundk kann beliebig groß sein.
• Genauigkeitsfehler aufgrund von Gleitkommaungenauigkeiten werden möglicherweise ignoriert - Ihre Lösung sollte absolut genaue Gleitkommazahlen mit unendlicher Genauigkeit voraussetzen.

Testfälle

Format: k, N -> exact fraction (float approximation)

2, 4 -> 795341/48627125 (0.016355912466550306)
2, 10 -> 2689423743942044098153/22996713557917153515625 (0.11694817771107766)
2, 23 -> 38093904702297390785243708291056390518886454060947061/75091883268515350125426207425223147563269805908203125 (0.5072972343239854)
3, 3 -> 1/133225 (7.5060987051979735e-06)
3, 15 -> 99202120236895898424238531990273/29796146005797507000413918212890625 (0.0033293607910766013)
3, 23 -> 4770369978858741874704938828021312421544898229270601/375459416342576750627131037126115737816349029541015625 (0.01270542106874784)
3, 88 -> 121972658600365952270507870814168157581992420315979376776734831989281511796047744560525362056937843069780281314799508374037334481686749665057776557164805212647907376598926392555810192414444095707428833039241/238663638085694198987526661236008945231785263891283516149752738222327030518604865144748956653519802030443538582564040039437134064787503711547079611163210009542953054552383296282869196147657930850982666015625 (0.5110651106247305)
4, 5 -> 1821/17748900625 (1.0259790386313012e-07)
4, 25 -> 2485259613640935164402771922618780423376797142403469821/10004116148447957520459906484225353834116619892120361328125 (0.0002484237064787077)
5, 50 -> 786993779912104445948839077141385547220875807924661029087862889286553262259306606691973696493529913926889614561937/7306010813549515310358093277059651246342214174497508156711617142094873581852472030624097938198246993124485015869140625 (0.00010771867165219201)
10, 11 -> 801/8393800448639761033203125 (9.542757239717371e-23)
10, 20 -> 7563066516919731020375145315161/4825745614492126958810682272575693836212158203125 (1.5672327389589693e-18)
10, 100 -> 122483733913713880468912433840827432571103991156207938550769934255186675421169322116627610793923974214844245486313555179552213623490113886544747626665059355613885669915058701717890707367972476863138223808168550175885417452745887418265215709/1018100624231385241853189999481940942382873878399046008966742039665259133127558338726075853312698838815389196105495212915667272376736512436519973194623721779480597820765897548554160854805712082157001360774761962446621765820964355953037738800048828125 (1.2030611807765361e-10)
10, 200 -> 46037609834855282194444796809612644889409465037669687935667461523743071657580101605348193810323944369492022110911489191609021322290505098856358912879677731966113966723477854912238177976801306968267513131490721538703324306724303400725590188016199359187262098021797557231190080930654308244474302621083905460764730976861073112110503993354926967673128790398832479866320227003479651999296010679699346931041199162583292649095888379961533947862695990956213767291953359129132526574405705744727693754517/378333041587022747413582050553902956219347236460887942751654696440740074897712544982385679244606727641966213694207954095750881417642309033313110718881314425431789802709136766451022222829015561216923212248085160525409958950556460005591372098706995468877542448525403291516015085653857006548005361106043070914396018461580475651719152455730181412523297836008507156692430467118523245584181582255037664477857149762078637248959905010608686740872875726844702607085395469621591502118462813086807727813720703125 (1.21685406174776e-07)

Jelly , 17 16 Bytes

ĠZL
365ṗÇ€<¬µS÷L

Extrem ineffizient. Probieren Sie es online! (aber halte N unter 3 )

Wie es funktioniert

365ṗÇ€<¬µS÷L  Main link. Left argument: N. Right argument: K

365ṗ          Cartesian product; generate all lists of length N that consist of
              elements of [1, ..., 365].
    ǀ        Map the helper link over all generated lists. It returns the highest
              amount of people that share a single birthday.
      <       Compare each result with K.
       ¬      Negate.
        µS÷L  Take the mean by dividing the sum by the length.


ĠZL           Helper link. Argument: A (list of integers)

Ġ             Group the indices have identical values in A.
 Z            Zip; transpose rows with columns.
  L           Take the length of the result, thus counting columns.

MATL , 16 Bytes

365:Z^!tXM=s>~Ym

Erster Eingang ist N, zweiter ist k.

Probieren Sie es online!

Dies ist ein auf Aufzählungen basierender Ansatz, wie die Antwort von Dennis Jelly. Daher sollten die Eingabenummern aufgrund von Speicherbeschränkungen klein gehalten werden.

365:   % Vector [1 2 ... 365]
Z^     % Take N implicitly. Cartesian power. Gives a 2D array with each
       % "combination" on a row
!      % Transpose
t      % Duplicate
XM     % Mode (most frequent element) of each column
=      % Test for equality, element-wise with broadcast. For each column, gives
       % true for elements equal to that column's mode, false for the rest
s      % Sum of each column. Gives a row vector
>~     % Take k implicitly. True for elements equal or greater than k
Ym     % Mean of each column. Implicitly display

J 41 36 Bytes

(+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^))

Unkomplizierter Ansatz ähnlich wie bei den anderen. Stößt bei n> 3 auf Speicherprobleme .

Verwendung

Nimmt den Wert von kauf der LHS und nauf der RHS.

   f =: (+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^))
   0 f 0
0
   0 f 1
1
   1 f 1
1
   0 f 2
1
   1 f 2
1
   2 f 2
0.00273973
   0 f 3
1
   1 f 3
1
   2 f 3
0.00820417
   3 f 3
7.5061e_6

Auf meinem PC werden bei Verwendung eines i7-4770k und des fremden Timers 6!:2für n = 3 etwa 25 Sekunden benötigt.

   timer =: 6!:2
   timer '2 f 3'
24.7893
   timer '3 f 3'
24.896

Erläuterung

(+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^)) Input: k on LHS, n on RHS
          365&                       The number 365
               #~                    Create n copies of 365
                                 ^   Calculate 365^n
                              i.@    The range [0, 1, ..., 365^n-1]
                            #:       Convert each value in the range to base-n and pad
                                     with zeroes to the right so that each has n digits
                     (#/.~)@         Find the size of each set of identical values
                 >./@                Find the max size of each
        <:                           Test each if greater than or equal to k
(+/%#)@                              Apply to the previous result
 +/                                  Find the sum of the values
    #                                Count the number of values
   %                                 Divide the sum by the count and return