# How to determine all non-negative solutions to a combinatorial diophantine equation?

Hello,

I have an equation such as this. I do not have a Math background in my education, but I can read and understand Math pretty quickly. If I could be pointed to the right topics to solve this equation, it would be great. I want non-negative, integral solutions for the $a_i$'s Also, s is a given integer.

$\displaystyle\sum\limits_{i=2}^{n-1} a_i* {i \choose 2} = s$

Besides I have an added constraint : $\displaystyle\sum\limits_{i=2}^{n-1} i* a_i = n$ for any solution set {$a_i$}

I know its linear diophantine equation. But I am just wondering if there is any material which deals with this combinatorial diophantine equation straightaway. Otherwise, I have ventured into reading the basics of number theory before I can start reading papers that deal with Linear Diophantine Equations in n variables.

Thank you,

Mahesh Narayanamurthi

-
Because you want non-negative solutions, your problem will be similar to the postage stamp problem or Frobenius coin problem. Your added constraint is pretty tight however. You may be able to analyze that very quickly (and find similar equations in the literature). When you have those solutions you may be able to determine solutions to the first equation mechanically, although not necessarily in a closed form. Gerhard "Email Me About System Design" Paseman, 2011.06.28 –  Gerhard Paseman Jun 28 '11 at 21:48
Also, my first original piece of mathematics involved enumerating certain groupoids. The expression I came up with involved exponents which satisfied relations similar to yours. Will you provide motivation and/or the original problem that suggests studying these equations? Gerhard "Looking To Enhance And Borrow" Paseman, 2011.06.28 –  Gerhard Paseman Jun 28 '11 at 21:51
Finally, if you enumerate the number of solutions to your constraint for each n, you may be able to use Sloane's Integer Sequence Encyclopedia (oeis.org) to determine relations to other combinatorial objects and perhaps provide a formula or insight for your problem. Gerhard "Number After Number After Number" Paseman, 2011.06.28 –  Gerhard Paseman Jun 28 '11 at 21:55
I believe the solutions to the added constraint are enumerated at oeis.org/A083751 –  Gerry Myerson Jun 29 '11 at 0:31
@Gerhard: Thats exactly what I have been thinking, if I solve the constraint, then by means of elimination I can find the subset of solutions which would satisfy the first equation. The motivation for this: I am working on a problem in which I am mixing a subset of certain feasible points in N-dimensional and if I solve this set of equation(s), I have chosen the subset. @Gerry: I want the solutions {$a_i$}, I think what that Integer sequence gives is the number of solutions. –  mod0 Jul 9 '11 at 16:54

I echo Richard Stanley in his pessimism for there being a nice formula or method for giving you the solutions. On the other hand, most of the solutions will have a_i being 0 for most of the coefficients i. Here is another way to look at it, which might help you write a program for computer search for small n.

Your constraint summing to $n$ gives that $a_i + \epsilon_i = \frac{n}{i}$, where for most $i$, $0<\epsilon_i < 2$. Since you know most $a_i$ will be zero, $s$ will be not far from a sum of terms of the form $\frac{n(i-1)}{2}$, so many solutions will be close to partitioning an integer near $\frac{2s}{n}$ into distinct parts (so e.g. a partition of 20 into {1,4,4,5,6} is not allowed). This roughening of the problem can be easily programmed without expanding the search space too much.

If you still hope for more, you might try deriving some recurrences which might help in a partial characterization of solutions. It is my feeling that a quick program can be developed that will give you the solution set for any feasible s even for n as large as 50.

Gerhard "Email Me About System Design" Paseman, 2011.07.11

-

For simplicity let us change the last constraint to $\sum_{i=2}^n ia_i=n$. This makes no real difference since we have kept the number of solutions the same except in the case $s={n\choose 2}$, in which case the number of solutions increases from 0 to 1. If we set $f(n,s)$ equal to the number of solutions, then $$\sum_{n,s\geq 0}f(n,s)q^s x^n = \prod_{i\geq 2}(1-q^{{i\choose 2}}x^i)^{-1}.$$ I doubt whether much can be done with this. Certainly there is no simple formula for $f(n,s)$ since summing on $s$ gives $p(n)-p(n-1)$, where $p(m)$ is the number of partitions of $m$, for which a simple formula would be astonishing.

-
Hi Richard, Does this give me the solution set or the number of solutions? I want the solution set. Thank you, Mahesh –  mod0 Jul 9 '11 at 17:01