A006071 Maximal length of rook tour on an n X n board. (Formerly M3474)

1, 4, 14, 38, 76, 136, 218, 330, 472, 652, 870, 1134, 1444, 1808, 2226, 2706, 3248, 3860, 4542, 5302, 6140, 7064, 8074, 9178, 10376, 11676, 13078, 14590, 16212, 17952, 19810, 21794, 23904, 26148, 28526, 31046, 33708, 36520, 39482, 42602

Offset

1,2

References

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 76.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..40.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Index entries for linear recurrences with constant coefficients, signature (3, -2, -2, 3, -1).

Formula

From R. J. Mathar, Mar 22 2009: (Start)

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 even n the Gardner reference 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) (see A152110).

For n odd the Gardner reference 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,... (see A152100),

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. if the offset were 0.

In summary: a(n)= 3 a(n-1) -2 a(n-2) -2 a(n-3) +3 a(n-4) - a(n-5), n > 6.

a(2n)= 2+2*n*(8n^2-5)/3, n>=1. a(2n+1)= 2n(1+8n^2+12n)/3, n>=1.

G.f.: x*(x^5-5x^4+6x^3+4x^2+x+1)/((x-1)^4/(x+1)). (End)

Maple

A006071:=(1+z+4*z**2+6*z**3-5*z**4+z**5)/(z+1)/(z-1)**4; # conjectured (correctly) by Simon Plouffe in his 1992 dissertation

Crossrefs

Cf. A152100, A152110, A152132-A152135.

Sequence in context: A187428 A316878 A036368 * A086954 A111583 A124615

Adjacent sequences: A006068 A006069 A006070 * A006072 A006073 A006074

Keyword

nonn,walk

Author

N. J. A. Sloane

Extensions

Edited (with more terms) by R. J. Mathar, Mar 22 2009

Status

approved