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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.