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

Author

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

Keywords

• nonn
• walk

Examples

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

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

Crossrefs

Row 3 of A378938.

Cf. A046995.

Programs

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

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

Extensions

More terms and formula from Hugo van der Sanden