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

Question

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.

Answer 1

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.$$

Answer 2

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.$$