Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Time for another easy challenge in which all can participate!

The multinomial theorem states: Formula for computing the nth power of a multinomial

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

Multinomial coefficient

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.

Task

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
share|improve this question
    
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 Büttner Jan 14 at 15:15
    
@MartinBüttner Yes, that is a correct assumption. – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 14 at 15:28
2  
@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

11 Answers 11

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.
share|improve this answer
    
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!.
share|improve this answer
    
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 Büttner 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
share|improve this answer
4  
Try it online! now has experimental MATL support: matl.tryitonline.net/… Suggestions are welcome. – Dennis Jan 14 at 19:03
1  
@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 -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

share|improve this answer

Mathematica, 26 bytes

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

Example:

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

Out[1]= 1934550571913396675776550070308250
share|improve this answer

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))!
share|improve this answer

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
share|improve this answer

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)
share|improve this answer
1  
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
2  
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
2  
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
1  
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
share|improve this answer

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
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.