1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ You should specify integer solutions (x_1,...) $\endgroup$ – quasi May 10 '17 at 9:20
  • $\begingroup$ Anyway, do you have particular values of $n,M$ that you are trying to analyze? $\endgroup$ – quasi May 10 '17 at 9:21
  • $\begingroup$ @quasi Thanks for pointing out the type , the value of n,m and k can be any integer value , quite be large also in range $\endgroup$ – Marvel May 10 '17 at 9:22
  • $\begingroup$ There is one coefficient trick. That turns out to be good only if you have specific values of the parameters. $\endgroup$ – Sayan May 10 '17 at 9:23
  • 1
    $\begingroup$ Your count for the case $k+1 \le x_i$ is not correct. It should be $$\binom{M-nk-1}{n-1}$$ $\endgroup$ – quasi May 10 '17 at 9:24
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\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.