A302335 -id:A302335 - 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.

A302336 Linear coefficient (in absolute value) 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, 2, 6, 28, 140, 740, 4056, 22904, 132344, 778832, 4652404, 28140536, 172021360, 1061153560, 6597813620, 41307119692, 260198053200, 1647958588568, 10488324116052, 67046234983840, 430300354820176, 2771678138269600, 17912347088664868, 116113406138798112

Offset: 1

Eric W. Weisstein, Apr 05 2018

nonn

			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 linear coefficients give a(n), so the first few are 0, 2, 6, 28, 140, .... - _Eric W. Weisstein_, Apr 05 2018

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

Cf. A302335 (constant coefficients).
Cf. A002931 (quadratic coefficients).
Cf. A006772, A302337.

a(n) = 2*A006772(n). - Andrey Zabolotskiy, Nov 09 2018

Terms a(12) and beyond added using data from A006772 by Andrey Zabolotskiy, Feb 10 2022

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

A302336 Linear coefficient (in absolute value) of the quadratic polynomials giving the numbers of 2k-cycles in the n X n grid graph for n >= k-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions