Suppose that we are given two values: d and N.
We want to know what is the number of possible d-dimensional vectors of non-negative integer numbers, that vector sum is always equal to N.
For example, if we say d=2 and sum=10 the number of possible vectors is equal to 11:
array([[ 0, 10],
[ 1, 9],
[ 2, 8],
[ 3, 7],
[ 4, 6],
[ 5, 5],
[ 6, 4],
[ 7, 3],
[ 8, 2],
[ 9, 1],
[10, 0]])
Or, for d=3 and sum=10 the number of possible vectors is 66:
array([[ 0, 0, 10],
[ 0, 1, 9],
[ 0, 2, 8],
[ 0, 3, 7],
[ 0, 4, 6],
[ 0, 5, 5],
[ 0, 6, 4],
[ 0, 7, 3],
[ 0, 8, 2],
[ 0, 9, 1],
[ 0, 10, 0],
[ 1, 0, 9],
[ 1, 1, 8],
[ 1, 2, 7],
.
.
.
[ 6, 2, 2],
[ 6, 3, 1],
[ 6, 4, 0],
[ 7, 0, 3],
[ 7, 1, 2],
[ 7, 2, 1],
[ 7, 3, 0],
[ 8, 0, 2],
[ 8, 1, 1],
[ 8, 2, 0],
[ 9, 0, 1],
[ 9, 1, 0],
[10, 0, 0]])
Just in case you are interested in, here I put the code that gives you all possibe vectors:
import numpy as np
def combinations_recursive_inner(n, buf, gaps, tsum, accum, tot):
if gaps == 0:
accum.append(list(buf))
else:
for x in range(0, tot+1):
if tsum + x + (gaps - 1) * tot < tot:
continue
if tsum + x > tot:
break
combinations_recursive_inner(n, buf + [x], gaps - 1, tsum + x, accum, tot)
def combinations_recursive(d, tsum):
accum = []
combinations_recursive_inner(d, [], d, 0, accum, tsum)
return np.array(accum)
print(combinations_recursive(d=3,tsum=10))
So, is there any formula that, given d and N, tell us the possible combinations?