A057730 -id:A057730 - 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

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

A131482 a(n) is the number of n-celled polyominoes with perimeter 2n+2.

Original entry on oeis.org

1, 1, 2, 4, 11, 27, 83, 255, 847, 2829, 9734, 33724, 118245, 416816, 1478602, 5267171, 18840144, 67611472, 243378415, 878407170, 3178068821, 11523323634, 41865833602, 152382134767

Offset: 1

Tanya Khovanova, Jul 27 2007

2n+2 is the maximal perimeter of an n-celled polyomino. a(n) is the number of n-celled polyominoes that have a tree as their connectedness graph (vertices of this graph correspond to cells and two vertices are connected if the corresponding cells have a common edge).

Andrew Clarke, Isoperimetrical Polyominoes, The Poly Pages.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).

Cf. A000105, A057730. Diagonal of A342243.
A359522 counts only polyominoes with holes.
A002013 counts only unbranched polyominoes.
A038142 is the analog for polyhexes.

a(n) <= A000105(n), a(n) <= A057730(n+1).

a(n) >= A000602(n) [see comment on edge graph trees]. - R. J. Mathar, Mar 08 2021

a(14)-a(16) from David Radcliffe, Dec 25 2017
a(17) from David Radcliffe, Dec 26 2017
a(18)-a(24) from John Mason, Dec 11 2021

A057779 Number of hexagonal polyominoes (or polyhexes, A000228) with perimeter 2n.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 3, 2, 12, 14, 50, 98, 313, 750, 2308, 6270

Offset: 1

N. J. A. Sloane, Oct 29 2000

Cf. A000228, A000105, A057730, A258206 (counts only polyhexes without holes).

Link updated by William Rex Marshall, Dec 16 2009

a(13)-a(16) from John Mason, Jul 26 2021

A342243 Triangle T(n,p) read by rows: the number of n-celled polyominoes with perimeter 2p, 2 <= p <= 1+n.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 1, 4, 0, 0, 0, 1, 11, 0, 0, 0, 1, 7, 27, 0, 0, 0, 0, 4, 21, 83, 0, 0, 0, 0, 2, 21, 91, 255, 0, 0, 0, 0, 1, 9, 89, 339, 847, 0, 0, 0, 0, 0, 6, 67, 393, 1360, 2829, 0, 0, 0, 0, 0, 1, 45, 325, 1713, 5255, 9734, 0, 0, 0, 0, 0, 1, 23, 275

Offset: 1

R. J. Mathar, Mar 07 2021

			The triangle has rows n=1,2,3,... and columns p=2,3,4,5,...:
  1;
  0, 1;
  0, 0, 2;
  0, 0, 1, 4;
  0, 0, 0, 1, 11;
  0, 0, 0, 1,  7, 27;
  0, 0, 0, 0,  4, 21, 83;
  0, 0, 0, 0,  2, 21, 91, 255;
  0, 0, 0, 0,  1,  9, 89, 339,  847;
  0, 0, 0, 0,  0,  6, 67, 393, 1360, 2829;
  0, 0, 0, 0,  0,  1, 45, 325, 1713, 5255, 9734;
  ...

John Mason, Table of T(n,k) for n <= 18 (n <= 17 from R. J. Mathar)
Andrew Clarke, Isoperimetrical Polyominoes
John Mason, Incomplete rows for n>18

Cf. A000105 (row sums), A057730 (column sums), A131482 (diagonal), A131487 (skew antidiagonal sums), A027709 (number of leading zeros per row), A100092 (first nonzero in each row).

A131487(e) = Sum_{e=2*n+p} T(n,p).

A131487 a(n) is the number of polyominoes with n edges, including inner edges.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 1, 4, 0, 1, 11, 1, 7, 27, 4, 21, 85, 21, 92, 264, 89, 345, 914, 394, 1405, 3155, 1736, 5530, 11400, 7586, 22022, 41756, 32702, 87158, 156412, 139253, 346836, 592661, 589101, 1379837, 2275935, 2476770, 5501846, 8830267, 10363627, 21970992, 34594887, 43188260, 87950618

Offset: 1

Tanya Khovanova, Jul 28 2007

An n-celled polyomino with perimeter p has (4n+p)/2 edges. The maximum number of edges in an n-celled polyomino is 3n+1.

			A single cell has 4 edges; a domino has 7 edges (this includes the edge between the two cells); both trominoes have 10 edges; their possible orientations are not considered distinct. Thus a(4) = a(7) = 1, a(10) = 2, and a(n) = 0 for n < 10 not equal to 4 or 7.
a(22) = 85 = 83 + 2: there are 83 polyominoes with 7 cells and perimeter 16 (such as a 1 X 7 strip) and two polyominoes with 8 cells and perimeter 12 (a 3 X 3 square without a corner and a 4 X 2 rectangle), and each of these polyominoes has 22 edges.
a(23) = 21. a(24) = 91+1. a(25) = 255+9. a(26) = 89. a(27) = 339+6. a(28) = 847+67. a(34) = 9734+1655+11. a(35) = 7412+174. - _R. J. Mathar_, Feb 22 2021

Andrew Clarke, Isoperimetrical Polyominoes

Cf. A000105, A057730, A342243.

Cf. A131482 (number of n-celled polyominoes with perimeter 2n+2), A131488 (analog for hexagonal tiling).

See A342243 for formula.

a(23)-a(35) from R. J. Mathar, Feb 22 2021
a(36)-a(39) from R. J. Mathar, Mar 11 2021
a(40)-a(44) from R. J. Mathar, Mar 24 2021
a(45)-a(54) from John Mason, Apr 28 2023

A366443 Number of free polyominoes of site-perimeter n.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 5, 5, 23, 46, 187, 552, 2145, 7818

Offset: 1

John Mason from an idea of Allan C. Wechsler, Oct 10 2023

This sequence counts free connected (via common edges) polyominoes with given site-perimeter. The site-perimeter of a polyomino is the number of cells that are adjacent to it (via common edges). This sequence allows holes of any kind.

			a(4) = a(6) = a(7) = 1 as the monomino, domino and L-shaped tromino are the only polyominoes with site perimeter 4, 6 and 7 respectively.
a(5) = 0 as no polyomino has a site-perimeter of 5.
a(8) = 5 as the straight tromino, square tetromino, T-tetromino, S-tetromino and cross pentomino are the only polyominoes with site perimeter 8. See link "Examples".

John Mason, Examples

Cf. A000105 (free polyominoes), A001971 (the maximum size of a polyomino with site-perimeter n is given by A001971(n-2)), A057730 (perimeter instead of site-perimeter), A216820 (fixed version of current sequence).

Column sums of A338211 (without the column for 0-celled polyominoes).

a(15) corrected by Sean A. Irvine, Apr 13 2025

A216820 Number of polyominoes of site-perimeter n with 8-holes allowed.

Original entry on oeis.org

1, 0, 2, 4, 12, 32, 110, 340, 1209, 4272, 16166, 61848, 246660, 1004883, 4209124, 18020832, 78898047, 352437205, 1605225878, 7445515638, 35142033027, 168644213617, 822311934788, 4071431204506, 20457850555113

Offset: 4

N. J. A. Sloane, Sep 20 2012

This sequence counts fixed connected (via common edges) polyominoes with given site-perimeter. The site-perimeter of a polyomino is the number of cells that are adjacent to it (via common edges). This sequence allows holes of any kind; A216819 allows holes but requires them to be connected to each other and to the exterior area via common corners; A216818 doesn't allow holes. - Andrey Zabolotskiy, Feb 02 2022

			The only polyomino with site-perimeter 4 is a single cell.
No polyominoes have site-perimeter 5.
a(6) = 2: the domino, rotated (or reflected) in 2 possible ways.
a(7) = 4: the L-tromino, rotated in 4 ways.
a(8) = 12: the X-pentomino; the square tetromino; the straight tromino, rotated in 2 ways; the T-tetromino, rotated in 4 ways; the skew tetromino, rotated and reflected in 4 ways.

A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen., 28 (1995), 891-904. See Table 2.
J. Fortier, A. Goupil, J. Lortie and J. Tremblay, Exhaustive generation of gominoes, Theoretical Computer Science, 502 (2013), 76-87. See Table 1, beware of the typo in a(15).

Cf. A216818 (no holes), A216819 (holes connected by corners); A001168 (by area), A057730 (by perimeter); A366443 (free).

a(15) corrected, a(16)-a(28) from Conway & Guttmann added by Andrey Zabolotskiy, Feb 02 2022

A057753 Total area of all polyominoes with perimeter 2n.

Original entry on oeis.org

1, 2, 10, 27, 150, 641, 3796, 21525, 134863, 846159, 5464173, 35548106, 234007149, 1551388944, 10361158723

Offset: 2

N. J. A. Sloane, Nov 04 2000

			a(2*n=4) = 1 with area 1: 1*1=1.
a(2*n=6) is 1 with area 2: 1*2=2.
a(2*n=8) is 2 with area 3, 1 with area 4: 2*3+4=10.
a(2*n=10) is 4 with area 4, 1 with area 5, 1 with area 6: 4*4+5+6=27.
a(2*n=12) = 11*5 +7*6 +4*7 +2*8 +1*9 = 150.
a(2*n=14) = 27*6 +21*7 +21*8+ 9*9 + 6*10 +1*11 + 1*12 = 641. - _R. J. Mathar_, Feb 18 2021
a(2*n=16) = 7*83 + 8*91 + 9*89 + 10*67 + 11*45 + 12*23 + 13*11 + 14*4 + 15*2 + 16*1. - _John Mason_, Feb 18 2021

Andrew Clarke, Isoperimetrical Polyominoes
Andrew Clarke, Picture from Andrew Clarke's page showing the polyominoes of perimeters 4, 6, 8 and 10.

Cf. A057730.

Link updated by William Rex Marshall, Dec 16 2009
Offset set to 2 by R. J. Mathar, Feb 18 2021
a(8) from John Mason, Feb 18 2021
a(9)-a(16) from John Mason, Sep 08 2022

A130622 Number of polyominoes with perimeter at most 2n.

Original entry on oeis.org

0, 1, 2, 5, 11, 36, 122, 538, 2526, 13166, 71153, 400109, 2300430, 13504780, 80547558, 487327904

Offset: 1

Tanya Khovanova, Aug 10 2007

The perimeter of a polyomino is always even.
a(n) is partial sums of A057730.
a(n+1) >= A130866(n).
Is there another prime term beyond {2, 5, 11}?

Cf. A131482 (number of n-celled polyominoes with perimeter 2n+2).
Cf. A057730 (number of polyominoes (A000105) with perimeter 2n).
Cf. A130866 (number of polyominoes with at most n cells).

Offset corrected by John Mason, Jan 16 2023

a(9)-a(16) from John Mason, Jan 16 2023

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

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

A131482 a(n) is the number of n-celled polyominoes with perimeter 2n+2.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A057779 Number of hexagonal polyominoes (or polyhexes, A000228) with perimeter 2n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A342243 Triangle T(n,p) read by rows: the number of n-celled polyominoes with perimeter 2p, 2 <= p <= 1+n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A131487 a(n) is the number of polyominoes with n edges, including inner edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A366443 Number of free polyominoes of site-perimeter n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A216820 Number of polyominoes of site-perimeter n with 8-holes allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A057753 Total area of all polyominoes with perimeter 2n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A130622 Number of polyominoes with perimeter at most 2n.