|
|
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.
|
|
5
|
|
|
1, 8, 38, 178, 844, 4012, 19072, 90658, 430938, 2048450, 9737260, 46285868, 220018976, 1045856010, 4971456754, 23631725866, 112332963420, 533972624844, 2538228811648, 12065422836242, 57352760145834, 272625264866098, 1295919060481740, 6160126839867820
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
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
|
|
EXAMPLE
|
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):
.__ __ __ . . . . __
__| . | . | |__ |__ | . | . __|
| . __| . | __| . | |__ | . |__
| . | . __| | . __| __| | . __|
|
|
CROSSREFS
|
Cf. A181688 (maximal walks with same conditions).
Cf. A216211 (grids with 4 columns).
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|