# Finding the number of solutions to $x+2y+4z=400$

My question is how to find the easiest way to find the number of non-negative integer solutions to $$x+2y+4z=400$$ I know that I can use generating functions, and think of it as partitioning $400$ with $x$ $1$'s, $y$ $2$'s, and $z$ $4$'s. The overall generating function is: $$(1+x+x^2 + \cdots x^{400})(1+x^2+x^4+\cdots x^{200})(1+x^4+x^8+\cdots x^{100})$$ And then from this I have to calculate the coefficient of $x^{400}$, which I don't know how to do. If there's an easier way to do, I'd love to know.

My question is how to find the easiest way to find the number of non-negative integer solutions to $$x+2y+4z=400$$

I think the following way is easy (I'm not sure if it's the easiest, though).

Since $x+2y+4z=400$, $x$ has to be even. So, setting $x=2m$ gives you $$2m+2y+4z=400\Rightarrow m+y+2z=200.$$ Since $m+y$ has to be even, setting $m+y=2k$ gives you $$2k+2z=200\Rightarrow k+z=100.$$

There are $101$ pairs for $(k,z)$ such that $k+z=100$. For each $k$ such that $m+y=2k$, there are $2k+1$ pairs for $(m,y)$.

Hence, the answer is $$\sum_{k=0}^{100}(2k+1)=1+\sum_{k=1}^{100}(2k+1)=1+2\cdot \frac{100\cdot 101}{2}+100=10201.$$

• interesting solution. Could you elaborate on why the number of pairs for $(m, y)$ is $2k + 1$? – Vishwa Iyer Aug 8 '14 at 12:58
• (+1) This is a rather clever trick. I just used analytic combinatorics like a hammer, instead :) – Jack D'Aurizio Aug 8 '14 at 13:02
• @VishwaIyer: Sure! You can see $(m,y)=(0,2k),(1,2k-1),\cdots,(2k,0)$ – mathlove Aug 8 '14 at 13:02
• @JackD'Aurizio: Thanks! I like the hammer, though:) – mathlove Aug 8 '14 at 13:04
• @mathlove when you find that $k +z = 100$, why isn't there only 101 possible combinations? for every value of $k = 0$ to $k = 101$, there is only one value of $z$ to make this equality true, hence only 101 possibilities? – Varun Iyer Aug 8 '14 at 13:17

You were on the right track, but instead of truncating the factors, just consider the coefficient of $x^{400}$ in: $$(1+x+x^2+x^3+\ldots)(1+x^2+x^4+x^6+\ldots)(1+x^4+x^8+x^{12}+\ldots)=\frac{1}{(1-x)(1-x^2)(1-x^4)},\tag{1}$$ then write the RHS of $1$ as a sum of terms like $\frac{A}{(1-\xi x)^k}$, with $\xi\in\{1,-1,i,-i\}$, and exploit the identities: $$\frac{1}{1-\xi x}=\sum_{k=0}^{+\infty}(\xi x)^k,$$ $$\frac{1}{(1-\xi x)^2}=\sum_{k=0}^{+\infty}(k+1)(\xi x)^k,$$ $$\frac{1}{(1-\xi x)^3}=\sum_{k=0}^{+\infty}\frac{(k+2)(k+1)}{2}(\xi x)^k$$ to recover the final expression:

$$[x^n]\frac{1}{(1-x)(1-x^2)(1-x^4)}=\frac{2n^2+14n+21}{32}+\frac{(7+2n) (-1)^n}{32}+\frac{1}{8} \cos\left(\frac{n \pi }{2}\right)+\frac{1}{8} \sin\left(\frac{n \pi }{2}\right)$$

that if $8\mid n$ becomes:

$$[x^n]\frac{1}{(1-x)(1-x^2)(1-x^4)}=\frac{1}{16}(n+4)^2.$$

• I'm confused when you "recover the final expression", did you use the identities above and find the nth term of the sequence? And where did the $\sin$ and $\cos$ come from as well? – Vishwa Iyer Aug 8 '14 at 13:20
• Yes, I just used the identites derived from above. That combination of $\sin$ and $\cos$ just comes from $(2+2i)(-i)^n+(2-2i)i^n$. – Jack D'Aurizio Aug 8 '14 at 13:26
• Another question, you can avoid using epsilon completely and just set it equal to 1, right? And you got these identities through differentiating the first one, right? – Vishwa Iyer Aug 8 '14 at 13:50
• And would you mind showing the steps you made to arrive at the final expression? I'm trying the same process you did and I can't seem to derive the expression. – Vishwa Iyer Aug 8 '14 at 13:55