Constrained integer partition

Question

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 code-golf, so the lowest byte count for each language wins!

Answer 1

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

Answer 2

Haskell, 35 bytes

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

Try it online!

Answer 3

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

Answer 4

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}$$

Answer 5

Ruby, 62 51 bytes

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

Try it online!

Answer 6

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.

Answer 7

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!

Answer 8

Julia 0.6, 38 bytes

port of xnor's answer

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+

Answer 9

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.

Answer 10

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.

Answer 11

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.