¡Es hora de otro desafío fácil en el que todos puedan participar!

El teorema multinomial establece:

La expresión entre paréntesis es el coeficiente multinomial, definido como:

Permitir que los términos k _i a la gama de más de todas las particiones de enteros de n da la n -ésima nivel de de Pascal m -simplex. Su tarea es calcular este coeficiente.

Tarea

Escriba un programa o función que tome m números, n , k ₁ , k ₂ , ..., k _m-1 , y genere o devuelva el coeficiente multinomial correspondiente. Su programa puede tomar opcionalmente m como argumento adicional si es necesario. Tenga en cuenta que k _m no está en la entrada.

• Estos números pueden ingresarse en cualquier formato que le guste, por ejemplo, agrupados en listas o codificados en unario, o cualquier otra cosa, siempre que su código realice el cálculo real del coeficiente multinomial, y no el proceso de codificación.

• El formato de salida es igualmente flexible.

• Todo el código debe ejecutarse en menos de un minuto para n y m hasta 1000.

• No te preocupes por el desbordamiento de enteros.

• No están permitidos los elementos integrados diseñados para calcular el coeficiente multinomial.

• Se aplican lagunas estándar.

Tanteo

Este es el código de golf: la solución más corta en bytes gana.

Casos de prueba

Input: 3, [2, 0]
Output: 3

Input: 3, [1, 1]
Output: 6

Input: 11, [1, 4, 4]
Output: 34650

Input: 4, [1,2]
Output: 12

Input: 15, [5,4,3,2]
Output: 37837800

Input: 95, [65,4,4]
Output: 1934550571913396675776550070308250

Input: 32, [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output: 4015057936610313875842560000000

Input: 15, [3,3,3,3]
Output: 168168000

Input: 1000, [10,10,10,10,10,10,10,10,10,10,100,100,100,100,100,100,100,100]
Output: 1892260836114766064839886173072628322819837473493540916521650371620708316292211493005889278395285403318471457333959691477413845818795311980925098433545057962732816261282589926581281484274178579110373517415585990780259179555579119249444675675971136703240347768185200859583936041679096016595989605569764359198616300820217344233610087468418992008471158382363562679752612394898708988062100932765563185864346460326847538659268068471585720069159997090290904151003744735224635733011050421493330583941651019570222984959183118891461330718594645532241449810403071583062752945668937388999711726969103987467123014208575736645381474142475995771446030088717454857668814925642941036383273459178373839445456712918381796599882439216894107889251444932486362309407245949950539480089149687317762667940531452670088934094510294534762190299611806466111882595667632800995865129329156425174586491525505695534290243513946995156554997365435062121633281021210807821617604582625046557789259061566742237246102255343862644466345335421894369143319723958653232683916869615649006682399919540931573841920000000000000

Input: 33, [17]
Output: 1166803110

Input: 55, [28]
Output: 3824345300380220

Gelatina , 7 6 bytes

;_/!:/

Mira ma, no Unicode! Este programa toma una sola lista como entrada, con n en su primer índice.

Pruébalo en línea! o verificar todos los casos de prueba a la vez .

Cómo funciona

;_/!:/ Input: A (list)

 _/    Reduce A by subtraction. This subtracts all other elements from the first.
;      Concatenate A with the result to the right.
   !   Apply factorial to all numbers in the resulting list.
    :/ Reduce the result by division. This divides the first element by the others.

CJam, 11 bytes

l~_:-+:m!:/

Ingrese como una lista única con nprimero:

[95 65 4 4]

Este asas insumos hasta ny m1000 casi al instante.

Pruébalo aquí.

Explicación

l~  e# Read a line of input and evaluate it.
_   e# Duplicate.
:-  e# Fold subtraction over the list. A fold is essentially a foreach loop that starts
    e# from the second element. Hence, this subtracts all the k_i from n, giving k_m.
+   e# Append k_m to the list.
:m! e# Compute the factorial of each element in the list.
:/  e# Fold division over the list. Again, this divides n! by each of the k_i!.

MATL , 21 15 bytes

Pongamos la función log-gamma en buen uso. Esto evita el desbordamiento interno al trabajar con logaritmos de factoriales, no con factoriales en sí.

1+ZgiO$Gs-h1+Zgs-ZeYo

Esto funciona en la versión actual (9.2.2) del lenguaje / compilador, que es anterior a este desafío.

Las entradas son: primero un número, luego un vector numérico. El resultado se produce como a double, lo que limita la salida máxima a algún lugar alrededor 2^52.

Ejemplo

>> matl 1+ZgiO$Gs-h1+Zgs-ZeYo
> 15
> [5 4 3 2]
37837800

Explicación

1+       % implicit input (number). Add 1
Zg       % log-gamma function
i        % input (numeric vector).
0$G      % push both inputs
s-       % sum the second input (vector) and subtract from first
h1+      % append to vector. Add 1
Zg       % log-gamma function, element-wise on extended vector
s        % sum of results
-        % subtract from previous result of log-gamma
Ze       % exponential
Yo       % round. Implicit display

PowerShell, 91 74 bytes

_{¡Cortejar! ¡Mi respuesta número 100 en PPCG!}

param($n,$k)(1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)

Uf. No voy a ganar el código más corto, eso es seguro. Sin embargo, utiliza un par de buenos trucos con rangos. _{Y esto es probablemente una tontería completa para cualquiera que no esté familiarizado con PowerShell.}

Explicación

Primero tomamos información con param($n,$k)y esperamos $kser una matriz, por ejemplo .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Comenzaremos con el numerador (todo a la izquierda de /). Eso es simplemente un rango desde el 1..$nque se ha -joineditado junto con *y luego evaluado iexpara calcular el factorial (es decir, 1*2*3*...*$n).

A continuación, un bucle sobre $k|%{...}y cada iteración se resta el valor actual $_de $n(que no se preocupan más) para formular $k_mmás tarde. Además, generamos el rango de 1..$k_icada iteración, que se deja en la tubería. Esos objetos de canalización se concatenan en matriz con la segunda expresión, rango 1..$n(que se encuentra $k_men este punto). Todo eso finalmente se -joinedita *y evalúa con iex, similar al numerador (esto funciona porque x! * y! = 1*2*3*...*x * 1*2*3*...*y, por lo que no nos importa el orden individual).

Finalmente, /sucede que el numerador se divide por el denominador y la salida.

Maneja la salida correctamente para números más grandes, ya que no estamos emitiendo explícitamente ninguna variable como ningún tipo de datos en particular, por lo que PowerShell volverá a emitir silenciosamente como diferentes tipos de datos sobre la marcha, según sea necesario. Para los números más grandes, salidas a través de notación científica para preservar mejor las cifras significativas a medida que los tipos de datos se vuelven a emitir. Por ejemplo, .\compute-the-multinomial-coefficient.ps1 55 @(28)saldrá 3.82434530038022E+15. Supongo que esto está bien dado que "El formato de salida es igualmente flexible" se especifica en el desafío y en los comentarios de quintopia "Si el resultado final puede caber dentro de los tipos enteros soportados de forma nativa, entonces el resultado debe ser preciso. Si no puede, hay no hay restricción sobre lo que se puede generar ".

---

Alternativamente

Dependiendo de las decisiones de formato de salida, lo siguiente en 92 bytes

param($n,$k)((1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)).ToString('G17')

Que es la misma que la anterior, simplemente usa la salida explícita formatear con .ToString('G17')para conseguir el número deseado de dígitos. Para 55 @(28)esto saldrá3824345300380220.5

---

Edit1: ahorró 17 bytes deshaciéndolo $dy calculándolo directamente, y deshaciéndolo del cálculo $k_mal encadenarlo mientras realizamos el bucle $k
Edit2: se agregó una versión alternativa con formato explícito

APL (Dyalog Extended) , 9 bytes

×/2!/+\⍛,

Pruébalo en línea!

Usando la idea de mi respuesta APL en otro desafío que involucra a los multinomiales .

Una función tácita cuyo argumento izquierdo es la lista de k, y el argumento derecho es n. Los casos de prueba verifican si está de acuerdo con la solución de Adam con los argumentos izquierdo y derecho invertidos.

Cómo funciona

×/2!/+\⍛,
     +\    ⍝ Cumulative sum of k's (up to m-1'th element)
       ⍛,  ⍝ Append n (sum of k_1 to k_m)
  2!/      ⍝ Binomial of consecutive pairs
×/         ⍝ Product

$$\frac{(k_1 + k_2 + \cdots + k_m)!}{k_1! k_2! \cdots k_m!} = \frac{(k_1 + k_2)!}{k_1! k_2!} \times \frac{(k_1 + k_2 + \cdots + k_m)!}{(k_1 + k_2)! k_3! \cdots k_m!}$$

$$= \frac{(k_1 + k_2)!}{k_1! k_2!} \times \frac{(k_1 + k_2 + k_3)!}{(k_1 + k_2)! k_3!} \times \frac{(k_1 + k_2 + \cdots + k_m)!}{(k_1 + k_2 + k_3)! \cdots k_m!}$$

$$= \cdots = \binom{k_1 + k_2}{k_1} \binom{k_1 + k_2 + k_3}{k_1 + k_2} \cdots \binom{k_1 + \cdots + k_m}{k_1 + \cdots + k_{m-1}}$$

Mathematica, 26 bytes

#!/Times@@({#-+##2,##2}!)&

Ejemplo:

In[1]:= #!/Times@@({#-+##2,##2}!)&[95,65,4,4]

Out[1]= 1934550571913396675776550070308250

Pitón 3, 93 91

Gracias a Dennis y FryAmTheEggman .

f=lambda x:0**x or x*f(x-1)
def g(n,k):
    r=f(n)
    for i in k:r//=f(i)
    return r//f(n-sum(k))

ncomo entero, kcomo iterable.

Sin golf:

import functools #cache

@functools.lru_cache(maxsize=None) #cache results to speed up calculations
def factorial(x):
    if x <= 1: return 1
    else: return x * factorial(x-1)

def multinomial(n, k):
    ret = factorial(n)
    for i in k: ret //= factorial(i)
    km = n - sum(k)
    return ret//factorial(km)

APL (Dyalog Unicode) , ^{SBCS de} 16 bytes

Completamente basado en la habilidad matemática de mi colega Marshall .

Función de infijo anónimo. Toma k como argumento derecho yn como argumento izquierdo.

{×/⍵!⍺-+\¯1↓0,⍵}

Pruébalo en línea!

{... } lambda anónimo; ⍺es argumento izquierdo ( n ) y ⍵argumento derecho ( k )

 0,⍵ anteponer un cero a k

 ¯1↓ suelte el último elemento de ese

 +\ suma acumulativa de eso

 ⍺- restar eso de n

 ⍵! ( ^k ) que

 ×/ producto de eso

PARI / GP, 43 bytes

Muy claro; Aparte del formateo, la versión sin golf podría ser idéntica.

m(n,v)=n!/prod(i=1,#v,v[i]!)/(n-vecsum(v))!

Matlab 48 bytes

Debe configurarlo formatde longantemano para obtener la mayor precisión. Entonces, es bastante sencillo:

@(n,k)factorial(n)/prod(factorial([k,n-sum(k)]))

ans(95, [65,4,4])
ans =

 1.934550571913395e+33

Pyth, 10 bytes

/F.!MaQ-FQ

Pruébelo en línea: demostración

Explicación:

/F.!MaQ-FQ   implicit: Q = input list
       -FQ   reduce Q by subtraction
     aQ      append the result to Q
  .!M        compute the factorial for each number
/F           reduce by division

J, 16 bytes

[(%*/)&:!],(-+/)

Uso

Para valores mayores, xse usa un sufijo de para denotar enteros de precisión extendidos.

   f =: [(%*/)&:!],(-+/)
   11 f 1 4 4
34650
   15x f 5 4 3 2
37837800

Explicación

[(%*/)&:!],(-+/)  Input: n on LHS, A on RHS
             +/   Reduce A using addition
            -     Subtract that sum from n, this is the missing term
         ]        Get A
          ,       Append the missing term to A to make A'
[                 Get n
      &:!         Take the factorial of n and each value in A'
   */             Reduce using multiplication the factorials of A'
  %               Divide n! by that product and return

05AB1E , 8 bytes

Ƹ«!R.«÷

Pruébalo en línea! Explicación:

Æ           Subtract all the elements from the first
 ¸«         Append to the original list
   !        Take the factorial of all the elements
    R.«÷    Reduce by integer division

Parece que no puedo encontrar mejores formas de realizar el paso 2 o el paso 4.

APL (Dyalog Unicode) , 17 bytes

⊢∘!÷(×/∘!⊣,⊢-1⊥⊣)

Pruébalo en línea!

Función infija tácita (Gracias a @ Adám por los 2 bytes que guarda).

---

APL (Dyalog Unicode) , 19 bytes

{(!⍺)÷×/!(⍺-+/⍵),⍵}

Pruébalo en línea!

Infix Dfn.

Ambas funciones anteriores calculan la fórmula dada.

Haskell , 59 58 bytes

f n=product[1..n]
n#k=foldl((.f).div)(f n)k`div`f(n-sum k)

Pruébalo en línea!

¡Gracias a BMO por guardar 1 byte!

Clojure, 70 bytes

#(let[a apply](a /(map(fn[x](a *(map inc(range x))))(conj %(a - %)))))

Crea una función anónima tomando todos los argumentos como una lista única, con nprimero.

Se desperdician 30 caracteres simplemente definiendo la maldita función factorial. Oh bien.

Perl 6 ,  52  50 bytes

->\n,\k{[*](1..n)div[*] ([*] 1..$_ for |k,[-] n,|k)}

Pruébalo

->\n,\k{[*](1..n)/[*] ([*] 1..$_ for |k,[-] n,|k)}

Pruébelo (el resultado es un racional con denominador de 1)

Expandido:

->     # pointy block lambda
  \n,
  \k
{
    [*]( 1 .. n )   # factorial of ｢n｣

  /                 # divide (produces Rational)

    [*]             # reduce the following using &infix:«*»

      (
          [*] 1..$_ # the factorial of

        for         # each of the following

          |k,       # the values of ｢k｣ (slipped into list)
          [-] n,|k  # ｢n｣ minus the values in ｢k｣
      )
}