0
$\begingroup$

How do I find a closed form solution to number of non negative integer solutions of $l_1+l_2+...+l_m=n$ for constraint $l_i\leq k$. I know that without the constraint, the answer is $$n+m-1 \choose{m-1}$$. However, How would I deal with the constraint here?

$\endgroup$
  • 1
    $\begingroup$ Hint : Generating Functions $\endgroup$ – Jon Garrick Oct 14 '17 at 5:37
0
$\begingroup$

Although not exactly a closed solution, stars and bars can be extended with inclusion-exclusion.

This will lead to the following formula:

$$ \sum_{j=0}^m(-1)^j\binom mj\binom{n-j(k+1)+m-1}{m-1}\; $$

$j$ counts the number of variables where the constraint is violated, and you are to continue only while the upper binomial index $\ge$ lower on

If you don't like "continue only while the upper binomial index $\ge$ lower one.."

define $J = \lfloor \frac{m}{k}\rfloor$ to make the formula

$$ \sum_{j=0}^J(-1)^j\binom mj\binom{n-j(k+1)+m-1}{m-1}\; $$

or put everything into one formula, thus

$$ \sum_{j=0}^{\lfloor\frac{m}{k}\rfloor}(-1)^j\binom mj\binom{n-j(k+1)+m-1}{m-1}\; $$

$\endgroup$

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.