Compute the multinomial coefficient

Question

Time for another easy challenge in which all can participate!

The multinomial theorem states:

The expression in parentheses is the multinomial coefficient, defined as:

Allowing the terms k_i to range over all integer partitions of n gives the n-th level of Pascal's m-simplex. Your task is to compute this coefficient.

Task

Write a program or function which takes m numbers, n, k₁, k₂, ... ,k_m-1, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take m as an additional argument if need be. Note that k_m is not in the input.

• These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else, as long as the actual computation of the multinomial coefficient is performed by your code, and not the encoding process.

• Output format is similarly flexible.

• All code should run in less than one minute for n and m up to 1000.

• Do not worry about integer overflow.

• Built-ins designed to compute the multinomial coefficient are not allowed.

• Standard loopholes apply.

Scoring

This is code golf: Shortest solution in bytes wins.

Test cases

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

Answer 1

Jelly, 7 6 bytes

;_/!:/

Look ma, no Unicode! This program takes a single list as input, with n at its first index.

Try it online! or verify all test cases at once.

How it works

;_/!:/ 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.

Answer 2

CJam, 11 bytes

l~_:-+:m!:/

Input as a single list with n first:

[95 65 4 4]

This handles inputs up to n and m 1000 pretty much instantly.

Test it here.

Explanation

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!.

Answer 3

MATL, 21 15 bytes

Let's put the log-gamma function to good use. This avoids internal overflowing by working with logarithms of factorials, not with factorials themselves.

1+ZgiO$Gs-h1+Zgs-ZeYo

This works in current version (9.2.2) of the language/compiler, which is earlier than this challenge.

Inputs are: first a number, then a numeric vector. The result is produced as a double, which limits maximum output to somewhere around 2^52.

Example

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

Explanation

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

Answer 4

PowerShell, 91 74 bytes

_{Woo! My 100th answer on PPCG!}

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

Whew. Not going to win shortest-code, that's for sure. Uses a couple neat tricks with ranges, though. _{And this is probably complete gibberish to anyone not familiar with PowerShell.}

Explanation

First we take input with param($n,$k) and expect $k to be an array, e.g. .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

We'll start with the numerator (everything to the left of /). That's simply a range from 1..$n that has been -joined together with * and then evaluated with iex to compute the factorial (i.e., 1*2*3*...*$n).

Next, we loop over $k|%{...} and each iteration we subtract the current value $_ from $n (which we don't care about anymore) to formulate $k_m later. Additionally, we generate the range 1..$k_i each iteration, which gets left on the pipeline. Those pipeline objects get array-concatenated with the second expression, range 1..$n (which is $k_m at this point). All of that is finally -joined together with * and evaluated with iex, similar to the numerator (this works because x! * y! = 1*2*3*...*x * 1*2*3*...*y, so we don't care about individual ordering).

Finally, the / happens, the numerator is divided by the denominator, and output.

Handles output correctly for larger numbers, since we're not explicitly casting any variables as any particular datatypes, so PowerShell will silently re-cast as different datatypes on the fly as needed. For the larger numbers, outputs via scientific notation to best preserve significant figures as the datatypes get re-cast. For example, .\compute-the-multinomial-coefficient.ps1 55 @(28) will output 3.82434530038022E+15. I'm presuming this to be OK given "Output format is similarly flexible" is specified in the challenge and quintopia's comments "If the final result can fit within the natively supported integer types, then the result must be accurate. If it cannot, there is no restriction on what may be output."

---

Alternatively

Depending upon output formatting decisions, the following at 92 bytes

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

Which is the same as the above, just uses explicit output formatting with .ToString('G17') to achieve the desired number of digits. For 55 @(28) this will output 3824345300380220.5

---

Edit1 -- Saved 17 bytes by getting rid of $d and just calculating it directly, and getting rid of the calculation for $k_m by stringing it along while we loop $k
Edit2 -- Added alternate version with explicit formatting

Answer 5

APL (Dyalog Extended), 9 bytes

×/2!/+\⍛,

Try it online!

Using the idea from my APL answer on another challenge that involves multinomials.

A tacit function whose left argument is the list of k's, and right argument is n. The test cases check if it agrees with Adam's solution with left and right arguments flipped.

How it works

×/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}} $$

Answer 6

APL (Dyalog Unicode), 16 bytes^SBCS

Entirely based on the mathematical skill of my colleague Marshall.

Anonymous infix function. Takes k as right argument and n as left argument.

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

Try it online!

{…} anonymous lambda; ⍺ is left argument (n) and ⍵ is right argument (k)

 0,⍵ prepend a zero to k

 ¯1↓ drop the last item from that

 +\ cumulative sum of that

 ⍺- subtract that from n

 ⍵! (^k) that

 ×/ product of that

Answer 7

Python 3, 93 91

Thanks to Dennis and 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 as integer, k as iterable.

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)

Answer 8

Mathematica, 26 bytes

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

Example:

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

Out[1]= 1934550571913396675776550070308250

Answer 9

Haskell, 59 58 bytes

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

Try it online!

Thanks to BMO for saving 1 byte!

Answer 10

05AB1E, 8 bytes

Ƹ«!R.«÷

Try it online! Explanation:

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

I can't seem to find better ways of performing step 2 or step 4.

Answer 11

APL (Dyalog Unicode), 17 bytes

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

Try it online!

Infix tacit function (Thanks to @Adám for the 2 bytes it saves.)

---

APL (Dyalog Unicode), 19 bytes

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

Try it online!

Infix Dfn.

Both functions above compute the given formula.

Answer 12

PARI/GP, 43 bytes

Pretty straightforward; aside from formatting, the ungolfed version might well be identical.

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

Answer 13

Matlab 48 bytes

You need to set format to long in advance to get the higher precision. Then, it's quite straightforward:

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

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

 1.934550571913395e+33

Answer 14

Pyth, 10 bytes

/F.!MaQ-FQ

Try it online: Demonstration

Explanation:

/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

Answer 15

J, 16 bytes

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

Usage

For larger values, a suffix of x is used to denote extended precision integers.

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

Explanation

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

Answer 16

Perl 6,  52  50 bytes

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

Test it

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

Test it (result is a Rational with denominator of 1)

Expanded:

->     # 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｣
      )
}

Answer 17

Clojure, 70 bytes

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

Creates an anonymous function taking all of the arguments as a single list, with n first.

30 characters are "wasted" just defining the damn factorial function. Oh well.