[seqfan] Re: Currency puzzle

[David Wilson]

I screwed up the ellipsis, it should have read:

1, 2, 2, 3, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64...

so the sequence continues ad infinitum in the obvious way.
So I blew this puzzle.

Robert Wilson's GF for ways of making change was incorrect because it counts zero or more instances of any coin/bill.
Robert Pratt's GF was also incorrect, the term for a duplicated denomination d should be (1 + x^d)^2, not (1 + 2x^d).
William Kieth's GF is correct:

GF = (1 + x) (1 + x^2)^2 (1 + x^3) (1 + x^4)^2 (1 + x^8)^2 ...

(amended to go on to forever per my original idea).

But we have

(1 + x^2) (1 + x^4) (1 + x^8) ... = 1 / (1 - x^2), so

GF = (1 + x) (1 + x^3) / (1 - x^2)^2

Dividing 1 + x twice out of top and bottom

GF = (1 - x + x^2) / (1 - x)^2
= 1 + x / (1 - x^2)

In the latter form, it is easier to recover the sequence of change counts:

1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

So we can change 0 blatz in 1 way (as always), and n blatz in n ways for n > 0.
I believe this is the unique currency in which each value n > 0 can be changed n ways in distinct denominations. 

For example, letting b stand for bill, and c for coin, here are the 10 ways to make change for 10 blatz:

b8 + b2
b8 + c2
c8 + b2
c8 + c2
b4 + c4 + b2
b4 + c4 + c2
b4 + c3 + b2 + c1
b4 + c3 + c2 + c1
c4 + c3 + b2 + c1
c4 + c3 + c2 + c1