A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

1, 8, 38, 178, 844, 4012, 19072, 90658, 430938, 2048450, 9737260, 46285868, 220018976, 1045856010, 4971456754, 23631725866, 112332963420, 533972624844, 2538228811648, 12065422836242, 57352760145834, 272625264866098, 1295919060481740, 6160126839867820

Offset: 1

Author

Toby Gottfried, Mar 09 2013

Keywords

• nonn
• walk

Examples

			For n=2, and moves U(p), D(own), R(ight), L(eft), the a(2)=8 walks are {DDD, DRDDL, DRDLD, DDRDL, RDDDL, RDDLD, RDLDD, RDLDRDL} with only the last touching all 8 squares of the grid.
Illustration of the 8 walks of a(2):
    .__      __      __        .       .        .       .     __
     __|    .  |    .  |    |__     |__      |  .    |  .     __|
    |  .     __|    .  |     __|     . |     |__     |  .    |__
    |  .    |  .     __|    |  .     __|      __|    |  .     __|
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100

Crossrefs

Row 4 of A271465.

Cf. A181688 (maximal walks with same conditions).

Cf. A005409 (grids with 3 rows), A006189 (grids with 3 columns).

Cf. A216211 (grids with 4 columns).

Formula

Empirical recurrence: a(1,...,5) = (1, 8, 38, 178, 844), a(n) = 7*a(n-1) - 12*a(n-2) + 7*a(n-3) - 3*a(n-4) - 2*a(n-5). - Giovanni Resta, Mar 13 2013

Empirical g.f.: x*(1+x-6*x^2+x^3+x^4)/(1-7*x+12*x^2-7*x^3+3*x^4+2*x^5). - Bruno Berselli, Mar 13 2013

Extensions

Missing a(7) and a(13)-a(14) from Giovanni Resta, Mar 13 2013

a(15)-a(24) from Andrew Howroyd, Apr 08 2016