A181528 -id:A181528 - cp's OEIS frontend

A019988 Number of ways of embedding a connected graph with n edges in the square lattice.

1, 2, 5, 16, 55, 222, 950, 4265, 19591, 91678, 434005, 2073783, 9979772, 48315186, 235088794, 1148891118, 5636168859, 27743309673

Offset: 1

Russ Cox

It is assumed that all edges have length one. - N. J. A. Sloane, Apr 17 2019
These are referred to as 'polysticks', 'polyedges' or 'polyforms'. - Jack W Grahl, Jul 24 2018
Number of connected subgraphs of the square lattice (or grid) containing n length-one line segments. Configurations differing only a rotation or reflection are not counted as different. The question may also be stated in terms of placing unit toothpicks in a connected arrangement on the square lattice. - N. J. A. Sloane, Apr 17 2019
The solution for n=5 features in the card game Digit. - Paweł Rafał Bieliński, Apr 17 2019

Brian R. Barwell, "Polysticks," Journal of Recreational Mathematics, 22 (1990), 165-175.

D. Goodger, An introduction to Polysticks
M. Keller, Counting polyforms
D. Knuth, Dancing Links, arXiv:cs/0011047 [cs.DS], 2000. (A discussion of backtracking algorithms which mentions some problems of polystick tiling.)
Ed Pegg, Jr., Illustrations of polyforms
N. J. A. Sloane, Illustration of a(1)-a(4)
Eric Weisstein's World of Mathematics, Polyedge
Wikicommons, Polysticks 5-sticks 6-sticks 7-sticks

If only translations (but not rotations) are factored, consider fixed polyedges (A096267).
If reflections are considered different, we obtain the one-sided polysticks, counted by (A151537). - Jack W Grahl, Jul 24 2018
Cf. A001997, A003792, A006372, A059103, A085632, A056841 (tree-like), A348095 (with cycles), A348096 (refined by symmetry), A181528.
See A336281 for another version.
6th row of A366766.

A348095(n) + A056841(n+1) = a(n). - R. J. Mathar, Sep 30 2021

More terms from Brendan Owen (brendan_owen(AT)yahoo.com), Feb 20 2002

a(18) from John Mason, Jun 01 2023

A255539 Number of digital images in Z^2 with 4-adjacency on n points up to isomorphism.

Original entry on oeis.org

1, 1, 1, 3, 4, 10, 19, 51, 112, 300, 746, 2042, 5450, 15197, 42192, 119561, 339594

Offset: 1

P. Christopher Staecker, Feb 24 2015

Also the number of polyominoes on n points, up to isomorphism of the adjacency graph.

Also the number of "grid graphs" (finite induced subgraphs of the integer lattice using only horizontal and vertical edges) on n vertices.

			a(4) = 3: (1) the square tetromino has the 4-cycle as its "adjacency graph"; (2) the T-tetromino corresponds to the claw graph; (3) the straight, skew, and L-tetromino all correspond to the 4-path.

P. Christopher Staecker, Some enumerations of binary digital images, arXiv 1502.06236 [math.CO], 2015.
Baoming Tang, Ehsan Khatami and Marcos Rigol, A short introduction to numerical linked-cluster expansions, Computer Physics Communications, 184 (2013), 557-564; arXiv:1207.3366 [cond-mat.stat-mech], 2012.

Cf. A000105, A181528, A255540.

a(13)-a(16) from Giovanni Resta, Apr 10 2020

a(17) from Tang et al. added by Andrey Zabolotskiy, Oct 23 2022

cp's OEIS Frontend

A019988 Number of ways of embedding a connected graph with n edges in the square lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions