3
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ interesting solution. Could you elaborate on why the number of pairs for $(m, y)$ is $2k + 1$? $\endgroup$ – Vishwa Iyer Aug 8 '14 at 12:58
  • $\begingroup$ (+1) This is a rather clever trick. I just used analytic combinatorics like a hammer, instead :) $\endgroup$ – Jack D'Aurizio Aug 8 '14 at 13:02
  • $\begingroup$ @VishwaIyer: Sure! You can see $(m,y)=(0,2k),(1,2k-1),\cdots,(2k,0)$ $\endgroup$ – mathlove Aug 8 '14 at 13:02
  • 1
    $\begingroup$ @JackD'Aurizio: Thanks! I like the hammer, though:) $\endgroup$ – mathlove Aug 8 '14 at 13:04
  • $\begingroup$ @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? $\endgroup$ – Varun Iyer Aug 8 '14 at 13:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Vishwa Iyer Aug 8 '14 at 13:20
  • $\begingroup$ 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$. $\endgroup$ – Jack D'Aurizio Aug 8 '14 at 13:26
  • $\begingroup$ 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? $\endgroup$ – Vishwa Iyer Aug 8 '14 at 13:50
  • $\begingroup$ 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. $\endgroup$ – Vishwa Iyer Aug 8 '14 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.