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

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

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