27
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.
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
Can we have imprecision errors? I.e., instead of
1934550571913396675776550070308250
, can we output1.9345505719133966e+33
? – Conor O'Brien – 2016-01-14T15:09:53.070@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 – 2016-01-14T15:15:07.493@MartinBüttner Yes, that is a correct assumption. – Conor O'Brien – 2016-01-14T15:28:49.277
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 – 2016-01-14T16:56:19.933
@AshwinGupta Don't worry about it. You just compute the expression in the second image and you're good to go! – quintopia – 2016-01-14T17:01:55.370
@quintopia hey thanks :D! I'll give it a shot. Sorry I didn't respond all day I was at school then had an after school thing. – Ashwin Gupta – 2016-01-15T03:15:40.073