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

Question

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

Answer 1

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

Answer 2

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.