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, 2952740864, 5905498112, 11811061760, 23622156288

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

Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height., arXiv:2407.18205 [math.CO], 2024.

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 *)

Prog

(PARI) a(n)=if(n>1, ([0, 1, 0; 0, 0, 1; -4, 2, 2]^(n-2)*[3; 8; 17])[1, 1], 1) \\ Charles R Greathouse IV, May 13 2026

Crossrefs

Row 3 of A378938.

Cf. A046995.

Sequence in context: A295061 A247374 A336512 * A380124 A058811 A101822

Adjacent sequences: A046991 A046992 A046993 * A046995 A046996 A046997

Keyword

nonn,walk,easy

Author

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

Extensions

More terms and formula from Hugo van der Sanden

Status

approved