login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=1..40.

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

Comments 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: A192974 A187428 A036368 * A086954 A111583 A124615

Adjacent sequences:  A006068 A006069 A006070 * A006072 A006073 A006074

KEYWORD

nonn,walk

AUTHOR

N. J. A. Sloane.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 02:10 EDT 2017. Contains 283984 sequences.