Question

Looking for the different ways to find the number of nonnegative integer solutions to

a + 2b + 3c = 18

Answer 1

Perhaps a modified stars-and-bars approach?
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Answer 2

We have spreadsheets and computer programs. We can do exhaustion with little effort.

Answer 3

@HolsterEmission I think it is a good idea. As it is, stars-and-bars is for solving equations of type a+b+c = n. We may start with this and make it useful somehow, not sure...

Answer 4

Here is one method that I have discovered while playing with `linear` equations like these.

Analogous to solving system of equations in linear algebra(Ax=b),
I started by finding a `particular solution` : (18, 0, 0)
and `two null solutions` : (0, -3, 2) and (-3, 0, 1)

Then the `complete solution` can be expressed as
(a, b, c) = (18, 0, 0) + s(0, -3, 2) + t(-3, 0, 1)

Not sure if above really cover `all` the possible solutions..

Answer 5

Suppose we set \(x=a+b+c\), \(y=b+c\), and \(z=c\). Then
\[a+2b+3c=x+y+z=18\]has \(\dbinom{18+3-1}{3-1}=\dbinom{20}2=190\) possible solutions.

Now if only there were a quick way to filter out the solutions where \(3|z\) and \(2|y\)...

Answer 6

Mathematica says this has \(37\) solutions.
`Length[FrobeniusSolve[{1, 2, 3}, 18]]`
`(* 37 *)`

Also, apparently the number of solutions to \(a+2b+3c=n\) has a closed form of \(\mathrm{round}\dfrac{(n+3)^2}{12}\) (which checks out, depending on the definition of \(\mathrm{round}\)).
http://oeis.org/A001399

Answer 7

Interesting... that oeis link has more than a dozen formulas for this !

Answer 8

And according to
https://en.wikipedia.org/wiki/Partition_(number_theory)
the number of solutions also corresponds to the coefficient of \(x^{18}\) in
\[\prod_{i=1}^3\frac{1}{1-x^i}=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^5+\cdots)\]but there doesn't seem to be a simple formula for the coefficient of the \(n\)th power term...

Answer 9

From your method using stars-and-bars, it appears 190 is a upper bound for the number of solutions to any equation of form ax + by + cz = n

Answer 10

generating functions are neat, I feel there exists some clever way to find the x^18 th coefficient..

Answer 11

Using that product formula, we can shorten the work (by how much, not sure) to finding the coefficient of the \(x^{18}\) term in the expansion of
\[\sum_{i=1}^{18}x^n\times\sum_{i=1}^9x^{2n}\times\sum_{i=1}^6x^{3n}\]since these cover all the terms that contribute to getting that \(x^{18}\) term.

Answer 12

Figuring out which terms actually contribute brings us back to the original problem, though...

Answer 13

Ahh I see... Actually I got stuck with this while trying another problem posted by one of our users recently :
Find the number of terms with integer coefficients in the expansion of \[(1 + \sqrt{2}x + \sqrt[3]{5}x^2)^{18}\]

http://openstudy.com/users/ganeshie8#/updates/5832df68e4b01f730e9fc5fc

Answer 14

Maybe we can consider a simpler problem and try to extrapolate from that? Take
\[a+2b+3c=6\implies a=6-2b-3c\]We could list all the possible multiples of \(2\) and \(3\) that we can take from the RHS to make sure that \(0\le a\le6\). These are
\[\begin{array}{cc|cccc}
&c&0&1&2\\
b\\
\hline
0&&(0,0)\to6&(0,1)\to3&(0,2)\to0\\
1&&(1,0)\to4&(1,1)\to1&\color{lightgray}{(1,2)\to-2}\\
2&&(2,0)\to2&\color{lightgray}{(2,1)\to-1}&\color{lightgray}{(2,2)\to-4}\\
3&&(3,0)\to0&\color{lightgray}{(3,1)\to-3}&\color{lightgray}{(3,2)\to-6}
\end{array}\]giving us \(7\) possible solutions.

For the problem at hand, we'd have to check a lot more pairs, with \(b\in\{0,1,\ldots,9\}\) and \(c\in\{0,1,\ldots,6\}\).
\[\begin{array}{cc|cccc}
&c&0&1&\cdots&6\\
b\\
\hline
0&&\\
1&&\\
\vdots\\
9&&
\end{array}\]

Answer 15

Exactly what I'm thinking at the moment.
From your listing, it becomes easy to see that the number of nonnegative integer solns to `a + 2b + 3c = 6` is same as the number of nonnegatie integer solns to `2b + 3c <= 6`. In other words number of lattice points lying inside the trianlge :