A302336 -id:A302336 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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

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

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.

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

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

A302337 Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

Original entry on oeis.org

1, 4, 4, 5, 9, 12, 26, 52, 76, 32, 6, 16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226, 25, 40, 110, 332, 1070, 3504, 11144, 32172, 77874, 146680, 217470, 255156, 233786, 158652, 69544, 13732, 1072, 36, 60, 173, 556, 1942, 7092, 26424, 97624, 346428, 1136164, 3313812, 8342388, 18064642, 33777148, 54661008, 76165128, 89790912, 86547168, 64626638, 34785284, 12527632, 2677024, 255088

Offset: 2

Eric W. Weisstein, Apr 05 2018

			Triangle begins:
   1;
   4,  4,  5;
   9, 12, 26,  52,  76,   32,    6;
  16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226;
  ...
So for example, the 3 X 3 grid graph has 4 4-cycles, 4 6-cycles, and 5 8-cycles.

Seiichi Manyama, Rows n = 2..9, flattened
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A003763 (number of Hamiltonian cycles in 2n X 2n grid graph).
Cf. A140517 (number of cycles).
Cf. A301648 (number of longest cycles).

Flatten[Table[Tally[Length /@ FindCycle[GridGraph[{n, n}], Infinity, All]][[All, 2]], {n, 6}]] (* Eric W. Weisstein, Mar 26 2021 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A302337(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return [cycles.len(2 * k).len() for k in range(2, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A302337(n)])  # Seiichi Manyama, Mar 29 2020

Row sums equal A140517(n).
Length of row n equals A047838(n) = floor(n^2/2) - 1.
T(n,2) =    1 -   2*n +     n^2 = (n-1)^2.
T(n,3) =    4 -   6*n +   2*n^2 = A046092(n-2).
T(n,4) =   26 -  28*n +   7*n^2 for n > 2.
T(n,5) =  164 - 140*n +  28*n^2 for n > 3.
T(n,6) = 1046 - 740*n + 124*n^2 for n > 4.
T(n,k) = A302335(k) - A302336(k)*n + A002931(k)*n^2 for n > k-2.
T(n,floor(n^2/2)) = A301648(n).
T(n,n^2/2) = A003763(n) for n even.

A302335 Constant coefficient of the quadratic polynomials giving the numbers of 2k-cycles in the n X n grid graph for n >= k-1.

Original entry on oeis.org

0, 1, 4, 26, 164, 1046, 6672, 42790, 275888, 1787624, 11634704

Offset: 1

Eric W. Weisstein, Apr 05 2018

a(n) is the sum of the areas of minimal bounding rectangles of (fixed, self-avoiding) 2n-cycles in a grid. - Andrey Zabolotskiy, Feb 09 2022

			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 constant coefficients give a(n), so the first few are 0, 1, 4, 26, 164, .... - _Eric W. Weisstein_, Apr 05 2018

Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A302336 (linear coefficients).

Cf. A002931 (quadratic coefficients).

A006772 Sum of spans of 2n-step polygons on square lattice.

Original entry on oeis.org

0, 1, 3, 14, 70, 370, 2028, 11452, 66172, 389416, 2326202, 14070268, 86010680, 530576780, 3298906810, 20653559846, 130099026600, 823979294284, 5244162058026, 33523117491920, 215150177410088, 1385839069134800, 8956173544332434, 58056703069399056, 377396656568011618, 2459614847765495754, 16068572108927106202

Offset: 1

N. J. A. Sloane

nonn

			From _Andrey Zabolotskiy_, Nov 09 2018: (Start)
There are no 2-step polygons (conventionally).
For n=2, the only 4-step polygon is a 1 X 1 square having span 1, so a(2)=1.
For n=3, the only 6-step polygon is a 2 X 1 domino which can be rotated 2 ways having spans 2 and 1, so a(3) = 2+1 = 3.
For n=4, there are the following 8-step polygons:
a 3 X 1 stick which can be rotated 2 ways having spans 3 and 1;
an L-tromino which can be rotated 4 ways, all having span 2;
a 2 X 2 square, having span 2.
So a(4) = 3 + 1 + 4*2 + 2 = 14.
For n=5, there are the following 10-step polygons:
a 4 X 1 stick which can be rotated 2 ways having spans 4 and 1;
an L-tetromino which can be rotated 2 ways with span 2 and 2 more ways with span 3, plus reflections;
a T-tetromino which can be rotated 2 ways with span 2 and 2 more ways with span 3;
an S-tetromino which can be rotated 2 ways having spans 3 and 2, plus reflections;
a 3 X 2 rectangle which can be rotated 2 ways having spans 3 and 2;
a 3 X 2 rectangle without one of its angular squares having same counts as L-tetromino.
So a(5) = 4 + 1 + 2 * 2*2*(2+3) + 2*(2+3) + 2*(3+2) + 3 + 2 = 70.
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A. J. Guttmann and I. G. Enting, The size and number of rings on the square lattice, J. Phys. A 21 (1988), L165-L172.

Cf. A002931, A006773, A302336, A302337, A232103.

Name corrected, more terms from Andrey Zabolotskiy, Nov 09 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A302337 Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A302335 Constant coefficient of the quadratic polynomials giving the numbers of 2k-cycles in the n X n grid graph for n >= k-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A006772 Sum of spans of 2n-step polygons on square lattice.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions