[seqfan] Re: Currency puzzle

[David Wilson]

In change-making problems, the default assumption is order doesn't matter.
Having a bill and coin of the same value is the same as having a coin and bill.

Suppose there is an N blatz coin and a N blatz bill.
The problem states that change must be made with distinct denominations (counting coin and bill as distinct).

If you don't care about order, your change could contain one of the 4 following possibilities:

No N-blatz bills or coins.
One N-blatz bill.
One N-blatz coin.
One N-blatz bill and one N-blatz coin.

There is 1 possibility of value 0, 2 possibilities of value N, and 1 possibility of value 2N.
This leads to the term  1x^0 + 2x^N + 1x^(2N) = (1 + x^N)^2 in the GF.

If you do care about order, your change could contain one of the 5 following possibilities:

No N-blatz bills or coins.
One N-blatz bill.
One N-blatz coin.
One N-blatz bill and one N-blatz coin.
One N-blatz coin and one N-blatz bill.

This leads to the term 1 + 2x^N  + 2x^(2N) in the GF.

The only way I can think that would lead to the term 1 + 2x^N in the GF would be if you forbid equal-valued bill and coin in your change. Then your possibilities would be

No N-blatz bills or coins.
One N-blatz bill.
One N-blatz coin.

But I think the problem statement made it clear that bill and coin were considered distinct denominations, so that you could both in your change.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Joerg
> Arndt
> Sent: Sunday, September 27, 2015 4:12 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Currency puzzle
> 
> 
> About
> > G.F.: (1+x)(1+2x^2)(1+x^3)(1+2x^4)(1+2x^8)(1+2x^16)(1+2x^32)(1+2x^64)
> versus
>   G.F.:
> (1+x)(1+x^2)^2(1+x^3)(1+x^4)^2(1+x^8)^2(1+x^16)^2(1+x^32)^2(1+x^64)^
> 2
> 
> The first accounts for ordered sorts, the second for un-ordered which is
> more common with partitions.  "Ordered" is more common with
> compositions ("ordered partitions").
> 
> Regards,  jj
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/