|
%I #19 Apr 10 2016 22:54:26
%S 1,1,4,8,23,55,144,360,921,2329,5924,15024,38159,96847,245888,624176,
%T 1584593,4022609,10211940,25924088,65811431,167069767,424126160,
%U 1076693080,2733310377,6938824361,17615009476,44717740000,113521160607,288186606623
%N Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2, 2, -2, 1).
%F G.f.: (x^2-x)/(x^4-2*x^3+2*x^2+2*x-1).
%F a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4), n > 4.
%e Illustration of a(1)=a(2)=1:
%e . .__.
%e | .__|
%e | |__
%e | .__|
%e Illustration of a(3)=4:
%e .__.__. . .__. . .__. .__.__.
%e .__.__| |__| | | | | .__. |
%e |__.__. .__. | |__| | | | |
%e .__.__| | |__| .__.__| | |__|
%t LinearRecurrence[{2, 2, -2, 1}, {1, 1, 4, 8}, 30] (* _T. D. Noe_, Nov 06 2013 *)
%Y Row 4 of A271592.
%Y Cf. A000532, A014524, A014523, A181689, A003695, A006864.
%K nonn,walk
%O 1,3
%A _Sean A. Irvine_, Nov 17 2010
%E G.f. formula reverted to the original (correct) value by _Stefan Bühler_, Nov 06 2013
|
