# Find the number of ways of making change for a dollar with coins where the number of coins is odd

I feel like that I should use generating functions but even if I can count the combinations, I can't find a way to get the ones with an odd number of coins. Hints?

P. S. Cents, nickels, dimes and quarters are allowed

1 dollar = 100 cents
1 nickel = 5 cents
1 dime = 10 cents
1 quarter = 25 cents

• What coins are allowed? What did you try? – Qudit Sep 20 '17 at 20:06
• It might be worth finding all the ways to make change (which is even + odd), then finding (even-odd) by slightly changing the generating function. From that you can solve for even and odd. – Steve D Sep 20 '17 at 20:09
• maybe you should explain what nickels, etc. are !? – G Cab Sep 20 '17 at 20:25
• @SteveD I don't get this bit. With the generating functions I can determine the number of combinations by finding the 100 exponent but I have no clue about how to proceed. :( – AMeoni Sep 20 '17 at 20:57

Here's the generating function solution:

The generating function that counts all ways of making change is:

$$\text{all}(x) = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}$$

[That is, the coefficient of $x^{100}$ is the number of ways to make change of a dollar.]

If we look at the function

$$\text{alternating}(x) = \frac{1}{(1+x)(1+x^5)(1+x^{10})(1+x^{25})}$$

Then the coefficient of $x^{100}$ is (number of ways to do it with even number of coins) - (number of ways to do it with odd number of coins) [can you see why?]. From here you can easily solve for both (even number of ways) and (odd number of ways).

• From Steve D I realise that Marcus M wanted to help me understand the logic behind it, I get that I don't really need to know how many coins I am using, all I need to know is that the total number of the solution is odd+even (obviously), hence as both Marcus M and Steve D suggest, it seems that $$odd(x)= \frac{all(x)−alternating(x)}{2}$$ – AMeoni Sep 21 '17 at 22:51

Here's a hint for a generating function solution: let $a_{m,n}$ be the number of ways to make change for $n$ cents with $m$ coins.

Find the generating function $$F(x,y) = \sum_{m,n} a_{m,n} y^m x^n.$$

Try to manipulate this generating function to get the generating function for the number of ways to make change with an odd number of coins. Hover below for the solution:

Notice that $$\frac{F(x,y) - F(x,-y)}{2} = \sum_{m,n} a_{2m +1,n} y^{2m+1}x^n.$$ This would imply $\frac{F(x,1) - F(x,-1)}{2}$ is the generating function for the number of ways to make change with an odd number of coins.

Hint: Since $100$ is an even number, we must use an even number of odd summands. Therefore, to use an odd number of coins, we must use an odd number of dimes.