The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A006071 Maximal length of rook tour on an n X n board. (Formerly M3474) 7
 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 (list; graph; refs; listen; history; text; internal format)
 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 Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992. Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992. 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 EXTENSIONS Edited (with more terms) by R. J. Mathar, Mar 22 2009 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 30 19:49 EDT 2020. Contains 333127 sequences. (Running on oeis4.)