Keep getting generating function wrong (making change for a dollar) [duplicate]

Possible Duplicate:
Making Change for a Dollar (and other number partitioning problems)

I am working on the classic coin problem where I would like to calculate the number of ways to make change for a dollar with a given number of denominations. From here, I am also going to be working on how to partition the number $100$ with at least two positive integers below $100$.

I have read over all the same posts on here and other sites and still I am unsure of what I am doing wrong.

The answer to our problem ($293$) is the coefficient of $x^{100}$ in the reciprocal of the following:

$$(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100}).$$

I do out this equation with $x = 100$ and get a really large return. My skills are very limited and most of the sites I have been reading over use terminology and operators/symbols I am unfamiliar with.

I look at this and think it seems very straight forward but, I get answers that way off. Are there any tips or steps that I could be overlooking?

Here is how you can compute the coefficient you are after without using symbolic algebra software, just any programming language where you can handle an array of $101$ integers; I'll assume for convenience that the array is called $c$ and is indexed as $c[i]$ where $i$ ranges from $0$ to $100$, because then $c[i]$ records the coefficient of $x^i$ in a power series.

To multiply such a power series by a binomial of the form $(1-ax^k)$ (with $k>0$) is easy: the coefficient $c[i]$ must be subtracted $a$ times from $c[i+k]$ for every $i$ for which this is possible (so $i+k\leq100$). One must make sure that the old value of $c[i]$ is being subtracted from $c[i+k]$, which can be achieved (in sequential operation) by traversing the values of $i$ in decreasing order.

To divide such a power series by a binomial of the form $(1-ax^k)$ is the inverse operation, which turns out to be even easier. The inverse of subtracting $a*c[i]$ from $c[i+k]$ is adding $a*c[i]$ to $c[i+k]$, and this must be performed for all $i$ in reverse order to what was done for multiplication, namely in increasing order.

So here is schematically the computation you need to perform:

• Initialise your array so that $c[0]=1$ and $c[i]=0$ for all $i>0$.
• For $k=1,5,10,25,50,100$ (in any order; multiplication is commutatitve) do:
  • for $i=0,1,\ldots,100-k$ (in this order) do:
    • add $c[i]$ to $c[i+k]$.
• Now $c[100]$ gives your answer.

This computation gives you the coefficient of $x^{100}$ in the power series for $1/((1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100}))$. Note however that your question asks to "partition the number $100$ with at least two positive integers below $100$", and to find that, one should omit the case $k=100$ from the outer loop, as this contributes (only) the partition of $100$ into a single part equal to $100$. The result with this modification is $292$.

The coefficient of $x^{100}$ means the multiplicative factor that appears along with $x^{100}$ as some term in the expansion of the expression. For example, the coefficient of $x$ in $$(1-x)^2 = 1 - 2x + x^2$$ is $-2$.

In this case, you want the coefficient of $x^{100}$ in $$\frac1{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100})}.$$

Without going into any details on how to find the coefficient, let me just show you how to look it up: if you go to Wolfram Alpha and type in "power series [that expression]", the first output box "Series expansion at $x = 0$" says: $$1 + x + x^2 + x^3 + x^4 + 2x^5 + O(x^6)$$

If you click on "More terms" it expands to something like

$$1+x+x^{2}+x^{3}+x^{4}+2 x^{5}+2 x^{6}+2 x^{7}+2 x^{8}+2 x^{9}+4 x^{10}+4 x^{11}+4 x^{12}+4 x^{13}+4 x^{14}+6 x^{15}+6 x^{16}+6 x^{17}+6 x^{18}+6 x^{19}+9 x^{20}+9 x^{21}+9 x^{22}+9 x^{23}+9 x^{24}+13 x^{25}+13 x^{26}+13 x^{27}+13 x^{28}+13 x^{29}+18 x^{30}+18 x^{31}+18 x^{32}+18 x^{33}+18 x^{34}+24 x^{35}+24 x^{36}+24 x^{37}+24 x^{38}+24 x^{39}+31 x^{40}+31 x^{41}+31 x^{42}+31 x^{43}+31 x^{44}+39 x^{45}+39 x^{46}+39 x^{47}+39 x^{48}+39 x^{49}+50 x^{50}+50 x^{51}+50 x^{52}+50 x^{53}+50 x^{54}+62 x^{55}+62 x^{56}+62 x^{57}+62 x^{58}+62 x^{59}+77 x^{60}+77 x^{61}+77 x^{62}+77 x^{63}+77 x^{64}+93 x^{65}+93 x^{66}+93 x^{67}+93 x^{68}+93 x^{69}+112 x^{70}+112 x^{71}+112 x^{72}+112 x^{73}+112 x^{74}+134 x^{75}+134 x^{76}+134 x^{77}+134 x^{78}+134 x^{79}+159 x^{80}+159 x^{81}+159 x^{82}+159 x^{83}+159 x^{84}+187 x^{85}+187 x^{86}+187 x^{87}+187 x^{88}+187 x^{89}+218 x^{90}+218 x^{91}+218 x^{92}+218 x^{93}+218 x^{94}+252 x^{95}+252 x^{96}+252 x^{97}+252 x^{98}+252 x^{99}+ \color{red}{293 x^{100}} +293 x^{101}+293 x^{102}+293 x^{103}+293 x^{104}+337 x^{105}+337 x^{106}+337 x^{107}+337 x^{108}+337 x^{109}+388 x^{110}+388 x^{111}+388 x^{112}+388 x^{113}+388 x^{114}+442 x^{115}+442 x^{116}+442 x^{117}+442 x^{118}+442 x^{119}+503 x^{120}+503 x^{121}+503 x^{122}+503 x^{123}+503 x^{124}+571 x^{125}+571 x^{126}+571 x^{127}+571 x^{128}+571 x^{129}+646 x^{130}+646 x^{131}+646 x^{132}+646 x^{133}+646 x^{134}+728 x^{135}+728 x^{136}+O(x^{137})$$

so you can see that the coefficient of $x^{100}$ is $293$.

That said, I doubt whether the generating function approach is any easier to compute with, than the more elementary way of writing down a recurrence relation, etc.