Esta noche, mi prometida me llevó a cenar para celebrar mi cumpleaños. Mientras estábamos fuera, escuché que Happy Birthday cantaba a 5 invitados diferentes (incluido yo mismo), en un restaurante lleno de 50 personas. Esto me hizo preguntarme: el problema original del cumpleaños (encontrar la probabilidad de que 2 personas en una habitación Ncompartan el mismo cumpleaños) es muy simple y directo. Pero, ¿qué pasa con el cálculo de la probabilidad de que al menos kpersonas de otras Npersonas compartan el mismo cumpleaños?

En caso de que se lo pregunte, la probabilidad de que al menos 5 personas de un total de 50 personas compartan el mismo cumpleaños es aproximadamente 1/10000.

El reto

Dados dos enteros Ny k, donde N >= k > 0, genera la probabilidad de que al menos las kpersonas en un grupo de Npersonas compartan el mismo cumpleaños. Para simplificar las cosas, suponga que siempre hay 365 posibles cumpleaños, y que todos los días son igualmente probables.

Para k = 2, esto se reduce al problema de cumpleaños original, y la probabilidad es 1 - P(365, N)/(365)**N(donde P(n,k)es el número de permutaciones de longitud k formadas a partir de n elementos ). Para valores mayores de k, este artículo de Wolfram MathWorld puede resultar útil.

Reglas

• La salida debe ser determinista y lo más precisa posible para el idioma elegido. Esto significa que no hay estimación de Monte Carlo o aproximación de Poisson.
• Ny kno será mayor que el número entero representable más grande en el idioma elegido. Si el idioma seleccionado no tiene máxima duro en números enteros (aparte de las limitaciones de memoria), a continuación, Ny kpuede ser arbitrariamente grande.
• Los errores de precisión derivados de imprecisiones de punto flotante pueden ignorarse: su solución debe asumir flotadores de precisión infinita y perfectamente precisos.

Casos de prueba

Formato: 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)

Jalea , 17 16 bytes

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

Extremadamente ineficiente. Pruébalo en línea! (pero mantenga N debajo de 3 )

Cómo funciona

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

La primera entrada es N, la segunda es k.

Pruébalo en línea!

Este es un enfoque basado en la enumeración, como la respuesta de Dennis 'Jelly , por lo que los números de entrada deben mantenerse pequeños debido a las limitaciones de memoria.

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.@^))

Enfoque directo similar a los demás. Se encuentra con problemas de memoria en n> 3 .

Uso

Toma el valor de ken el LHS y nen el 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

En mi PC, usando un i7-4770k y el temporizador foráneo 6!:2, calcular para n = 3 requiere aproximadamente 25 segundos.

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

Explicación

(+/%#)@(<: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