Sums payable by exactly n banknotes.

[Max Alekseyev]

Ops. I have counted the sums with multiplicities.
The number of *different* sums is not given by a substitution of x=1
but rather by counting non-zero coefficients.

Regards,
Max

On Feb 16, 2008 8:50 AM, Max Alekseyev <maxale at gmail.com> wrote:
> 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
>