A037245 Number of unrooted self-avoiding walks of n steps on square lattice.

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

Offset: 1

Author

Brian Hayes

Keywords

• nonn
• walk
• hard
• nice

Comments

Or, number of 2-sided 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) 314-319.
• Ed Pegg, Jr., Illustrations of polyforms
• Eric Weisstein's World of Mathematics, Polyedge

Crossrefs

Asymptotically approaches (1/16) * A001411.

Cf. A266549 (closed self-avoiding walks).

Cf. A323188, A323189 (program).

Formula

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

Extensions

a(25)-a(27) from Luca Petrone, Dec 20 2015

More terms using formula by Bert Dobbelaere, Jan 07 2019