login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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

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

Sequence in context: A225429 A123518 A197338 * A229366 A007786 A026662

Adjacent sequences:  A214928 A214929 A214930 * A214932 A214933 A214934

KEYWORD

nonn,walk

AUTHOR

Toby Gottfried, Mar 09 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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 09:55 EST 2019. Contains 329261 sequences. (Running on oeis4.)