[seqfan] Re: Typo in formula-section of A001541 ?

[Richard Mathar]

hh> Hans Havermann pxp at rogers.com
hh> Sat Mar 21 20:07:29 CET 2009
hh> 
hh> > There is a group of sequences with conjectured g.f.'s still to be put
hh> > on the "good" or "bad" side...
hh> ...
hh> > A006071: this requires access to a book by Gardner
hh> 
hh> I don't know that it will help, but for what it's worth, I'll put  
hh> Gardner's page-and-a-half here:
hh> 
hh> http://chesswanks.com/pot/KD(75-76).jpg

This surely helps, and with a glance we realize that the sequence is
a hybrid of two sequences at the even and odd indices with linear recurrences
individually, therefore a linear recurrence in total; for 99.999 percent
of these cases the conjectured generating functions are correct. In detail:


For even n the manuscript gives the formula a(n)=n(2n^2-5)/3+2, which is

4,38,136,330,652,1134,1808,2706,3860,5302, n=2,4,6,8,...
with recurrence a(n)= 4 a(n-1) -6 a(n-2) +4 a(n-3) - a(n-4) and therefore
with g.f.  -2*(-2-11*x-4*x^2+x^3)/(x-1)^4 (offset 0).

For n odd the manuscript gives a(n)= n(2n^2-5)/3+1, which is
0,14,76,218,472,870,1444,2226,3248,4542,6140,8074,10376,13078, n=1,3,5,7,...
with the same recurrence and with g.f. -2*x*(-7-10*x+x^2)/(x-1)^4 (offset 0).
Since the first zero does not match the sequence and should be 1, we add
1 to the g.f.:
1,14,76,218,472,870,1444,2226,3248,4542,6140,8074,10376,13078,..
g.f.: 1-2*x*(-7-10*x+x^2)/(x-1)^4 .

We "aerate" both sequences by insertion of zeros at each second position,
which implies x->x^2 in the generating functions,

4,0,38,0,136,0,330,0,652,0,1134,0,1808,0,2706,0,3860,0,5302
g.f.  -2*(-2-11*x^2-4*x^4+x^6)/(x^2-1)^4 (offset 0).

1,0,14,0,76,0,218,0,472,0,870,0,1444,0,2226,0,3248,0,4542,0,6140,...
g.f. 1-2*x^2*(-7-10*x^2+x^4)/(x^2-1)^4 .

The first of these is multiplied by x to shift it right by one place:
0,4,0,38,0,136,0,330,0,652,0,1134,0,1808,0,2706,0,3860,0,5302
g.f.  -2*x*(-2-11*x^2-4*x^4+x^6)/(x^2-1)^4 .

The sum of these two is

1-2*x^2*(-7-10*x^2+x^4)/(x^2-1)^4 -2*x*(-2-11*x^2-4*x^4+x^6)/(x^2-1)^4
=
(x^5-5x^4+6x^3+4x^2+x+1)/((x-1)^4/(x+1)).

This is exactly the Plouffe g.f. in
http://research.att.com/~njas/sequences/A006071
assuming offset 0. In summary, we can delete the annotation "Conjectured" in
A006071 and get--with another multiplication by x to address the offset 1--:

%I A006071 M3474
%S A006071 1,4,14,38,76,136,218,330,472,652,870,1134,1444,1808,2226,2706,3248,
%T A006071 3860,4542,5302,6140,7064,8074,9178,10376,11676,13078,14590,16212,
%U A006071 17952,19810,21794,23904,26148,28526,31046,33708,36520,39482,42602
%F A006071 a(n)= 3 a(n-1) -2 a(n-2) -2 a(n-3) +3 a(n-4) - a(n-5), n> 6.
%F A006071 a(2n)= 2+2*n*(8n^2-5)/3, n>=1. a(2n+1)= 2n(1+8n^2+12n)/3, n>=1.
%F A006071 G.f.: x*(x^5-5x^4+6x^3+4x^2+x+1)/((x-1)^4/(x+1)) .


Looking at the other, more general, formula for the n by m boards,
n(3m^2+n^2-10)/6+C with C a function of the parities of m, n , and [n/2]
the other diagonals of figure 44 of the book can be treated in the same way:

m=n+1 (note the type for n=3,m=4 in table 44 which does not match the formula):
2,8,24,54,104,174,270,396,558,756,996,1282,1620,2010... (starts at n=1)
g.f.: -2*x*(-1-x-2*x^3-2*x^4-3*x^2+x^5)/(1+x)/(x^2+1)/(x-1)^4 .

m=n+2:
4,16,38,78,136,220,330,474,652,872,1134,1446,1808,2228,2706,3250,3860,4544,5302,6142,7064,8076,9178,10378 (starts at n=1):
g.f.: -2*x*(-2-2*x+x^2-2*x^3+x^4)/(1+x)/(x-1)^4

m=n+3 (note the typo for n=3,m=6 in table 44 which does not match the formula):
8,24,54,102,174,270,396,556,756,996,1282,1618,2010,2458,2968,3544,4192,4912:
g.f.: -2*x*(-4-3*x^2-2*x^3+x^4)/(1+x)/(x^2+1)/(x-1)^4 .

m=n+4:
12,36,74,134,216,328,470,650,868,1132,1442,1806,2224,2704,3246,3858,4540,5300..
g.f.: -2*x*(-6+5*x^2-4*x^3+x^4)/(1+x)/(x-1)^4

In Maplish:
# Figure 43 of the book
C := proc(n,m)
        if type(m,even) and type(n,even) then
                2 ;
        elif type(m,odd) and type(n,odd) then
                1 ;
        elif type(m,even) and type(n,odd) and type(floor(n/2),even) then
                3/2 ;
        elif type(m,even) and type(n,odd) and type(floor(n/2),odd) then
                1/2 ;
        elif type(m,odd) and type(n,even) and type(floor(n/2),even) then
                0 ;
        elif type(m,odd) and type(n,even) and type(floor(n/2),odd) then
                1 ;
        fi;
end:
# formula for n by m boards of the book
T := proc(n,m)
        n*(3*m^2+n^2-10)/6+C(n,m) ;

end:
for n from 1 to 24 do
        m := n+3 ; # third diagonal here, for example
        printf("%d,",T(n,m)) ;
od: