shekita@crys.WISC.EDU (Eugene Shekita) (10/17/86)
As many of you know, the number of non-negative integer solutions to the equation: x + x + ... + x = m 1 2 n is C(n + m - 1, n) where C(x, y) means x things taken y at a time. Is there an expression for the number of non-negative integer solutions to equations of the form: c x + c x + ... + c x = m 1 1 2 2 n n where the c are positive integer constants? i E. Shekita shekita@provolone.wisc.edu
kaden@osiris.CSO.UIUC.EDU (10/20/86)
I saw how this was solved in a graduate economics course, once. Assume {c1,...,cn} = {1,...,1}. Then we have our first problem, which has already been solved.
eklhad@ihuxv.UUCP (K. A. Dahlke) (10/21/86)
>Is there an expression for the number of non-negative integer solutions >to equations of the form: > > c x + c x + ... + c x = m > 1 1 2 2 n n > >where the c are positive integer constants? > i Ouch. You want a "formula" for the number of solutions to a specific class of diaphantine equations. Any formula would have to contain things like: if the greatest common divisor of ... divides such and so, etc. For example, 4x + 38y + 152z = 667839 has no solutions; and although 999x + 1000y + 1001z = 3004 has solutions, it has no non-negative solutions. When m is large, the number of solutions can be estimated by finding a few proximal solutions. (Procedures exist for this.) Since solutions line up like atoms in an n-1 dimensional crystalline latus, we can divide the volume of a unit cell into the volume of that portion of the hyperplane whose coordinates in Rn are all positive. The accuracy is proportional to m, since surface area (where the partial cells are) to volume ratios go as 1/m. Similarly, accuracy is inversely related to the size of the coefficients. This isn't very useful if you want an exact answer. Let me know if you obtain a "formula"; I would be quite interested. -- Karl Dahlke ihnp4!ihnet!eklhad