Sums payable by exactly n banknotes.

[Max Alekseyev]

On Feb 16, 2008 7:59 AM, zak seidov <zakseidov at yahoo.com> wrote:
> Dear Neil, seqfans,
>
> 1) can anyone check/extend these figures?
> 2) what about case n => inf?
> 3) is this worth submitting?
>
> thanks, zak
>
>
> %N A1 Number of sums payable by exactly n banknotes of
> nominals 1,5,10,20,50,100.

The sums s that are payable with exactly n banknotes appear as a term
x^s * y^n in the expansion of
g(x,y) = 1 / ( ( 1 - y*x) * ( 1 - y*x^5 ) * ( 1 - y*x^10 ) * ( 1 -
y*x^20 ) * ( 1 - y*x^50 ) * ( 1 - y*x^100 ) )

and o.g.f. for the number of different s (as a function of n) is simply
g(1,y) = 1 / ( ( 1 - y) * ( 1 - y ) * ( 1 - y ) * ( 1 - y ) * ( 1 - y
) * ( 1 - y ) ) = ( 1 - y )^(-6).

In particular, the coefficient of y^n in g(1,y) is
(-1)^n*binomial(-6,n) = binomial(n+5,n):

6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568,
11628, 15504, 20349, 26334, 33649, 42504, 53130

This is A000389 and it's somehow is different from yours:

> %S A1 6, 15, 52, 103, 174, 262, 360, 461, 561, 660.
>
> %e A1
> n=1: 6 payable sums are 1,5,10,20,50,100;
> n=2: 15 sums are 2,6,10,11,15,20,21,25,30,40,51,
> 55,60,70,100;

Take a look:

? G=taylor(1 / ( ( 1 - y*x) * ( 1 - y*x^5 ) * ( 1 - y*x^10 ) * ( 1 -
y*x^20 ) * ( 1 - y*x^50 ) * ( 1 - y*x^100 ) ), y); polcoeff(G,2,y)
%1 = x^200 + x^150 + x^120 + x^110 + x^105 + x^101 + x^100 + x^70 +
x^60 + x^55 + x^51 + x^40 + x^30 + x^25 + x^21 + x^20 + x^15 + x^11 +
x^10 + x^6 + x^2

You have missed 101, 105, 110, 120, 150, and 200.

> n=3: 52 sums are in A135137;
> n=4: 103 sums are:

These are also incorrect.

? polcoeff(G,3,y)
%2 = x^300 + x^250 + x^220 + x^210 + x^205 + x^201 + x^200 + x^170 +
x^160 + x^155 + x^151 + x^150 + x^140 + x^130 + x^125 + x^121 +
2*x^120 + x^115 + x^111 + 2*x^110 + x^106 + x^105 + x^102 + x^101 +
x^90 + x^80 + x^75 + x^71 + x^70 + x^65 + x^61 + 2*x^60 + x^56 + x^52
+ x^50 + x^45 + x^41 + x^40 + x^35 + x^31 + 2*x^30 + x^26 + x^25 +
x^22 + x^21 + x^20 + x^16 + x^15 + x^12 + x^11 + x^7 + x^3

? polcoeff(G,4,y)
%3 = x^400 + x^350 + x^320 + x^310 + x^305 + x^301 + x^300 + x^270 +
x^260 + x^255 + x^251 + x^250 + x^240 + x^230 + x^225 + x^221 +
2*x^220 + x^215 + x^211 + 2*x^210 + x^206 + x^205 + x^202 + x^201 +
x^200 + x^190 + x^180 + x^175 + x^171 + 2*x^170 + x^165 + x^161 +
3*x^160 + x^156 + x^155 + x^152 + x^151 + x^150 + x^145 + x^141 +
2*x^140 + x^135 + x^131 + 3*x^130 + x^126 + 2*x^125 + x^122 + 2*x^121
+ 2*x^120 + x^116 + 2*x^115 + x^112 + 2*x^111 + 2*x^110 + x^107 +
x^106 + x^103 + x^102 + x^100 + x^95 + x^91 + x^90 + x^85 + x^81 +
3*x^80 + x^76 + x^75 + x^72 + x^71 + 2*x^70 + x^66 + 2*x^65 + x^62 +
2*x^61 + x^60 + x^57 + x^55 + x^53 + x^51 + 2*x^50 + x^46 + x^45 +
x^42 + x^41 + 2*x^40 + x^36 + 2*x^35 + x^32 + 2*x^31 + x^30 + x^27 +
x^26 + x^25 + x^23 + x^22 + x^21 + x^20 + x^17 + x^16 + x^13 + x^12 +
x^8 + x^4

Regards,
Max