2
$\begingroup$

Given:

$x_1 + x_2 + ... + x_n = k$

where each $x_i$ can have some value between $0$ and $10$ (we might have $0\leq x_1\leq 7$ and we might have $0\leq x_2\leq 9$ and so on...)

How many nonnegative integer solutions are there to an equation like this, where each $x_i$ can take on any of the values in its range restrictions?

Is Mick A's answer applicable to this from the following? Number of solutions to equation, range restrictions per variable

If so, how would Mick A's answer be extended for equations of arbitrary lengths of the left-hand side? How could this be solved for programmatically?

EDIT: My thoughts are that we calculate $S$ and then subtract $S_1, S_2, ..., S_n$ from it, after which we add all intersections $S_1 \cap S_2, ...$ and then we subtract all "three-way intersections" $S_1 \cap S_2 \cap S_3, ... $ and then we add all the "four-way intersections" $S_1 \cap S_2 \cap S_3 \cap S_4,...$ and then we subtract all the "five-way intersections" etc...

Is this a correct approach?

$\endgroup$
6
  • $\begingroup$ The method described in your thoughts is correct. It is written up in more detail in the answers to this question. However, in the worst case, this requires a sum over $2^n$ possible multi-way intersections, so whether this counts as a valid programmatical solution depends on how big $n$ is. If you use the generating function method, this may be faster depending on the $n,k$ and the upper limits. $\endgroup$
    – Mike Earnest
    Commented Oct 5, 2021 at 20:51
  • $\begingroup$ Thank you for your reply, Mike. Do you have any resources or other answers to refer to, where the generating function method is implemented, for this particular problem? $\endgroup$
    – tmpquestionwonderer7777272
    Commented Oct 5, 2021 at 21:10
  • $\begingroup$ The algorithm in the approach to my answer will involve $\sum_{i=0}^k \binom{k}{i} = 2^k$ terms, each of which will either equal $0$, or have form $\binom{a}{b}$. There is a programmatic shortcut. Suppose that you have a binary counter that loops through $0$ through $[(2^k) - 1].$ Zero filled, this counter will loop through all of the $2^k$ possible binary strings of $1$'s and $0$'s. Reading (for example) right to left, you can have digit $i$ having the value $1$ rather than $0$ signify that the upper bound constraint on variable $x_i$ is violated. ...see next comment $\endgroup$
    – user2661923
    Commented Oct 6, 2021 at 22:59
  • $\begingroup$ You can then programmatically evaluate the specific term that corresponds to anyone of the $2^k$ binary numbers. Further, rather than attempting a $T_0, T_1, \cdots, T_k$ partition of the terms you can have the sign of the term be $(+1)$ rather than $(-1)$ if and only if the number of $1$'s in the corresponding binary string is even rather than odd. Further, you will notice that those terms that evaluate as positive, rather than $0$ will all have form $\binom{a}{k-1}$. ...see next comment $\endgroup$
    – user2661923
    Commented Oct 6, 2021 at 23:03
  • $\begingroup$ This means that you can have a preliminary step in your program where you evaluate all values $\binom{a}{k-1}$, where $(k-1) \leq a \leq [n + (k-1)]$. I know that Java (for example) provides a BigInteger class for integer only computations. Presumably, a similar facility is available for such programming languages as C or Python. The only challenge here, is if you have to calculate something like $\binom{100}{20}$. Personally, I would advise using the algorithm $$\frac{100 \times 99 \times \cdots \times 81}{20 \times 19 \times \cdots \times 1}$$ for such an expression. $\endgroup$
    – user2661923
    Commented Oct 6, 2021 at 23:09

1 Answer 1

Reset to default
-1
$\begingroup$

Let upper bound of $x_1,x_2..,x_n$ be given as $i_n$, then the answer is the coefficient of $x^k$ in the product:

$$ S= \prod_{j=1}^n (1 + x+x^2...+x^{i_1})$$

Now, suppose one was doing the problem by hand , then we can use a trick to reduce the calculations required in the above step. Consider the product,

$$ S'= \prod_{j=1}^n( \frac{1}{1-x} -\sum_{p=i_1+1}^k x^p)$$

It can be observed that in the above, the coefficient of $x^k$ is that of the one in $S$. The above form is also easier to compute. For instance, consider this problem:

Number of ways we can draw 6 chocolates drawn from 15 chocolates out of which 4 are blue, 5 are red and 6 are green if chocolates of the same colour are not distinguishable?

We are looking for solution of the equation $x_1 + x_2 + x_3 = 15$ with $0 \leq x_1 \leq 4$, $0 \leq x_2 \leq 5$ , $0 \leq x_3 \leq 6$. We have,

$$ S'= (\frac{1}{1-x} -x^5 -x^6)( \frac{1}{1-x} -x^6 ) ( \frac{1}{1-x} )= (\frac{1}{1-x} -x^5 -x^6)\left[\frac{1}{(1-x)^2} - \frac{x^6}{(1-x) }\right] \equiv \frac{1}{(1-x)^3} - \frac{x^6}{(1-x)^2}-\frac{x^5}{(1-x)^2} - \frac{x^6}{(1-x)^2}= \frac{1}{(1-x)^3} - \frac{2x^6}{(1-x)^2} - \frac{x^5}{(1-x)^2} $$

The above is quite easily calculable.

$\endgroup$
2
  • $\begingroup$ More details on the idea of dropping and inserting terms hwich preserve coefficients here $\endgroup$
    – Cathartic Encephalopathy
    Commented Apr 9, 2022 at 8:02
  • 1
    $\begingroup$ This is super inefficient. When $n=3$ and $(i_1,i_2,i_3)=(3,6,10)$, and $k=13$, your method requires expanding $$ \left(\frac1{1-x}-x^4-\dots-x^{13}\right)\left(\frac1{1-x}-x^7-\dots-x^{13}\right)\left(\frac1{1-x}-x^{11}-x^{12}-x^{13}\right) $$ which has way to many terms. The same problem instance would be doable by hand if you used the generating function method described in this answer. $\endgroup$
    – Mike Earnest
    Commented Apr 9, 2022 at 14:58

Not the answer you're looking for? Browse other questions tagged .