

A037245


Number of unrooted selfavoiding walks of n steps on square lattice.


16



1, 2, 4, 9, 22, 56, 147, 388, 1047, 2806, 7600, 20437, 55313, 148752, 401629, 1078746, 2905751, 7793632, 20949045, 56112530, 150561752, 402802376, 1079193821, 2884195424, 7717665979, 20607171273, 55082560423, 146961482787, 392462843329, 1046373230168, 2792115083878
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Or, number of 2sided polyedges with n cells.  Ed Pegg Jr, May 13 2009
A walk and its reflection (i.e., exchange start and end of walk, what Hayes calls a "retroreflection") are considered one and the same here.  Joerg Arndt, Jan 26 2018
With A001411 as main input and counting the symmetrical shapes separately, higher terms can be computed efficiently (see formula).  Bert Dobbelaere, Jan 07 2019


LINKS

Bert Dobbelaere, Table of n, a(n) for n = 1..60
Joerg Arndt, The a(6) = 56 walks of length 6, 2018 (pdf, 2 pages).
Brian Hayes, How to avoid yourself, American Scientist 86 (1998) 314319.
Ed Pegg, Jr., Illustrations of polyforms
Eric Weisstein's World of Mathematics, Polyedge


FORMULA

a(n) = (A001411(n) + A323188(n) + A323189(n) + 4) / 16.  Bert Dobbelaere, Jan 07 2019


CROSSREFS

Asymptotically approaches (1/16) * A001411.
Cf. A266549 (closed selfavoiding walks).
Cf. A323188, A323189 (program).
Sequence in context: A091561 A025265 A152225 * A244886 A143017 A307575
Adjacent sequences: A037242 A037243 A037244 * A037246 A037247 A037248


KEYWORD

nonn,walk,hard,nice


AUTHOR

Brian Hayes


EXTENSIONS

a(25)a(27) from Luca Petrone, Dec 20 2015
More terms using formula by Bert Dobbelaere, Jan 07 2019


STATUS

approved



