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 ? 
 A: 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}.$$
A: Here is an answer based upon generating functions.

The constraints $1 \leq x_i \leq k$ can be encoded for each $x_i$ as
  \begin{align*}
z+z^2+\cdots+z^k=z\frac{1-z^k}{1-z}\tag{1}
\end{align*}

In the following we denote with $[z^n]$ the coefficient of $z^n$ of a series.

Since we are looking for $x_1+x_2+\cdots+x_n=M$  we calculate according to (1)
  \begin{align*}
\color{blue}{[z^M]\left(z\frac{1-z^k}{1-z}\right)^n}&=[z^{M-n}]\frac{(1-z^k)^n}{(1-z)^n}\tag{2}\\
&=[z^{M-n}]\sum_{l=0}^n(-1)^l\binom{n}{l}z^{lk}\sum_{j=0}^\infty\binom{-n}{j}(-z)^j\tag{3}\\
&=\sum_{l=0}^{\lfloor(M-n)/k\rfloor}(-1)^l\binom{n}{l}[z^{M-n-lk}]\sum_{j=0}^\infty\binom{n+j-1}{n-1}z^j\tag{4}\\
&\color{blue}{=\sum_{l=0}^{\lfloor(M-n)/k\rfloor}(-1)^l\binom{n}{l}\binom{M-lk-1}{n-1}}\tag{5}
\end{align*}

Comment:


*

*In (2) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (3) we use the binomial theorem and the binomial series expansion.

*In (4) we use the linearity of the coefficient of operator and apply again the rule as in (2). We restrict the upper limit of the series accordingly, since the exponent of $z^{M-n-lk}$ is non-negative. We also use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

*In (5) we select the coefficients of $z^{M-n-lk}$.
