A006071 Maximal length of rook tour on an n X n board.

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

Author

N. J. A. Sloane

Keywords

• nonn
• walk

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

• 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).

Crossrefs

Cf. A152100, A152110, A152132-A152135.

Programs

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

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)

Extensions

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