Find the Number of Solution of equation
I have the following equation
$$x_1+x_2+x_3+x_4+x_5+...+x_n= M$$
and constraints is all elements should in between $1\leq x_i\leq k$. how to find the solution for the above equation.
I can easily found the number of solution of equation where $1\leq x_i$
Number of Solution: ${M-1 \choose n-1}$
Number of solution of equation where $k+1\leq x_i$
Number of Solution: ${M-n*(k+1)-1 \choose n-1}$.
But how to find the solution which satisfy the required criteria ?
We can use inclusion/exclusion principle here. The total number of solutions of equation such that $x_i \ge b_i k + 1$ is $\binom{M - k\sum_i b_i - 1}{n - 1}$, where $b_i \in \{\,0, 1\,\}$. Then the number of solutions such that $1 \le x_i \le k$ is $$\binom{M - 1}{n - 1} - \binom{n}{1} \binom{M - k - 1}{n - 1} + \binom{n}{2} \binom{M - 2k - 1}{n - 1} - \cdots + (-1)^{\left\lfloor \frac{M - n}{k}\right\rfloor} \binom{n}{\left\lfloor \frac{M - n}{k}\right\rfloor} \binom{M - \left\lfloor \frac{M - n}{k}\right\rfloor k - 1}{n - 1}\\ = \sum_{\ell = 0}^{\left\lfloor \frac{M - n}{k}\right\rfloor}(-1)^{\ell}\binom{n}{\ell}\binom{M - \ell k - 1}{n - 1}.$$