# Finding the number of solutions to a diophantine equation

I want to count total number of the natural solutions (different from 0) of the equation $2x + 3y + z = 100$, but don't know how. How can I calculate it using Mathematica? I tried:

Solve[{2*x + 3*y + z == 100, x > 0, y > 0, z > 0}, {x, y, z}, Integers]

This should work:

sols = Solve[{2*x + 3*y + z == 100, x > 0, y > 0, z > 0},
{x, y, z}, Integers];
Length@sols

There is an especially useful function for this kind of task: FrobeniusSolve[{a, b, c}, d] for finding the list of all solutions to the equation a x + b y + c z == d, where a,b,c are given positive integers and d is an integer, while x,y,z are non-negative integers to be found. There are many solutions (884 of them):

FrobeniusSolve[{2, 3, 1}, 100] // Short
{{0, 0, 100}, {0, 1, 97}, {0, 2, 94}, {0, 3, 91}, <<876>>, {48, 0, 4},
{48, 1, 1},  {49, 0, 2}, {50, 0, 0}}

Note that I used Short which omitted 876 solutions. If you need only positive solutions you can use e.g. DeleteCases to get lists free of 0:

DeleteCases[ FrobeniusSolve[{2, 3, 1}, 100], {___, 0, ___}] // Length
784

Edit

FrobeniusSolve is not a superfluous function since it is much more efficient than an adequate use of Solve. Consider e.g. the analogous equation 2 x + 3 y + z == 1000. We compare the timings of solving the same equation:

Solve[{2*x + 3*y + z == 1000, x >= 0, y >= 0, z >= 0}, {x, y, z}, Integers] //
Length // AbsoluteTiming
FrobeniusSolve[ {2, 3, 1}, 1000] // Length // AbsoluteTiming
{76.9510000, 83834}
{0.1900000, 83834}

This huge efficiency difference doesn't really change if we are to find positive solutions:

Solve[{2*x + 3*y + z == 1000, x > 0, y > 0, z > 0}, {x, y, z}, Integers] //
Length // AbsoluteTiming
DeleteCases[ FrobeniusSolve[{2, 3, 1}, 1000], {___, 0, ___}] // Length // AbsoluteTiming
{77.9720000, 82834}
{0.2420000, 82834}

Moreover, the lists of solutions have the same orderings; e.g.:

DeleteCases[ FrobeniusSolve[{2, 3, 1}, 200], {___, 0, ___}] ===
Solve[{2*x + 3*y + z == 200, x > 0, y > 0, z > 0}, {x, y, z}, Integers][[All, All, 2]]
True
• +1 for my favorite Frobenius* functions! – Silvia Sep 15 '12 at 18:48
• @Silvia Thanks ! Functions like FrobeniusSolve are indeed really useful. I think its documentation might be a bit more comprehensive. – Artes Sep 15 '12 at 19:56

There are also power series methods for counting these.

SeriesCoefficient[
x^(1 + 2 + 3)/(1 - x^1)*1/(1 - x^2)*1/(1 - x^3), {x, 0, 100}]

(* Out[118]= 784 *)
• Generating functions can be nice sometimes... – J. M.'s torpor Apr 17 '13 at 20:38