I need the number of solutions to the problem $100 = 10x_1 +8x_2 + 5x_3 + 7x_4 + 11x_5$ with the constraints that $x_1$ is even, $x_2$ is greater than or equal to 2, $x_3$ is 0 or 4, $x_4$ is less than or equal to 3.

I have my generating function as $(1 + x^{10} + x^{20} + ...)(x^{16} + x^{24} + ...)(1 + x^{20})(1 + x^7 + x^{14} + ...)(1 + x^{11} + x^{22} + ...)$

And I factored out an $x^{16}$ so now I need the coefficient of $x^{84}$ in the generating function

$(1 + x^{10} + x^{20} + ...)(1 + x^{8} + x^{16} + ...)(1 + x^{20})(1 + x^7 + x^{14} + ...)(1 + x^{11} + x^{22} + ...)$

but I don't know how to operate on it with the multiples of $x$ in the function, I tried substituting in things like $a = x^{10}, b = x^{7}$, but I don't know where to go from there with multiple variables in the function.

  • $\begingroup$ The coefficient of $x^{84}$ is $1$. $\endgroup$ – science Feb 12 '15 at 18:56
  • $\begingroup$ One way to find the answer is to truncate all the infinite series at $x^{84}$ or less, thereby turning the problem into a problem of expanding the product of polynomials, and then use a computer algebra system do the dirty work. $\endgroup$ – awkward Feb 12 '15 at 23:28

Generating functions are sometimes helpful but sometimes they just give you a different way to phrase your problem, and the problem doesn't become any easier to solve. It looks like this is the case for your problem. If you really want to use generating functions, then your generating function should actually be

$$(1 + x^{20} + x^{40} + \ldots)(x^{16} + x^{24} + \ldots)(1 + x^{20})(1 + x^{7} + x^{14} + x^{21})(1 + x^{11} + x^{22} + \ldots)$$

Notice the difference in a couple of the factors. So now you want the coefficient of $x^{100}$. Notice that there aren't that many possibilities because your coefficients are pretty big in your original equation, and also you have restrictions on the variables. So you could brute force this.


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.