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?

-

marked as duplicate by J. M., user26872, Did, sdcvvc, WilliamAug 31 '12 at 6:01

The coefficient of $x^{100}$. Not the value you get when you substitute $x = 100$. You shouldn't substitute $x$ to any value, just expand the expression (don't forget the reciprocal) and see what is the coefficient of the term $x^{100}$. This may not be the computationally easiest way to do it though. – ShreevatsaR Jul 29 '12 at 4:57
For checking purposes, $293$ is the right answer. – J. M. Jul 29 '12 at 5:00
You might want to see this. – J. M. Jul 29 '12 at 5:11
Did you at least look at pages 172-173 of that book? – J. M. Jul 29 '12 at 5:27

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.

-
tijko: This is an entirely different question. Before turning to it, will you at least acknowledge that the post above fully answers your question? – Did Jul 29 '12 at 8:16
@ShreevatsaR I'm looking into power series right now, thanks. – tijko Jul 29 '12 at 16:44

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

-
Marc van Leeuwen you and ShreevatsaR were very helpful. While this is all new to me your explanation cleared up a few things. I marked ShreevatsaR's response as the answer because it responded to my first question. I should have created a separate post for this, the follow up that you layed out nicely! – tijko Jul 29 '12 at 16:30
This is very nice! – joriki Sep 28 '12 at 12:17
I have tried this solution but I think its wrong because it counts some ways twice like 1+2 and 2+1 for 3. (Its a different problem, sum 200 and different coins) int[] coins = { 1, 2,5,10,20,50,100,200 }; int[] value = new int[201]; value[0] = 1; for (int i = 1; i < 201; i++) { for (int coin:coins) { if (i-coin >= 0) { value[i] += value[i-coin]; } } } Can you explain how your solution doesnt so that? – tomer.z Mar 17 at 16:17
@tomer.z No, this solution does not double-count for permuting terms in sums, because it is based on combining multiplicities of individual coins, taken in a fixed order. For instance multiplying $1(1-x^2)$ by $1/(1-x^5)$ is combining the possibilities to make some amount using only coins of value $2$ and another (complementary) amount using only coins of value $5$; basically the order of using coins is fixed beforehand. By the way this remark is not proper to my answer, but addresses the method already mentioned in the original question. – Marc van Leeuwen Mar 18 at 9:26
@tomer.z But looking more closely, your program does count sequences with things like 1+1+2 and 1+2+1 distinctly (so it gets value 5 at amount=4, rather than the proper result 3). This is because you interchanged placement of the the two loops. But my answer is quite clear about this: the loop on coins must be outside the loop over the positions $i$ (while you put it inside). This effectively forces coin types to be considered in a fixed order. – Marc van Leeuwen Mar 19 at 11:18