A002931 Number of self-avoiding polygons of length 2n on square lattice (not allowing rotations).

0, 1, 2, 7, 28, 124, 588, 2938, 15268, 81826, 449572, 2521270, 14385376, 83290424, 488384528, 2895432660, 17332874364, 104653427012, 636737003384, 3900770002646, 24045500114388, 149059814328236, 928782423033008, 5814401613289290, 36556766640745936

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• walk
• nice

Comments

Translations are allowed, but not rotations or reflections.

a(n) is also the coefficient of n^2 in the sequence of quadratic polynomials giving the numbers of 2k-cycles in the n X n grid graph for n >= k-1 (see the example). - Eric W. Weisstein, Apr 05 2018

Examples

			At length 8 there are 7 polygons, consisting of the 2, 1, 4 resp. rotations of:
._. .___. .___.
| | | . | | ._|
| | |___| |_|
|_|
Let p(k,n) be the number of 2k-cycles in the n X n grid graph for n >= k-1.  p(k,n) are quadratic polynomials in n, with the first few given by:
p(1,n) = 0,
p(2,n) = 1 - 2*n + n^2,
p(3,n) = 4 - 6*n + 2*n^2,
p(4,n) = 26 - 28*n + 7*n^2,
p(5,n) = 164 - 140*n + 28*n^2,
p(6,n) = 1046 - 740*n + 124*n^2,
p(7,n) = 6672 - 4056*n + 588*n^2,
p(8,n) = 42790 - 22904*n + 2938*n^2,
p(9,n) = 275888 - 132344*n + 15268*n^2,
...
The quadratic coefficients give a(n), so the first few are 0, 1, 2, 7, 28, 124, .... - _Eric W. Weisstein_, Apr 05 2018
		

References

• N. Clisby and I. Jensen: A new transfer-matrix algorithm for exact enumerations: self-avoiding polygons on the square lattice, J. Phys. A: Math. Theor. 45 (2012). Also arXiv:1111.5877, 2011. [Extends sequence to a(65)]
• I. G. Enting: Generating functions for enumerating self-avoiding rings on the square lattice, J. Phys. A: Math. Gen. 13 (1980). pp. 3713-3722. See Table 2.
• A. J. Guttmann, Asymptotic analysis of power-series expansions, pp. 1-234 of C. Domb and J. L. Lebowitz, editors, Phase Transitions and Critical Phenomena. Vol. 13, Academic Press, NY, 1989.
• B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 461.
• I. Jensen: A parallel algorithm for the enumeration of self-avoiding polygons on the square lattice, J. Phys. A: Math. Gen. 36 (2003). [Extends sequence to a(55)]
• I. Jensen and A. J. Guttmann: Self-avoiding polygons on the square lattice, J. Phys. A: Math. Gen. 32 (1999). Also arXiv:cond-mat/9905291. [Extends sequence to a(45)]
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..65 [Formed from tables in several references, the most recent being Clisby-Jensen, 2011/2012]
• Jérôme Bastien, Construction and enumeration of circuits capable of guiding a miniature vehicle, arXiv:1603.08775 [math.CO], 2016. Cites this sequence.
• Nathan Clisby, Lattice enumeration, Slides of talk at Enting fest, CSIRO, Aspendale, 2015; Lattice enumeration [Local copy].
• M. E. Fisher and D. S. Gaunt, Ising model and self-avoiding walks on hypercubical lattices and high density expansions, Phys. Rev. 133 (1964) A224-A239.
• M. E. Fisher and M. F. Sykes, Excluded-volume problem and the Ising model of ferromagnetism, Phys. Rev. 114 (1959), 45-58.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 364.
• A. J. Guttmann, Asymptotic analysis of power-series expansions, pp. 1-13, 56-57, 142-143, 150-151 from of C. Domb and J. L. Lebowitz, editors, Phase Transitions and Critical Phenomena. Vol. 13, Academic Press, NY, 1989. (Annotated scanned copy)
• A. J. Guttmann and I. G. Enting, The size and number of rings on the square lattice, J. Phys. A 21 (1988), L165-L172.
• Brian Hayes, How to avoid yourself, American Scientist 86 (1998) 314-319.
• B. J. Hiley and M. F. Sykes, Probability of initial ring closure in the restricted random-walk model of a macromolecule, J. Chem. Phys., 34 (1961), 1531-1537.
• I. Jensen, A parallel algorithm for the enumeration of self-avoiding polygons on the square lattice, Journal of Physics A, Vol. 36 (2003), pp. 5731-5745.
• I. Jensen, More terms
• G. S. Rushbrooke and J. Eve, On Noncrossing Lattice Polygons, Journal of Chemical Physics, 31 (1959), 1333-1334.
• S. G. Whittington and J. P. Valleau, Figure eights on the square lattice: enumeration and Monte Carlo estimation, J. Phys. A 3 (1970), 21-27. See Table 2.

Crossrefs

Cf. A056634, A036638, A036639. Equals A010566(n)/(4n).

Cf. A057730.

Cf. A302335 (constant coefficients in p(k,n)).

Cf. A302336 (linear coefficients in p(k,n)).

Extensions

Updated by N. J. A. Sloane, Mar 18 2021