# 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?

• 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. Jul 29 '12 at 4:57
• For checking purposes, $293$ is the right answer. Jul 29 '12 at 5:00
• You might want to see this. Jul 29 '12 at 5:11
• Did you at least look at pages 172-173 of that book? Jul 29 '12 at 5:27

## 2 Answers

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! Jul 29 '12 at 16:30
• This is very nice! 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? Mar 17 '16 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. Mar 18 '16 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. Mar 19 '16 at 11:18

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. Jul 29 '12 at 16:44