A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

1, 1, 4, 8, 23, 55, 144, 360, 921, 2329, 5924, 15024, 38159, 96847, 245888, 624176, 1584593, 4022609, 10211940, 25924088, 65811431, 167069767, 424126160, 1076693080, 2733310377, 6938824361, 17615009476, 44717740000, 113521160607, 288186606623

Offset

1,3

Links

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

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

Formula

G.f.: (x^2-x)/(x^4-2*x^3+2*x^2+2*x-1).

a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4), n > 4.

Example

Illustration of a(1)=a(2)=1:
   .    .__.
   |    .__|
   |    |__
   |    .__|
Illustration of a(3)=4:
   .__.__.    .  .__.    .  .__.    .__.__.
   .__.__|    |__|  |    |  |  |    .__.  |
   |__.__.    .__.  |    |__|  |    |  |  |
   .__.__|    |  |__|    .__.__|    |  |__|

Mathematica

LinearRecurrence[{2, 2, -2, 1}, {1, 1, 4, 8}, 30] (* T. D. Noe, Nov 06 2013 *)

Prog

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

Crossrefs

Row 4 of A271592.

Cf. A000532, A014524, A014523, A181689, A003695, A006864.

Sequence in context: A306483 A274521 A026596 * A243557 A316687 A083504

Adjacent sequences: A181685 A181686 A181687 * A181689 A181690 A181691

Keyword

nonn,walk,easy

Author

Sean A. Irvine, Nov 17 2010

Extensions

G.f. formula reverted to the original (correct) value by Stefan Bühler, Nov 06 2013

Status

approved