A046994 Number of Greek-key tours on a 3 X n board; i.e., self-avoiding walks on a 3 X n grid starting in the top left corner.

1, 3, 8, 17, 38, 78, 164, 332, 680, 1368, 2768, 5552, 11168, 22368, 44864, 89792, 179840, 359808, 720128, 1440512, 2882048, 5764608, 11531264, 23063552, 46131200, 92264448, 184537088, 369078272, 738172928, 1476354048

Offset

1,2

References

Posting by Thomas Womack (mert0236(AT)sable.ox.ac.uk) to sci.math newsgroup, Apr 21 1999.

Links

Robert Israel, Table of n, a(n) for n = 1..2985

Index entries for linear recurrences with constant coefficients, signature (2, 2, -4).

Formula

a(1) = 1; a(2m) = Sum_{i = 2...2m-1} a(i) + 3*2^(m-1); a(2m+1) = Sum_{i = 2...2m} a(i) + 5*2^(m-1).

a(n) = 11*2^(n-3) - (4 + (-1)^n)*(2^((1/4)*(2n - 7 - (-1)^n))), n >= 2. - Nathaniel Johnston, Feb 03 2006

a(n) = 2*a(n-1)+2*a(n-2)-4*a(n-3) for n>4. G.f.: x*(1+x-x^3)/(1-2*x-2*x^2+4*x^3). - Colin Barker, Jul 19 2012

Example

On a 3 X 3 board labeled 123 456 789 (reading across rows), 125478963 is such a tour.

Maple

A046994:=n->`if`(n=1, 1, 11*2^(n-3)-(4+(-1)^n)*(2^((1/4)*(2*n-7-(-1)^n)))): seq(A046994(n), n=1..30); # Wesley Ivan Hurt, Sep 14 2014

Mathematica

CoefficientList[Series[(1 + x - x^3)/(1 - 2 x - 2 x^2 + 4 x^3), {x, 0, 30}], x] (* Wesley Ivan Hurt, Sep 14 2014 *)

Crossrefs

Cf. A046995.

Sequence in context: A295061 A247374 A336512 * A058811 A101822 A354538

Adjacent sequences: A046991 A046992 A046993 * A046995 A046996 A046997

Keyword

nonn,walk

Author

Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr)

Extensions

More terms and formula from Hugo van der Sanden

Status

approved