A152133 Maximal length of rook tour on an n X n+2 board.

4, 16, 38, 78, 136, 220, 330, 474, 652, 872, 1134, 1446, 1808, 2228, 2706, 3250, 3860, 4544, 5302, 6142, 7064, 8076, 9178, 10378, 11676, 13080, 14590, 16214, 17952, 19812, 21794, 23906, 26148, 28528, 31046, 33710, 36520, 39484, 42602, 45882

Offset: 1

Author

R. J. Mathar, Mar 22 2009

Keywords

• nonn
• easy

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Crossrefs

Cf. A006071, A152132, A152134, A152135.

Programs

Magma

I:=[4,16,38,78,136]; [n le 5 select I[n] else 3*Self(n-1)-2*Self(n-2)-2*Self(n-3)+3*Self(n-4)-Self(n-5): n in [1..40]]; // Vincenzo Librandi, Dec 11 2012

Mathematica

LinearRecurrence[{3,-2,-2,3,-1},{4,16,38,78,136},40] (* Harvey P. Dale, Dec 16 2011 *)

Formula

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

a(n) = 3*a(n-1) -2*a(n-2) -2*a(n-3) +3*a(n-4) -a(n-5).

a(n) = 2*n^3/3+2*n^2+n/3+3/2+(-1)^n/2. [R. J. Mathar, Oct 20 2009]