# find and count the number of solutions without multiplicity in Solve?

I would like to solve a Diophantine equation and find its solution, but I need only count one time for each $a$, i.e., when for some $a$ it found some $x,y,z$, then go to the next $a$. more precisely in the following code

Clear[x, y, z, p, a]
p=5;
Solve[{x + y + z - p == a && -p - 1 < a < p + 1 && x >= 1 && y >= x &&
z >= y}, {a, x, y, z}, Integers] // Column


I get

 {{a -> 1, x -> 1, y -> 1, z -> 4}},
{{a -> 1, x -> 1, y -> 2, z -> 3}},
{{a -> 1, x -> 2, y -> 2, z -> 2}}


but I only need one of them. Another question, when the above is done, I want also at the end to get the total number of solutions, as it may happen that for some $a$ in that interval there is no solutions. for example in the above code I count manually to get total number of 31 solutions, but I need to count for example only 8 solutions under the above condition (without multiplicity).

Thanks!

• Are you trying to avoid generating these solutions entirely or can you filter afterward? If the latter try // DeleteDuplicatesBy[First] // Column – Mr.Wizard Jan 24 '17 at 12:41

Something like the following?

p=5;
sols=Solve[{x+y+z-p==a&&-p-1<a<p+1&&x>=1&&y>=x&&z>=y},{a,x,y,z},Integers];

Tally[sols, #1[[1]]==#2[[1]]&]


{{{a->-2,x->1,y->1,z->1},1},{{a->-1,x->1,y->1,z->2},1},{{a->0,x->1,y->1,z->3},2},{{a->1,x->1,y->1,z->4},3},{{a->2,x->1,y->1,z->5},4},{{a->3,x->1,y->1,z->6},5},{{a->4,x->1,y->1,z->7},7},{{a->5,x->1,y->1,z->8},8}}

• I guess in your answer it solve all solution, but then filter it in the first component, and I guess it takes some time, is it possible to avoid this? I mean after finding the first solution for the initial component (here $a$), it goes to find the next solution for the next $a$. Finally I also needed to count all solutions. Thanks! – asad Jan 24 '17 at 20:52

The FindInstance command partially does the job:

p = 5;
Table[Union[  FindInstance[{x + y + z - p == j && -p - 1 < j < p + 1 && x >= 1 &&
y >= x && z >= y}, {x, y, z}, Integers], {a -> j}], {j, -2, 5}]


{{{x -> 1, y -> 1, z -> 1}, a -> -2}, {{x -> 1, y -> 1, z -> 2}, a -> -1}, {{x -> 1, y -> 2, z -> 2}, a -> 0}, {{x -> 2, y -> 2, z -> 2}, a -> 1}, {{x -> 2, y -> 2, z -> 3}, a -> 2}, {{x -> 1, y -> 2, z -> 5}, a -> 3}, {{x -> 1, y -> 2, z -> 6}, a -> 4}, {{x -> 1, y -> 2, z -> 7}, a -> 5}}

• Thanks for your answer, it does my job and is fast. The only remaining point is to count the answers (or non-answer if easier). also if it is possible to put $a$'s in the beginning instead of the end of each line? – asad Jan 25 '17 at 7:12

I recommend using FindInstance to obtain a single solution for each allowed value of $a$. The following uses generating functions to answer your questions about counting the number of solutions with and without multiplicity.

Rewrite in terms of variables ${u,v,w}$, where $x=u$, $y=u+v$, and $z=u+v+w$. The constraints on ${x,y,z}$ become $u\ge1$, $v\ge0$, and $w\ge0$. The original equation $x+y+z=p+a$ becomes $3u+2v+w=p+a$.

The series in dummy variable $s$ corresponding to $3u$ where $u\ge1$ is $s^3/(1-s^3)=s^3+s^6+s^9+...$.

The series corresponding to $2v$ where $v\ge0$ is $1/(1-s^2)=1+s^2+s^4+s^6+...$.

The series corresponding to $w$ where $w\ge0$ is $1/(1-s)=1+s^1+s^2+s^3+...$.

The coefficient of $s^{p+a}$ in the product of these three series give the number of integer solutions to $x+y+z=p+a$.

Series[s^3/(1 - s^3)*(1/(1 - s^2))*(1/(1 - s)), {s, 0, 15}]


s^3 + s^4 + 2 s^5 + 3 s^6 + 4 s^7 + 5 s^8 + 7 s^9 + 8 s^10 + 10 s^11 + 12 s^12 + 14 s^13 + 16 s^14 + 19 s^15

For example, the above series shows that for parameter $p=5$, when $a=-5$ to $a=5$ there are ${0,0,0,1,1,2,3,4,5,7,8}$ solutions, respectively.

The coefficients of $s^0$, $s^1$, and $s^2$ are always zero because of the $3u$ term and the constraint that $u\ge1$.

Given parameter $p$, the total number of solutions for all allowed $a$ between $a=-p$ and $a=p$ including multiplicity is given by the following generating function. One additional term $1/(1-s)$ is included in the product. The coefficient of $s^{2p}$ of this series gives the total number of solutions to the equation, including multiplicity.

Series[s^3/(1 - s^3)*(1/(1 - s^2))*(1/(1 - s))*(1/(1 - s)), {s, 0, 15}]


s^3 + 2 s^4 + 4 s^5 + 7 s^6 + 11 s^7 + 16 s^8 + 23 s^9 + 31 s^10 + 41 s^11 + 53 s^12

Given parameter $p$, all $a$ between $a=-p+3$ and $a=p$ produce at least one solution to $x+y+z=p+a$. Therefore, the count of solutions without multiplicity is $2(p-1)$.

• your answer is inspiring but I am not sure if it works for general equations as I gave here a simple question. "FindInstance" gives only one solution, but I need to go to check if there is a solution for the next $a$ in the domain after finding (or not finding if not exists) one solution for some present $a$. – asad Jan 25 '17 at 7:02
• @asad It's discouraging to answer your question and then find it is not the question you want answered. Nevertheless, I enjoy the challenge of Diophantine equations. So, can you tell me the equation you actually want to solve? – KennyColnago Jan 25 '17 at 15:33