A002931 -id:A002931 - cp's OEIS frontend

A010566 Number of 2n-step 2-dimensional closed self-avoiding paths on square lattice.

0, 8, 24, 112, 560, 2976, 16464, 94016, 549648, 3273040, 19781168, 121020960, 748039552, 4664263744, 29303071680, 185307690240, 1178635456752, 7535046744864, 48392012257184, 312061600211680, 2019822009608592, 13117263660884768, 85447982919036736

Offset: 1

N. J. A. Sloane

a(n) = 4n*A002931(n). There are (2n) choices for the starting point and 2 choices for the orientation, in order to produce self-avoiding closed paths from a polygon of perimeter 2n. - Philippe Flajolet, Nov 22 2003

B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 461.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Felix A. Pahl, Table of n, a(n) for n = 1..55 (from Iwan Jensen's computations of A002931, using a(n)=4n*A002931(n))
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 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.
Iwan Jensen, Series Expansions for Self-Avoiding Walks
G. S. Rushbrooke and J. Eve, On Noncrossing Lattice Polygons, Journal of Chemical Physics, 31 (1959), 1333-1334.

Cf. A002931.

A002931 = Cases[Import["https://oeis.org/A002931/b002931.txt", "Table"], {, }][[All, 2]]; a[n_] := 4n A002931[[n]];
a /@ Range[55] (* Jean-François Alcover, Jan 11 2020 *)

# Alex Nisnevich, Jul 22 2023
def num_continuations(path, dist):
    (x, y) = path[-1]
    next = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
    if dist == 1:
        return (0, 0) in next
    else:
        return sum(num_continuations(path + [c], dist - 1) for c in next if c not in path)
def A010566(n):
    return 4 * num_continuations([(0, 0), (1, 0)], 2 * n - 1) if n >= 2 else 0

A266549 Number of 2n-step 2-dimensional closed self-avoiding paths on square lattice, reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Original entry on oeis.org

0, 1, 1, 3, 6, 25, 86, 414, 1975, 10479, 56572, 316577, 1800363, 10419605, 61061169, 361978851

Offset: 1

Luca Petrone, Dec 31 2015

Differs from A057730 beginning at n = 8, since that sequence includes polyominoes with holes.

Joerg Arndt, All a(6)=25 walks of length 12, 2018
Brendan Owen, Isoperimetrical Polyominoes, part of Andrew I. Clarke's Poly Pages.
Hugo Pfoertner, Illustration of ratio A002931(n)/a(n) using Plot2, showing apparent limit of 8.
Hugo Pfoertner, Illustration of polygons of perimeter <= 16.

Apparently lim A002931(n)/a(n) = 8 for increasing n, accounting for (in most cases) 4 rotations times two flips. - Joerg Arndt, Hugo Pfoertner, Jul 09 2018

Cf. A010566, A037245 (open self-avoiding walks), A316194.

a(11)-a(16) from Joerg Arndt, Jan 25 2018

A057730 Number of polyominoes (A000105) with perimeter 2n.

Original entry on oeis.org

0, 1, 1, 3, 6, 25, 86, 416, 1988, 10640, 57987, 328956, 1900321, 11204350, 67042778, 406780346

Offset: 1

N. J. A. Sloane, Oct 29 2000

Does this include polyominoes with holes? - Franklin T. Adams-Watters, Sep 12 2006. Answer from R. J. Mathar: Yes! See the illustrations in the links (e.g. perimeter 16, area 7, No 81 or perimeter 16, area 8, No 174).

All lines (sides of cells which are not common to a pair of cells) contribute to the perimeter, including the interior sides of cavities and holes. - R. J. Mathar, Feb 19 2021

Andrew Clarke, Isoperimetrical Polyominoes
Andrew Clarke, Picture from Andrew Clarke's page showing the polyominoes of perimeters 4, 6, 8 and 10.
Gordon Hamilton, Grade 3 area and perimeter activity
R. J. Mathar, perimeter 10
R. J. Mathar, perimeter 12
R. J. Mathar, perimeter 14
R. J. Mathar, Illustrating perimeter 16, area <= 13
R. J. Mathar, Illustrating perimeter 18, area <= 13
R. J. Mathar, Illustrating perimeter 20, area <= 13

Cf. A000105, A002931, A057753, A266549 (same, but holes not allowed), column sums of A342243, A131487 (polyominoes by total number of edges).

Additional comments from Barry Cipra, Jun 08 2004
Link updated by William Rex Marshall, Dec 16 2009
a(9)-a(10) added by Luca Petrone, Jan 08 2016
a(1)-a(9) confirmed by Bert Dobbelaere, Oct 19 2018
a(10)-a(12) corrected and extended by John Mason, Jul 26 2021
a(13)-a(16) added by John Mason, Sep 08 2022

A334720 Number of 2-dimensional closed-loop self-avoiding paths on a square lattice where each path consists of steps with incrementing length from 1 to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 8, 24, 0, 0, 40, 112, 0, 0, 1376, 2008, 0, 0, 21720, 60848, 0, 0, 635544, 1517368, 0, 0, 20008456, 46010640, 0, 0, 640819936, 1571759136, 0, 0, 22704325648, 55436103264

Offset: 1

Scott R. Shannon, May 08 2020

This sequence gives the number of closed-loop self avoiding walks on a 2D square lattice where the walk starts with a step length of 1 which then increments by 1 after each step up until the step length is n. No closed-loop path is possible until n = 7.
Like A010566 all possible paths are counted, including those that are equivalent via rotation and reflection.
For n = 8, 15, 20, 24, 27, 32, 35, 39, 44, ... =  A380867, the path can be a rectangle. The first two cases are illustrated through the "Images" link from Scott R. Shannon. These numbers correspond to triangular numbers T(n) for which there are n1 > n2 > n3 > n4 >= 0 such that T(n) = 2(A+B) for A = T(n1) - T(n2) = T(n3) - T(n4) and B = T(n2) - T(n3). See A380867 for more. - M. F. Hasler, Mar 14 2025

			a(1) to a(6) = 0 as no closed-loop is possible.
a(7) = 8 as there is one path which forms a closed loop which can be walked in 8 different ways on a 2D square lattice. The path is:
.
             5
   *---.---.---.---.---*
   |                   |
   .                   .
   |                   |
   .                   .  4
   |                   |
6  .                   .
   |                   |     3
   .                   *---.---.---*
   |                               |
   .                               . 2
   |                               |
   *---.---.---.---.---.---.---X---*
                 7               1
.
See the attached link for text images of the closed loops for other n values.

A. J. Guttmann and I. G. Enting, The size and number of rings on the square lattice, J. Phys. A 21 (1988), L165-L172.
Scott R. Shannon, Images of the closed-loops for n=7,8,11,12,15.

Cf. A010566, A334877, A002931, A334756, A380867.

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.

A316194 Number of symmetric self-avoiding polygons on square lattice with perimeter 2*n, not counting rotations and reflections as distinct.

Original entry on oeis.org

0, 1, 1, 3, 4, 16, 23, 87

Offset: 1

Hugo Pfoertner, Jun 27 2018

The sequence includes polygons of 2-fold, i.e., mirror or rotational, and higher (order >= 4) symmetry.

Hugo Pfoertner, Illustration of polygons of perimeter <= 16.

Cf. A002931, A266549, A316196, A323188, A323189.

A006724 Number of fixed n-celled self-avoiding polygons on square lattice.

Original entry on oeis.org

1, 2, 6, 19, 63, 216, 756, 2684, 9638, 34930, 127560, 468837, 1732702, 6434322, 23993874, 89805691, 337237337, 1270123530, 4796310672, 18155586993, 68874803609, 261803388854, 996971935098, 3802944302442, 14528816598358

Offset: 1

N. J. A. Sloane, Simon Plouffe

Translations, rotations and reflections are not allowed.

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

I. Jensen, Table of n, a(n) for n = 1..42 (from link below)
I. G. Enting and A. J. Guttmann, On the area of square lattice polygons, J. Statist. Phys., 58 (1990), 475-484. See p. 477.
I. Jensen, More terms
Tomás Oliveira e Silva, Enumeration of polyominoes
Hugo Tremblay and Julien Vernay, On the generation of discrete figures with connectivity constraints, RAIRO-Theor. Inf. Appl. (2024) Vol. 58, Art. No. 16. See p. 13.

Cf. A002931.

A034010 Number of 2n-step self avoiding closed walks on square grid, restricted to a quadrant and passing through origin.

Original entry on oeis.org

0, 1, 2, 6, 20, 74, 300, 1302, 5944, 28266, 139010, 703102, 3641956, 19255106, 103630920, 566522778, 3140130354, 17620845976, 99977635264, 572935630884, 3313078283974

Offset: 1

Felice Russo

			When the number of steps is 8, one of the six closed paths is
0___.
| ._|
|_|

B. Hayes, How to avoid yourself, American Scientist, Vol. 86, Number 4, Jul-August 1998. p. 314-319.

A subset of the polyominoes with perimeter 2n (A006725), also a subset of A002931. Cf. A000105, A038373.

Corrected and extended by David W. Wilson
a(16)-a(18) from Alex Chernov, Jan 22 2012
a(19)-a(21) from Bert Dobbelaere, Jan 06 2019

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

A334756 Irregular table read by rows: T(n,k) is the number of 2n-step closed self-avoiding paths on a 2D square lattice with area k, where k >= n-1.

Original entry on oeis.org

0, 8, 24, 96, 16, 360, 160, 40, 1320, 960, 528, 144, 24, 4872, 4704, 3752, 2016, 840, 224, 56, 18112, 21632, 20992, 15424, 9920, 4832, 2176, 704, 192, 32, 67248, 96192, 107712, 93312, 75096, 50112, 31104, 16416, 7848, 3168, 1080, 288, 72

Offset: 1

Scott R. Shannon, May 10 2020

See A010566 for the number of closed self-avoiding 2D square lattice paths. Like that sequence here all possible paths are counted when determining the polygon areas, including those that are equivalent via rotation and reflection.

			For n = 2, total steps = 4, there are 8 different paths with an area of 1. These are the 8 possible ways to walk the polygon:
+---+
|   |
+---+
.
For n = 3, total steps = 6, there are 24 different paths with an area of 2. These are the 24 possible ways to walk the polygon:
+---+---+
|       |
+---+---+
.
For n = 4, total steps = 8, there are 96 different paths with an area of 3 and 16 different paths with an area of 4. These are the possible ways to walk the polygons:
+---+                      +---+---+
|   |                      |       |
+   +---+                  +       +
|       |                  |       |
+---+---+  for area = 3    +---+---+ for area = 4
.
For n = 5, total steps = 10, there are 360 different paths with an area of 4, 160 paths with an area of 5 and 40 different paths with an area of 6. These are the possible ways to walk the polygons:
+---+---+---+---+    +---+               +---+           +---+---+
|               |    |   |               |   |           |       |
+---+---+---+---+    +   +---+---+   +---+   +---+   +---+   +---+
                     |           |   |           |   |       |
                     +---+---+---+   +---+---+---+   +---+---+      for area = 4
.
+---+---+                      +---+---+---+
|       |                      |           |
+       +---+                  +           +
|           |                  |           |
+---+---+---+  for area = 5    +---+---+---+  for area = 6
.
Table begins:
0;
8;
24;
96,16;
360,160,40;
1320,960,528,144,24;
4872,4704,3752,2016,840,224,56;
18112,21632,20992,15424,9920,4832,2176,704,192,32;
67248,96192,107712,93312,75096,50112,31104,16416,7848,3168,1080,288,72;
249480,415040,526400,514480,468680,373280,281280,189920,120400,69120,36560,17040,7480,2720,880,240,40;
Row sums = A010566.

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.
Iwan Jensen, Series Expansions for Self-Avoiding Walks
G. S. Rushbrooke and J. Eve, On Noncrossing Lattice Polygons, Journal of Chemical Physics, 31 (1959), 1333-1334.
Scott R. Shannon, Data for n=1..12.

Cf. A008855, A010566, A002931, A316194, A001411, A037245, A352838.

T(n, k) = 4 * n * A008855(k, n). - Andrey Zabolotskiy, Sep 27 2024

cp's OEIS Frontend

A010566 Number of 2n-step 2-dimensional closed self-avoiding paths on square lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

A266549 Number of 2n-step 2-dimensional closed self-avoiding paths on square lattice, reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A057730 Number of polyominoes (A000105) with perimeter 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A334720 Number of 2-dimensional closed-loop self-avoiding paths on a square lattice where each path consists of steps with incrementing length from 1 to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A316194 Number of symmetric self-avoiding polygons on square lattice with perimeter 2*n, not counting rotations and reflections as distinct.

Views

Author

Keywords

Comments

Links

Crossrefs

A006724 Number of fixed n-celled self-avoiding polygons on square lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A034010 Number of 2n-step self avoiding closed walks on square grid, restricted to a quadrant and passing through origin.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

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

A334756 Irregular table read by rows: T(n,k) is the number of 2n-step closed self-avoiding paths on a 2D square lattice with area k, where k >= n-1.