How many $k-$dimensional non-negative integer arrays $(x_1,\cdots,x_k)$ satisfies $x_1+x_2+\cdots+x_k\le n$

Question

The question is, how many $k-$dimensional non-negative integer arrays $(x_1,\cdots,x_k)$ satisfies $x_1+x_2+\cdots+x_k\le n$?

For example for $k=3,n=2$ we have $(0,0,0),(1,0,0),(0,1,0),(0,0,1),(2,0,0),(1,1,0),(1,0,1),(0,2,0),(0,1,1),(0,0,2)$ overall $10$ such vectors. Can we obtain a formula for this?

The number definitely smaller than $n^k$ due to the constraint. But how much is it smaller?

Answer 1

By "stars and bars" the number you are looking for is: $$ \binom{n+k}{k}. $$

The trick in the case of inequality is to add a "dummy" cell, which accumulates excess of the sum.

Answer 2

You add an integer 'l' such that

$x_1+x_2+\cdots+x_k + l = n$

number of non negative integers of such equation is give by

$\binom{n+(k+1)-1}{(k+1)-1}$ = $\binom{n+k}{k}$