# m-nomial coefficient

While the binomial coefficient are the coefficients of $$\(1+x)^n\$$, m-nomial coefficients are the coefficients of $$\(1+x+x^2+...+x^{m-1})^n\$$.

For example, $$\m(3,5,6)\$$ is the coefficient of $$\x^6\$$ in the expansion of $$\(1+x+x^2)^5\$$.

Write a program/function that takes 3 numbers as input and outputs the corresponding m-nomial coefficient.

### Details

• Input can be taken via any reasonable method.
• Everything out of range is $$\0\$$, for example $$\m(2,0,-1) = m(2,5,6) = 0\$$
• The first argument will be positive.
• The second argument will not be negative.
• All three arguments will be integers.

### Testcases

Inputs:

[1,0,0]
[2,5,6]
[3,5,6]
[4,5,-1]


Outputs:

1
0
45
0


### Scoring

This is . Shortest solution in bytes wins.

• It's strange that a negative exponent gives a result of zero, since it gives a nonzero power series.
– xnor
Apr 23, 2016 at 23:39
• Why is m(0,0,0)=1 ? Any m(0, x, y) should be based on a polynomial with NO terms (not even 1) so it's really out of range and should give 0 (I'd even count it as invalid input) Apr 24, 2016 at 1:13
• @TonHospel Sorry, thanks, edited. Apr 24, 2016 at 1:15
• Thematically related. Apr 25, 2016 at 9:19
• @MartinBüttner If you are counting "thematically related" as related, then all arithmetic and regex-golf are related. Apr 25, 2016 at 10:29

# Perl, 636059 57 bytes

Includes +2 for -pa

Give input parameters on STDIN

mnomial.pl <<< "3 5 6"

#!/usr/bin/perl -pa
$_=/-/^($_--,1x$F)=~/^(1{0,$_}){$F}$(??{++$;})/+$


As a perl programmer I just know that every problem is really a regex in disguise...

# Explanation:

m(3,5,6) can be seen as the number of ways you can get 6 by adding 5 integers in the range [0..2]. You can write a regex matching such a partition using:

1 x 6 = /^(1{0,2}){5}$/  However once a single solution is found the regex stops. We need to fail the found solution to get the regex to backtrack to the next solution and count the failures. In perl this can be done by extending the regex at runtime with something that is sure to fail, e.g. by demanding that something comes after the end of the string:  1 x 6 = /^(1{0,2}){5}$(??{++$n})/ $n will count the number of failed attempts

My solution is basically this with two modifications:

• Output the counter in such a way that you get 0 instead of the empty string if there is no valid partition and the counter never gets incremented
• If the third argument is negative it would work if negative string lengths existed, but 1 x -5 is the empty string and 0 can be written exactly one way as sum of zeros, so that would output 1 instead of 0. I xor with the result of /-/to change the 1 back to 0

Without the need to handle a negative third argument this 49 byte solution would be good enough (give one parameter of m(x,y,z) on each line of STDIN in order y \n z \n x \n):

#!/usr/bin/perl -pa
$_=(1x<>)=~/^(1{0,@{[<>-1]}}){@F}$(??{++$;})/+$


# Jelly, 6 bytes

ṗ’S€ċ⁵


This is a full program that accepts m, n and the exponent as separate command line arguments.

Try it online!

### How it works

The problem boils down to counting the number of ways we can express the exponent as an ordered sum of exactly n integers between 0 and m - 1 (both inclusive).

ṗ’S€ċ⁵  Main link. Arguments: m, n, k

ṗ       Cartesian product; yield the array of all lists of exactly n elements of
[1, ..., m].
’      Decrement all integers in the resulting 2D list.
S€    Compute the sum of each individual list.
⁵  Yield k.
ċ   Count the number of times k appears in the list of sums.


# Pyth, 29 8 bytes

/sM^UQEE


Try it online!

Uses Dennis' Method.

If the input can be rearranged so that m(3,5,6) is fed in the order of 6,3,5 into the program, an extra byte can be cut off:

/sM^UEE


Try it online!

### Original 29-byte approach

.N?|TY?|<Y0>Y*tNT0sm:NtT-YdN1


How it works:

Uses the recurrence formula m(k,n,r) = m(k,n-1,r) + m(k,n-1,r-1) + ... m(k,n-1,r-k+1).

.N?|TY?|<Y0>Y*tNT0sm:NtT-YdN1
.N                             def colon(N,T,Y):
?|TY                             if T or Y:
?|<Y0>Y*tNT                      if Y<0 or Y>(N-1)*T:
0                         return 0
else:
sm:NtT-YdN               return sum([colon(N,T-1,Y-d) for d in range(N)])
else:
1          return 1


# Perl, 55 51 bytes

Includes +2 for -pa

Same basic idea as my other Perl answer, finding partitions of an integer but with a completely different implementation. This version is shorter, but only because I don't have to special case a negative third argument.This version is also totally boring...

Give input for m(x,y,z) on STDIN with a line for each argument in order z, x, y. E.g. to calculate m(3,5,6):

 mnomial.pl
6
3
5
^D


mnomial.pl:

#!/usr/bin/perl -pa
$"=",";$_=grep"@F"==eval,glob"+{@{[0..<>-1]}}"x<>


# Python, 64 bytes

f=lambda m,n,k:(k==0)+sum(f(m,n-1,k-t)for t in range(m*(n>0<k)))


As far as code golf goes, this is fairly efficient. Test it on Ideone.

• I don't know if we reached a consensus on whether True/False is OK for 1/0, but if so f=lambda m,n,k:n and sum(f(m,n-1,k-t)for t in range(m))or k==0 is shorter.
– xnor
Apr 24, 2016 at 17:44
• I tried something similar, but I used +(k==0) because I didn't think Booleans were valid output... I'll write a meta question later. This has come up rather frequently. Apr 24, 2016 at 18:18
• @xnor I finally remembered I was going to do this. Should Booleans be allowed where a number is required? Apr 29, 2016 at 4:01

## Sage, 71 bytes

lambda a,b,c:(c>=0and(sum(x^i for i in range(a))^b).list()[c:]or)


Verify all test cases online

The unnamed lambda function constructs the polynomial and returns the specified coefficient if c is not negative and less than or equal to the degree of the polynomial, else 0.

# Julia, 50 45 bytes

f(m,n,k)=n>0?sum(t->f(m,n-1,k-t),0:m-1):0^k^2


Try it online!

If digits supported unary, the following approach would be 1 byte shorter.

g(m,n,k)=sum(t->k==sum(digits(t,m)),0:m^n-1)


## JavaScript (ES6), 118 bytes

(m,n,k)=>[...Array(n)].reduce(a=>a.map(x=>t+=x,t=0),[...Array(m*n+1)].map((_,i)=>i%m?0:i?x=-x*(n+1-i/m)*m/i:x=1))[k]|0


Works by calculating (xm-1)n/(x-1)n. (xm-1)n is calculated by the binomial theorem and the result is then repeatedly divided by x-1.

Edit: Saved 24 bytes by using a different binomial calculation. Saved 4 bytes by switching to reduce (yay!).