Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have one problem which needs to count the number of solution of the equation $$2x+7y+11z=42$$

where $x,y,z \in \{0,1,2,3,4,5,\dots\}$.

My attempt:

I noticed that that maximum value of $z$ could be $3$,hence $z \in \{0,1,2,3\}$ after this it was hit and trial for the remaining equations and finally I got $9$ solutions of $(x,y,z)$,however given a larger value in place of $42$ this approach would be tedious and very slow.

I realized that the general problem of this kind is to find the number of Solutions of a Diophantine equation of Frobenius,however I am not sure if there is any easy paper and pencil way for doing it,could anybody explain me an approach for the same?

Well,if there is none, does my approach is the only fastest approach for that particular problem?

share|improve this question
1  
What's $\mathbb W$? –  TonyK Sep 24 '11 at 13:21
1  
@TonyK:The whole number set. –  Quixotic Sep 24 '11 at 13:27
2  
So it's the same as $\mathbb Z$? I've never seen this notation before. –  TonyK Sep 24 '11 at 13:42
1  
@Fool: $\mathbb N$ is the more customary notation... –  J. M. Sep 24 '11 at 15:17
1  
@J.M:But not everyone includes $0$ in $\mathbb{N}$ ;) –  Quixotic Sep 24 '11 at 23:07

1 Answer 1

up vote 5 down vote accepted

This gets surprisingly tricky. See here for some techniques, as well as the papers of Eisenbrand and Eisenbrand and Rote in the bibliography.

Although it seems complicated, the three variable problem is easily computed by hand using the algorithms of Greenberg (or the equivalent algorithm of Davison.) Both papers are easily readable, and reduce the problem to a couple of runs of the Euclidean algorithm. These give you the fundamental region, but it is simple to go from that to enumerating the solutions.

If you want an even simpler algorithm, use the Euclidean algorithm to find $y$ and $z$ once you have chosen $x$ instead of using trial and error.

Added:

I cannot get to the library website right now to get URLs, but the two articles are (I am not sure that they are available free online.)

Davison, J. L. "On the Linear Diophantine Problem of Frobenius." J. Number Th. 48, 353-363, 1994.

Greenberg, H. "Solution to a Linear Diophantine Equation for Nonnegative Integers." J. Algorithms 9, 343-353, 1988.

these will give you a basis of the homogeneous solution, and a particular solution, and from there you are just counting lattice points in a triangle.

Added:

Ok, in retrospect I have given a correct but unhelpful answer, one of those famous "thereby reducing the problem to one already solved" answers, sorry. Having more time now, I will attempt to explain things clearly and concentrate on the problem at hand. In this example we can easily find a particular solution (0,6,0) (by inspection in this case, but the Euclidean algorithm will make this easy in general. We can see that (7,-2,0) is a homogeneous solution that generates all the homogeneous solutions with $z=0$, and (-2,-1,1) is another homogeneous solution and the two form a basis for the homogeneous space (again by inspection, but in general the Euclidean algorithm works wonders). So we can represent all solutions in the form $$(6,0,0) + m(7,-2,0) + n(-2,-1,1).$$ Our inequalities translate to $7m\ge 2$, $2m+n\le 6$ and $n\ge 0$. From here it is very easy to count the points inside the triangle using a sheet of graph paper.

If you get a very thin triangle you can apply Gaussian lattice basis reduction to make your basis vectors of the homogeneous space more orthogonal (this is essentially equivalent to the Euclidean algorithm and at heart what Greenberg and Davison are doing.) This will make your triangle fatter, making the points easier to count.

share|improve this answer
    
Could you give me the URL for those papers? –  Quixotic Sep 24 '11 at 23:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.