2
$\begingroup$

How does one find the number of integral solutions of equations like,

$2x + 5y + 4z = 20$

I know how to do this counting if the coefficient of every variable on the LHS is $1$. But I don't know how to do this counting with arbitrary coefficients.

  • 0
    I don't know if this helps, but what you have there is a linear Diophantine equation in which Bézout's identity applies (http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity). It doesn't give any guidance with respect to counting though.2011-03-25

3 Answers 3

2

The linear equation $2x + 5y + 4z = 20$ has a two-parameter family of infinite solutions in integers. Note that $y$ has to be even. Further any even $y$ will give a one parameter family of infinite solutions for the equation $2x + 4z = 20 - 5y$.

Let $y = 2y_1$. Then we need to solve $2x + 4z = 20 - 10y_1 \implies x + 2z = 10 -5y_1$.

Hence, the set of all integer solutions is the two parameter family $(10-5y_1-2z_1,2y_1,z_1)$ where $y_1,z_1 \in \mathbb{Z}$

If you are interested in non-negative integral solutions for $(x,y,z)$, then we need $y_1 \geq 0$,$z_1 \geq 0$ and $5y_1 + 2z_1 \leq 10$.

This implies $y_1 \in \{0,1,2\}$.

If $y_1 = 0$, then $z_1 = \{0,1,2,3,4,5\}$.

If $y_1 = 1$, then $z_1 = \{0,1,2\}$.

If $y_1 = 2$, then $z_1 = \{0\}$.

Hence, the set of all non-negative solutions are $\{ (10,0,0),(8,0,1),(6,0,2),(4,0,3),(2,0,4),(0,0,5),(5,2,0),(3,2,1),(1,2,2),(0,4,0) \}$

The set of all positive solutions are $\{(3,2,1),(1,2,2)\}$

0

here is a paper on the problem i just happened to see somewhere else

  • 0
    What is the connection? I can't see how that hel$p$s solves my question!2011-03-31
-1

Let x' = 2x, y' = 5y and z' = 4z. Then 2 \leq x' \leq 18, 5 \leq y' \leq 15 and 4 \leq z' \leq 16 for x',y',z' \in \mathbb{Z}^{+}. So you can apply the same techniques for counting the number of integral solutions if all the coefficients on the LHS are $1$.

So the number of solutions would be the coefficient of $x^{20}$ in $\left[(x^2)^{a_1}+(x^2)^{a_1+1}+ \cdots+ (x^a)^{a_2} \right] \cdot \left[(x^5)^{b_1}+(x^5)^{b_1+1}+ \cdots+ (x^5)^{b_2}\right] \cdot \left[(x^4)^{c_1}+(x^4)^{c_1+1}+ \cdots+ (x^4)^{c_2} \right]$

where $a_1 \leq x \leq a_2$, $b_1 \leq y \leq b_2$ and $c_1 \leq z \leq c_2$.

  • 1
    I didn't understand your answer. What is $a_1$, $a_2$, $b_1$, $b_2$, $c_1$ and $c_2$ ? Can you give some background, references and some more explanations?2011-03-31