# Compute the multinomial coefficient

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

Write a program or function which takes m numbers, n, k1, k2, ... ,km-1, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take m as an additional argument if need be. Note that km 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
``````
-
Can we have imprecision errors? I.e., instead of `1934550571913396675776550070308250`, can we output `1.9345505719133966e+33`? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 14 at 15:09
@CᴏɴᴏʀO'Bʀɪᴇɴ If you used 64-bit floats, you won't be able to represent input `[1000 {999 ones}]` at all, because the exponent is way beyond what 64-bit floats can represent. (128-bit floats will probably suffice, but I'm assuming you want to use JavaScript's native number type?) – Martin Ender Jan 14 at 15:15
@MartinBüttner Yes, that is a correct assumption. – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 14 at 15:28
@quintopia "Time for another easy challenge in which all can participate!". Everyone except me! (Since I have no idea what Pascals simplex and multinomials are D:) LOL. – Ashwin Gupta Jan 14 at 16:56
@AshwinGupta Don't worry about it. You just compute the expression in the second image and you're good to go! 👍 – quintopia Jan 14 at 17:01

# Jelly, 7 6 bytes

``````;_/!:/
``````

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

### 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.
``````
-
This is pretty much the algorithm I had in mind as being the simplest. – quintopia Jan 14 at 16:58

## 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!.
``````
-
It looks like you will actually lose the byte-count competition, but I have to say I am impressed with CJam's insane terseness. – phord Jan 14 at 15:39
@phord Well CJam is no match for Jelly (or Pyth for that matter). But I was quite surprised myself how compact it ended up. My first solution had 21 bytes, and while it didn't seem optimal, I didn't think I could almost cut that in half. – Martin Ender Jan 14 at 15:41

# 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
``````
-
Try it online! now has experimental MATL support: matl.tryitonline.net/… Suggestions are welcome. – Dennis Jan 14 at 19:03
@Dennis Hey! What a surprise!!! How can I thank you?? I do have a suggestion: if you ever come to Madrid I owe you a good dinner and some drinks – Luis Mendo Jan 14 at 19:24
I'm really grateful. It's great to have it online. How will we handle revisions? I'm still constantly updating the language, you know... – Luis Mendo Jan 14 at 19:25
For now, I'm manually updating the interpreters. If you make an update, just ping me in The Nineteenth Byte and I'll pull it asap. -- I'll have to go to Madrid in the near future, so I'll keep your offer in mind. ;) – Dennis Jan 14 at 19:36
@Dennis Great! That way we can meet in person! – Luis Mendo Jan 14 at 21:09

## 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 `-join`ed 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 `-join`ed 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

-

# Mathematica, 26 bytes

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

Example:

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

Out[1]= 1934550571913396675776550070308250
``````
-

## 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))!
``````
-

# 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
``````
-

# 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)
``````
-
You can use a single space instead of four for the dynamic whitespace bit – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 14 at 15:31
I used tabs, they got replaced in this post. Byte count seems to be OK. I'm not sure about float result and possible overflow. – Trang Oul Jan 14 at 15:47
1. This produces an incorrect for `95, [65, 4, 4]`. Note that the input does not contain k_m. 2. You don't seem to be using `from functools import*` at all. – Dennis Jan 14 at 16:01
1. Your golfed code doesn't use `reduce`. 2. `import math;f=math.factorial` saves a byte. 3. Python 2 would allow you to get rid of the second `/` in `//`. – Dennis Jan 14 at 20:07
Defining `f` on your own saves some bytes: `f=lambda x:0**x or x*f(x-1)`. – FryAmTheEggman Jan 14 at 20:21

# J - 11 bytes

``````%~/!(,~-~/)
``````

## Usage

Takes a list of values with n being at the end. The value of n is also marked as an extended integer. All could be marked but having just n be marked will adjust the other integers also.

``````   %~/!(,~-~/) 5 4 3 2 15x
37837800
``````

## Explanation

``````%~/!(,~-~/)
-~/     - Fold right using subtraction with operators swapped
,~        - Append that value to the front of the list
!           - Compute the factorial of each
%~/            - Fold right using division with operators swapped
``````
-

# 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
``````
-

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

-