%I M3474
%S 1,4,14,38,76,136,218,330,472,652,870,1134,1444,1808,2226,2706,3248,
%T 3860,4542,5302,6140,7064,8074,9178,10376,11676,13078,14590,16212,
%U 17952,19810,21794,23904,26148,28526,31046,33708,36520,39482,42602
%N Maximal length of rook tour on an n X n board.
%D M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 76.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%F From _R. J. Mathar_, Mar 22 2009: (Start)
%F The sequence is a hybrid of two sequences at the even and odd indices with linear recurrences individually, therefore a linear recurrence in total.
%F For even n the Gardner reference gives the formula a(n)=n(2n^25)/3+2, which is
%F 4,38,136,330,652,1134,1808,2706,3860,5302, n=2,4,6,8,...
%F with recurrence a(n)= 4 a(n1) 6 a(n2) +4 a(n3)  a(n4) and therefore with g.f. 2*(211*x4*x^2+x^3)/(x1)^4 (offset 0) (see A152110).
%F For n odd the Gardner reference gives a(n)= n(2n^25)/3+1, which is
%F 0,14,76,218,472,870,1444,2226,3248,4542,6140,8074,10376,13078, n=1,3,5,7,...
%F with the same recurrence and with g.f. 2*x*(710*x+x^2)/(x1)^4 (offset 0).
%F Since the first zero does not match the sequence and should be 1, we add 1 to the g.f.:
%F 1,14,76,218,472,870,1444,2226,3248,4542,6140,8074,10376,13078,... (see A152100),
%F g.f.: 12*x*(710*x+x^2)/(x1)^4.
%F We "aerate" both sequences by insertion of zeros at each second position,
%F which implies x>x^2 in the generating functions,
%F 4,0,38,0,136,0,330,0,652,0,1134,0,1808,0,2706,0,3860,0,5302
%F g.f. 2*(211*x^24*x^4+x^6)/(x^21)^4 (offset 0).
%F 1,0,14,0,76,0,218,0,472,0,870,0,1444,0,2226,0,3248,0,4542,0,6140,...
%F g.f. 12*x^2*(710*x^2+x^4)/(x^21)^4.
%F The first of these is multiplied by x to shift it right by one place:
%F 0,4,0,38,0,136,0,330,0,652,0,1134,0,1808,0,2706,0,3860,0,5302
%F g.f. 2*x*(211*x^24*x^4+x^6)/(x^21)^4.
%F The sum of these two is
%F 12*x^2*(710*x^2+x^4)/(x^21)^4 2*x*(211*x^24*x^4+x^6)/(x^21)^4 =
%F (x^55x^4+6x^3+4x^2+x+1)/((x1)^4/(x+1)).
%F This is exactly the Plouffe g.f. if the offset were 0.
%F In summary: a(n)= 3 a(n1) 2 a(n2) 2 a(n3) +3 a(n4)  a(n5), n > 6.
%F a(2n)= 2+2*n*(8n^25)/3, n>=1. a(2n+1)= 2n(1+8n^2+12n)/3, n>=1.
%F G.f.: x*(x^55x^4+6x^3+4x^2+x+1)/((x1)^4/(x+1)). (End)
%p A006071:=(1+z+4*z**2+6*z**35*z**4+z**5)/(z+1)/(z1)**4; # conjectured (correctly) by _Simon Plouffe_ in his 1992 dissertation
%Y Cf. A152100, A152110, A152132A152135.
%K nonn,walk
%O 1,2
%A _N. J. A. Sloane_
%E Edited (with more terms) by _R. J. Mathar_, Mar 22 2009
