Hora de outro desafio fácil, no qual todos podem participar!

O teorema multinomial afirma:

A expressão entre parênteses é o coeficiente multinomial, definido como:

Permitindo que os termos de k _i a variar ao longo de todas as partições inteiros de n dá o n -simo nível de de Pascal m -simplex. Sua tarefa é calcular esse coeficiente.

Tarefa

Escreva um programa ou função que pegue m números, n , k ₁ , k ₂ , ..., k _m-1 e produz ou retorne o coeficiente multinomial correspondente. Seu programa pode opcionalmente considerar m como argumento adicional, se necessário. Observe que k _m não está na entrada.

• Esses números podem ser inseridos em qualquer formato que você queira, por exemplo, agrupado em listas ou codificado em unário ou qualquer outra coisa, desde que a computação real do coeficiente multinomial seja realizada pelo seu código, e não pelo processo de codificação.

• O formato de saída é igualmente flexível.

• Todo o código deve ser executado em menos de um minuto para n e m até 1000.

• Não se preocupe com o excesso de números inteiros.

• Built-ins projetados para calcular o coeficiente multinomial não são permitidos.

• Aplicam-se brechas padrão.

Pontuação

Este é o código golf: A solução mais curta em bytes vence.

Casos de teste

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

Geléia , 7 6 bytes

;_/!:/

Olha ma, não Unicode! Este programa usa uma única lista como entrada, com n em seu primeiro índice.

Experimente online! ou verifique todos os casos de teste de uma só vez .

Como 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!:/

Insira como uma única lista com o nprimeiro:

[95 65 4 4]

Este alças entradas até ne m1000 praticamente instantaneamente.

Teste aqui.

Explicação

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

Vamos usar bem a função log-gama . Isso evita o transbordamento interno ao trabalhar com logaritmos de fatoriais, não com os próprios fatoriais.

1+ZgiO$Gs-h1+Zgs-ZeYo

Isso funciona na versão atual (9.2.2) do idioma / compilador, anterior a esse desafio.

As entradas são: primeiro um número, depois um vetor numérico. O resultado é produzido como a double, o que limita a produção máxima para algo em torno de2^52 .

Exemplo

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

Explicação

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

_{Uau! Minha 100ª resposta sobre PPCG!}

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

Ufa. Não vai ganhar código mais curto, isso é certo. Usa alguns truques legais com intervalos, no entanto. _{E isso provavelmente é uma bobagem completa para quem não conhece o PowerShell.}

Explicação

Primeiro, aceitamos param($n,$k)e esperamos $kser uma matriz, por exemplo .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Começaremos com o numerador (tudo à esquerda de /). Isso é simplesmente um intervalo 1..$nque foi -joineditado *e avaliado com iexpara calcular o fatorial (ou seja,1*2*3*...*$n ).

Em seguida, vamos varrer $k|%{...}e cada iteração que subtrair o valor atual $_da $n(que não se preocupam mais) para formular $k_mmais tarde. Além disso, geramos o intervalo a 1..$k_icada iteração, que fica no pipeline. Esses objetos de pipeline são concatenados com a segunda expressão, range 1..$n(que está $k_mneste momento). Tudo isso é finalmente -joineditado *e avaliado com iex, semelhante ao numerador (isso funciona porquex! * y! = 1*2*3*...*x * 1*2*3*...*y , portanto, não nos importamos com pedidos individuais).

finalmente, o / acontece é que o numerador é dividido pelo denominador e pela saída.

Lida com a saída corretamente para números maiores, já que não estamos expressamente convertendo nenhuma variável como qualquer tipo de dados específico, portanto, o PowerShell silenciosamente reproduz novamente diferentes tipos de dados em tempo real, conforme necessário. Para os números maiores, as saídas via notação científica preservam melhor os números significativos à medida que os tipos de dados são relançados. Por exemplo, .\compute-the-multinomial-coefficient.ps1 55 @(28)será exibido 3.82434530038022E+15. Estou presumindo que isso esteja correto, dado que "O formato de saída é similarmente flexível" está especificado no desafio e nos comentários da quintopia "Se o resultado final puder caber nos tipos inteiros suportados nativamente, o resultado deverá ser preciso. Se não puder, não há restrição sobre o que pode ser produzido ".

---

alternativamente

Dependendo das decisões de formatação da saída, o seguinte em 92 bytes

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

Que é o mesmo que o acima, apenas usa formatação de saída explícita com .ToString('G17')para alcançar o número desejado de dígitos. Para 55 @(28)isso irá produzir3824345300380220.5

---

Edit1 - Economizou 17 bytes, livrando-se $de calculando-o diretamente, e livrando-se do cálculo $k_mamarrando-o enquanto fazemos o loop $k
Edit2 - Adicionada versão alternativa com formatação explícita

APL (Dyalog Extended) , 9 bytes

×/2!/+\⍛,

Experimente online!

Usando a ideia da minha resposta APL em outro desafio que envolve multinomiais .

Uma função tácita cujo argumento à esquerda é a lista de k e o argumento à direita é n. Os casos de teste verificam se concorda com a solução de Adam com os argumentos esquerdo e direito invertidos.

Como 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}!)&

Exemplo:

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

Out[1]= 1934550571913396675776550070308250

Python 3, 93 91

Agradecimentos a Dennis e 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))

n como inteiro, k como iterável.

Ungolfed:

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) , 16 bytes ^SBCS

Totalmente baseado nas habilidades matemáticas do meu colega Marshall .

Função de infixo anônimo. Toma k como argumento certo e n como argumento esquerdo.

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

Experimente online!

{... } lambda anônima; ⍺é argumento à esquerda ( n ) e ⍵é argumento à direita ( k )

 0,⍵ acrescente um zero a k

 ¯1↓ largar o último item desse

 +\ soma acumulada disso

 ⍺- subtrair isso de n

 ⍵! ( ^k ) que

 ×/ produto disso

PARI / GP, 43 bytes

Bem direto; além da formatação, a versão não-gasta pode muito bem ser idêntica.

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

Matlab 48 bytes

Você precisa definir formatcom longantecedência para obter a maior precisão. Então, é bem direto:

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

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

 1.934550571913395e+33

Pitão, 10 bytes

/F.!MaQ-FQ

Experimente online: Demonstração

Explicação:

/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 maiores, um sufixo de xé usado para indicar números inteiros de precisão estendidos.

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

Explicação

[(%*/)&:!],(-+/)  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.«÷

Experimente online! Explicação:

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

Não consigo encontrar melhores maneiras de executar as etapas 2 ou 4.

APL (Dyalog Unicode) , 17 bytes

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

Experimente online!

Função Infix tácita (Graças a @ Adám pelos 2 bytes que ele salva.)

---

APL (Dyalog Unicode) , 19 bytes

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

Experimente online!

Infix Dfn.

Ambas as funções acima calculam a fórmula fornecida.

Haskell , 59 58 bytes

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

Experimente online!

Obrigado ao BMO por economizar 1 byte!

Clojure, 70 bytes

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

Cria uma função anônima, recebendo todos os argumentos como uma única lista, com n primeiro.

30 caracteres são "desperdiçados" apenas definindo a função fatorial. Ah bem.

Perl 6 ,  52  50 bytes

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

Teste-o

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

Teste (o resultado é um Rational com denominador 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｣
      )
}