What is the number of possible combinations of d nonnegative integer numbers from 0 to N such that the sum equals N (and order matters)?

71 Views Asked by At

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?