# Solving $x+2y+5z=100$ in nonnegative integers

I have not done combinatorics since high school, so this is an embarrassingly simple question.

We can solve the diophantine equation $x+y+z=100$ in nonnegative integers using the "bars and boxes" combinatorial method. We have $100$ dots, and we want place 2 partition markers among them, so the answer is ${ 102 \choose 2}$. Is there a way to generalize this (by a change of variable, perhaps) to equations like $x+2y+5z=100$? I know we can handle the case where we need to solve in positive integers by making the substitutions $x\rightarrow x+1$ and so forth, but I can't think of a way to apply a similar technique when the coefficients aren't $1$.

If not, is there a slick way to handle these more general equations?

-
Generating functions are reasonably slick. – André Nicolas Mar 30 '13 at 1:16
@AndréNicolas: I don't know, as much as I love generating functions, I've never found a slick way of actually calculating the answer in closed form (the step after saying "the answer is the coefficent of $x^n$ in [some expression]"). Sometimes it even feels as though we're back to the original problem. Anyway most alleged answers I see on the net given using generating functions seem to leave out how to calculate the coefficient, so it seems like cheating to me. – ShreevatsaR Mar 30 '13 at 1:49
They are pretty good for getting asymptotic estimates. – André Nicolas Mar 30 '13 at 1:53

You can solve this problem by using the idea of generating functions; specifically, for the example above, let $c_n$ be the number of positive integer solutions to the equation

$$x+2y+5z=n$$

Then the generating function $f(a)$ for the sequence $a_i$ is

$$f(a)=c_0+c_1a+c_2a^2+c_3a^3+...+c_na^n+...$$

We have

$$f(a)=(1+a+a^2+...+a^i+...)(1+a^2+a^4+...+a^{2j}+...)(1+a^5+a^{10}+...+a^{5k}+...)$$

The exponents $i, j, k$ correspond the values of $x, y, z$ respectively in your equation above.

However, expanding that polynomial is still quite inconvenient. As such, we can re-write the formula as follows

$$f(a)=\frac{1}{1-a}\frac{1}{1-a^2}\frac{1}{1-a^5}$$

Using partial fractions, we re-write $f(a)$ as follows

$$f(a)=\frac{-a^4-a^3+a^2+1}{5(1-a^5)}+\frac{13}{40(1-a)}+\frac{1}{8(1+a)}+\frac{1}{4(1-a)^2}+\frac{1}{10(1-a)^3}$$

$$f(a)=\frac{1}{5}(-a^4-a^3+a^2+1)(1+a^5+a^{10}+a^{15}+...)+\frac{13}{40}(1+a+a^2+a^3+...)+\frac{1}{8}(1-a+a^2-a^3+a^4-...)+\frac{1}{4}(1+2a+3a^2+4a^3+...)+\frac{1}{10}(1+3a+6a^2+10a^3+15a^4+...)$$

Therefore, $$c_{100}=\frac{1}{5}+\frac{13}{40}+\frac{1}{8}+\frac{1}{4}\times 101+\frac{1}{10}\times \binom{102}{2}=541$$

-
By the way, as the first three coefficients are so small, the answer can be rewritten as the ceiling of $(n+1)/4+((n+2)(n+1))/20=((n+7)(n+1))/20$. – Vincent Tjeng Mar 30 '13 at 1:55
+1. Very nice.${}$ – user17762 Mar 30 '13 at 1:56
(+1) Nice answer. – Mhenni Benghorbal Mar 30 '13 at 2:39
+1 for getting the actual coefficients at the end; this one is slick! So for general $n$, we have $c_n = \frac{1}{10}\binom{n+2}{2} + \frac{1}{4}(n+1) + \frac{13}{40} + \frac{1}{8}[1, -1]_{n\bmod 2} + \frac{1}{5}[1, 0, 1, -1, -1]_{n\bmod 5}$ where $a\bmod b$ denotes the unique $0 \le r < b$ such that $a \equiv r \pmod b$, and I made up the notation $[a_0, \dots, a_n]_{i}$ to mean $a_i$. – ShreevatsaR Mar 30 '13 at 4:03

We can also solve it without generating functions as follows.

First, as a lemma, what is the number of nonnegative solutions to $x + 2y = n$? For any choice of $y$ such that $0 \le 2y \le n$, we have a unique solution (take $x = n - 2y$), so the number of solutions is the number of such choices, i.e. $\lfloor \frac{n}{2} \rfloor + 1$ (or, if you like, $\lceil \frac{n+1}{2} \rceil$).

Now the number of solutions to $x + 2y + 5z = n$: for each choice of $z$ such that $0 \le 5z \le n$, the number of solutions is that of $x + 2y = n - 5z$. The total number of solutions is got by adding them up.

For $n = 100$, the number $n - 5z$ takes values (enumerating the odd and even ones separately) $0, 10, \dots, 100$ and $5, 15, \dots, 95$, so the total number of solutions is \begin{align} &\phantom{=} \left(\left\lceil \frac{0+1}{2} \right\rceil + \left\lceil \frac{10+1}{2} \right\rceil + \dots + \left\lceil \frac{100+1}{2} \right\rceil\right) + \left(\left\lceil \frac{5+1}{2} \right\rceil + \left\lceil \frac{15+1}{2} \right\rceil + \dots + \left\lceil \frac{95+1}{2} \right\rceil \right)\\ &= \left(1 + 6 + \dots + 51\right) + \left(3 + 8 + \dots + 48\right) \\ &= 286 + 255 = 541. \end{align}

-
+1 nice! but why do you enumerate the answers separately? – Vincent Tjeng Mar 30 '13 at 2:48
@VincentTjeng: Just because $1 + 3 + 6 + 8 + \dots + 41 + 46 + 48 + 51$ is more easily recognizable/summable when written as the sum of two disjoint arithmetic progressions. :-) (This break-up happens because $\lceil k/2 \rceil$ is either $k/2$ or $(k+1)/2$ depending on whether $k$ is even or odd.) – ShreevatsaR Mar 30 '13 at 2:58
okay, I understand now! – Vincent Tjeng Mar 30 '13 at 3:06