Solve for the generating function with $x^1, x^5, x^{10}, x^{20}, x^{50}, x^{100}, x^{500}$

Question

How would you find the coefficient of $x^{2000}$ in

$ = (x^0 + x + x^2 +...)(x^0 + x^5 + x^{10} +...)(x^0 + x^{10} + x^{20}+...)(x^0 + x^{20} + x^{40} + ...)(x^0 + \\ \ \ \ \ \ \ \ \ \ \ x^{50} + x^{100} +...)(x^0 + x^{100} + x^{200} +...)(x^0 + x^{500} + x^{1000} +...)$

I've been trying to use Mathematica, but it's not giving me a solution (very new at using it).

Answer 1

So you have to find the number of non-negative integer solutions to:

$$a+5b+10c+20d+50e+100f+500g = 2000$$

A short C++ program with no more than 20 lines of code and a simple recurrence will serve for the purpose.

#include <iostream>

using namespace std;

int numSolutions(int *list, int size, int sum) {
    int num = list[0];
    if(size == 1) {
        return (sum % num == 0)? 1: 0;
    }
    int count = 0, cases = sum / num;
    for(int i = 0; i <= cases; i++) {
        count += numSolutions(list + 1, size - 1, sum - i * num);
    }
    return count;
}

int main() {
    int list[] = {500, 100, 50, 20, 10, 5, 1};
    int size = 7, sum = 2000;
    cout << numSolutions(list, size, sum);
}

...and the answer is: 86950230. Execution time is less than a second.