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

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

• You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$ – Fly by Night Dec 18 '18 at 21:35
• @FlybyNight could you explain how to do that? – Violet Jung Dec 18 '18 at 21:39
• You can ask WA to compute the number using command SeriesCoefficient[ 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)*(1-x^500)),{x,0,2000}] (same command should work on Mathematica), the number you want is 86950230. – achille hui Dec 18 '18 at 23:52
• @MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory) – Fly by Night Dec 19 '18 at 0:46

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.