# Challenge

In this challenge, all numbers are in $$\\mathbb{N}_0\$$.

Create a function or program that, when given a number $$\N\$$ and a tuple of $$\k\$$ numbers $$\(n_i)\$$ (all ≤ $$\N\$$), returns the number of ways $$\N\$$ can be written as a sum of $$\k\$$ integers ($$\x_1 + x_2 + ... + x_k\$$) such that $$\n_i \le x_i \le N\$$.

The input format is not fixed. You can read and parse strings, take two parameters as int and int[], etc.

This is a variation of the classical Integer Partition problem.

# Test Cases

$$\N=4, n=(0, 0, 2) \implies 6\$$ (2+0+2, 1+1+2, 0+2+2, 1+0+3, 0+1+3, 0+0+4)

$$\N=121, n=(7, 16, 21, 36, 21, 20) \implies 1\$$ (7+16+21+36+21+20)

This is , so the lowest byte count for each language wins!

• Do we have to support the edge case where all $n_i=0$? Feb 23 at 12:58
• I'm sorry if i dont get the question right, but how are you getting 1+0+3 in the first test case, when 3, or 1 are not in the tuple n?
– user100752
Feb 23 at 12:59
• @EliteDaMyth the numbers are not required to be in the tuple, but to be elementwise greater than or equal to the numbers in the tuple. Here, (1,0,3) elementwise ≥ (0, 0, 2) Feb 23 at 13:09
• This seems like a well-written challenge, but in future, I'd recommend posting in the Sandbox to get feedback first Feb 23 at 13:18
• Isn't this just the number of ways that $N - (x_1 + \cdots + x_k)$ can be written as the sum of $k$ non-negative integers?
– xnor
Feb 23 at 13:21

# Jelly, 5 bytes

rŒp§ċ


A dyadic Link accepting the lower bound tuple on the left and the total on the right which yields the count.

Try it online!

### How?

rŒp§ċ - Link: T, N       e.g. [2,1,3], 5
r     - inclusive range       [[2,3,4,5],[1,2,3,4,5],[1,2,3,4,5]]
Œp   - Cartesian product     [[2,1,1],[2,1,2],[2,1,3],[2,1,4],[2,1,5],[2,2,1],...,[5,5,4],[5,5,5]]
§  - sums                  [ 4,      5,      6,      7,      8,      5,     ..., 14,     15]
ċ - count (Ns)            2


n%(x:t)=sum\$map(%t)[0..n-x]
n%_=0^n


Try it online!

# Husk, 9 7 bytes

Edit: -2 bytes thanks to user

#¹mΣΠm…


Try it online!

#¹         # number of times that arg 1 appears in the list of
mΣ       # sums of
Π      # cartesian product of
m     # mapping
…    # range up to arg 1
# for each element of arg 2

• Nice answer! You can save a couple bytes by messing around with superscripts
– user
Feb 23 at 20:00
• @user - Thanks! I did try to get rid of the superscripts at the end, but never seemed to find the right permutation... Feb 23 at 20:23

# Python 3.8+, 62 bytes

import math
f=lambda S,N:math.comb(S-sum(N)+len(N)-1,len(N)-1)


The result can be found using the formula:

$$R = \binom{N-(\Sigma x_i)+k-1}{k-1}$$

• Shouldn't have trusted the byte counter, I forgot I was on Windows so the CR added 1 byte to the count. Feb 23 at 19:13
• You can make your function anonymous, and also use the new assignment operator to save a few bytes Feb 23 at 19:37

# Ruby, 62 51 bytes

->n,k{[*1..n-k.sum+z=k.size-1].combination(z).size}


Try it online!

# JavaScript (ES6), 65 bytes

Expects (n)(list). Uses the formula provided by the OP.

n=>a=>(n-=eval(a.join-1+),g=k=>!k||g(--k)*(k-n)/~k)(a.length-1)


Try it online!

### How?

The expression eval(a.join('-1+')) subtracts 1 from all entries in a[] except the last one and sums everything. For instance:

[ 2, 3, 4 ] --> "2-1+3-1+4" --> 7


So, this is equivalent to: $$\sum_{i=1}^{k} x_i-k+1$$

We could also use eval(a.join('+~-')) which subtracts 1 from all entries but the first one, leading to the same result.

The helper function g computes the combination.

# R, 46 bytes

(using n_choose_k)

function(x,y)choose(x-sum(y)+(z=sum(y|1)-1),z)


Try it online!

# R, 58 bytes

(by enumeration)

function(x,y)sum(rowSums(z<-expand.grid(Map(:,y,x)))==x)


Try it online!

# Julia 0.6, 38 bytes

n>N=n==[]?0^N:sum([n[2:end]].>0:N-n[])


Try it online!

### alternative answer, 38 bytes too

!N=0^N;!(N,x,t...)=sum(.!(0:N-x,t...))


Try it online!

a few more bytes with julia 1.0+

# Pyth, 14 bytes

.c+-hAQsHJtlHJ


Try it online!

Translation of zdimension's Python 3 answer.

# 14 bytes

/sMsM*F}RGeAQG


Try it online!

Translation of Jonathan Allan's Jelly answer.

# JavaScript (ES2020), 59 bytes

f=(n,[h,...t],s=0)=>eval('for(;n>=h;)s+=f(n-h++,t)')??!n&!h


f=(n,[h,...t],s=0)=>eval('for(;n>=h;)s+=f(n-h++,t)')??!n&!h

console.log(f(4, [0,0,2]));
console.log(f(121, [7,16,21,36,21,20]));

Firefox 72+, Chrome 80+, IE no. TIO currently out of date.

Simple brute force, literally.

• eval() return completion value of given statement(s).
• Completion value of for statement is completion value of its execute body in last iteration.
• Completion value of assignment is the value assigned.
• In case the control flow does not goes into for loop due to the looping condition, for statement has no completion value.
• As the result, eval(for(;n>=h;)...) returns the value of s (an integer) if once n>=h, and return undefined if n>=h never happened.
• ?? is nullish coalescing operator which is introduced in ES2020.
• If left side of ?? is null or undefined, it equals to right side. Otherwise, it returns left side (short circuit evaluation). (Similar as what ?? in C# do.)
• If n>=h is falsy, it may due to n<h or h is undefined.
• We found a valid integer partition as long as n == 0 and h is undefined (undefined value of h means the array is empty.).
• !n&!h check both n and h are falsy. As n may only be integers, it would be 0. h may be integers or undefined. But if h === 0, n >= h is true, the ?? operator short circuit current expression. As the result, we know h is undefined.

# Charcoal, 17 bytes

≔…¹ＬηζＩ÷Π⁺ζ⁻θΣηΠζ


Try it online! Link is to verbose version of code. Explanation: Based on the OP's formula.

≔…¹Ｌηζ


Get the exclusive range from 1 to k.

Ｉ÷Π⁺ζ⁻θΣηΠζ


Subtract the sum of xᵢ from N, add it element-wise to the the range, take the product, and divide by the product of the range. This is equivalent to calculating the number of combinations.