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?


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.