A006071 - OEIS

%I M3474 #26 Jul 14 2023 14:34:08

%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; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3, -2, -2, 3, -1).

%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^2-5)/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(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).

%F For n odd the Gardner reference gives a(n)= n(2n^2-5)/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*(-7-10*x+x^2)/(x-1)^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.: 1-2*x*(-7-10*x+x^2)/(x-1)^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*(-2-11*x^2-4*x^4+x^6)/(x^2-1)^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. 1-2*x^2*(-7-10*x^2+x^4)/(x^2-1)^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*(-2-11*x^2-4*x^4+x^6)/(x^2-1)^4.

%F The sum of these two is

%F 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 =

%F (x^5-5x^4+6x^3+4x^2+x+1)/((x-1)^4/(x+1)).

%F This is exactly the Plouffe g.f. if the offset were 0.

%F 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.

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

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

%p 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

%Y Cf. A152100, A152110, A152132-A152135.

%K nonn,walk

%O 1,2

%A _N. J. A. Sloane_

%E Edited (with more terms) by _R. J. Mathar_, Mar 22 2009