# Number of non-negative integer solutions for linear equations with constants

How do we find the number of non-negative integer solutions for linear equation of the form:

$$a \cdot x + b \cdot y = c$$

Where $a, b, c$ are constants and $x,y$ are the variables ?

-
Generating functions might help - the count is the coefficient of $x^c$ in $\dfrac{1}{(1-x^a)(1-x^b)}$. –  Thomas Andrews Jul 22 '13 at 21:03
Is there a known case where the number of solutions is not either $0$ or $\infty$? If $a,b,c \in \mathbb{Q}$, then any time $b | ka(1-c)$, $k\in\mathbb{N}$, then both $x$ and $y$ are integer solutions and I think there are infinitely many values of $k$ that solve the above. If any of the coefficients are irrational, then there are no integer solutions. –  AnonSubmitter85 Jul 22 '13 at 21:15
@AnonSubmitter85 - Yes, the number of sols is not either 0 or Infinity –  darthy734 Jul 22 '13 at 21:17
@AnonSubmitter85, note that $x, y \ge 0$, so there are not infinitely many solutions. –  George V. Williams Jul 22 '13 at 21:17
Have you found any answers for specific situations? For instance, if we assume that $a,b,c \in \mathbb{Q}$ and that $y = k \cdot \operatorname{lcm}(b_n,b_d)$, where $b = b_n/b_d$ and $k \in \mathbb{N}$, can you find ranges of $a$ and $c$ such that there are infinitely many or zero solutions? –  AnonSubmitter85 Jul 22 '13 at 22:09

Not a complete answer, but a relatively simple one and approximate one. By Schur's theorem of combinatorics?, the number of solutions is asymptotically ($c \to \infty$):

$$\frac{c}{ab}$$

Schur's theorem of combinatorics states that the number of solutions of (with $a_i$ relatively prime):

$$\sum_{i=1}^M a_i x_i = c$$

is:

$$\frac{c^{M-1}}{(M-1)!\prod a_i}$$

? This name is used by Wilf's Generatingfunctionology, but I cannot seem to find it elsewhere. It appears that Schur has many theorems.

-
I love Generatingfunctionology! –  Torsten Hĕrculĕ Cärlemän Jul 22 '13 at 21:23
@George V. Williams - Thanks, probably this might be the easiest way to get the desired result. Could you pls explain what is 'n' in the above equation ? –  darthy734 Jul 22 '13 at 21:28
@darthy734, my apologies, I wrote $n$ instead of $c$. It's fixed now. –  George V. Williams Jul 22 '13 at 22:54
You don't really need all of Schur for this - it is sort of obvious that $c/ab$ is approximation. –  Thomas Andrews Jul 23 '13 at 12:04
Do you have a source for this? Also, for c=5, M=2, a1=1, a2=2 this gives 2.5... –  Ella Shar Apr 26 at 4:41

You might be looking for Diophantine equations.

Check this link or this for an explanation!

-
He's not looking for how to solve it, he's looking for how to count non-negative solutions. –  Thomas Andrews Jul 22 '13 at 21:05
Maybe he was looking for small solution sets. Added because it provides a way to count solutions, mon ami. –  Torsten Hĕrculĕ Cärlemän Jul 22 '13 at 21:06
@ThomasAndrews - Can you please throw some more light on the generating functions method. –  darthy734 Jul 22 '13 at 21:06
@AnuragPallaprolu - Going through the link you've shared, will let you know once I'm done. –  darthy734 Jul 22 '13 at 21:08
@AnuragPallaprolu - Thanks for the link, but as Thomas mentioned, is there a way to get the number of non-neg solutions rather than solve for the whole set ? –  darthy734 Jul 22 '13 at 21:13