0

Given: $100$ banknotes of $20\$$, $100$ banknotes of $50\$$ and $100$ banknotes of $100\$$. How many ways are to create a pile with the amount of $n$? Notice that you cannot differ between banknotes with the same amount.

I was asked to create a generating function for this problem. The answer is:
$${{{{({x^{20}})}^{101}} - 1} \over {{x^{20}} - 1}} \cdot {{{{({x^{50}})}^{101}} - 1} \over {{x^{50}} - 1}} \cdot {{{{({x^{100}})}^{101}} - 1} \over {{x^{100}} - 1}}$$

I'm not quite sure how to get it. What's the explanation behind this expression?

AnnieOK
  • 2,920
  • 1
    Recall the formula for a finite geometric sum: $1 + x + \cdots + x^n = \frac{x^{n+1} - 1}{x - 1}$. Does that help? – Viktor Vaughn May 15 '14 at 21:39
  • So, it's actually $(1+x+...+x^{100})\cdot (1+x+...+x^{50})\cdot (1+x+...+x^{20})$. Isn't it the number of possibilities choosing $n$ banknotes? (and not banknotes with the sum of $n$). – AnnieOK May 15 '14 at 22:18
  • Not quite. (I probably should have used a different letter from $x$ in my formula.) For instance, $$ \frac{(x^{20})^{101} - 1}{x^{20} - 1} = 1 + x^{20} + (x^{20})^2 + \cdots + (x^{20})^{100} , . $$ – Viktor Vaughn May 15 '14 at 22:42

0 Answers0