0
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ You need to find non-negative integer solutions to $$a+5b+10c+20d+50e+100f+500g = 2000$$ $\endgroup$ – Fly by Night Dec 18 '18 at 21:35
  • $\begingroup$ @FlybyNight could you explain how to do that? $\endgroup$ – Violet Jung Dec 18 '18 at 21:39
  • $\begingroup$ 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. $\endgroup$ – achille hui Dec 18 '18 at 23:52
  • $\begingroup$ @MathNewbie No, sorry. This is related to "partitions" and that is a very difficult combinatorial problem. en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$ – Fly by Night Dec 19 '18 at 0:46
2
$\begingroup$

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.

$\endgroup$

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.