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

A056840 Number of rounded n-celled polyominoes.

Original entry on oeis.org

1, 2, 5, 22, 99, 580, 3557, 23295, 155437, 1057516, 7271980, 50478035, 352901040

Offset: 1

James Sellers, Aug 28 2000

There are n cells, drawn on a square grid, pointwise connected; polyominoes may be rotated by 90 degrees and turned over.
Comments from Joseph Myers, Oct 27 2003. "There is a figure for n=5 (the first term this differs from A030222) on the last Vicher's link. I think the following explains this sequence, but someone should do the computations to verify it (and probably compute counts for "fixed" shapes - orientation matters - and one-sided shapes - at the same time and add those sequences if not present).
"Consider a polyplet (A030222) as made up of n components which are polyominoes, those polyominoes being joined to each other only at corners. Then sever all but n-1 of the diagonal links in such a way that a spanning tree remains. The present sequence counts such spanning trees (where different orientations of the same spanning tree do not count as distinct; note that a single symmetrical polyplet can produce multiple identical spanning trees of lesser symmetry in different orientations, which count as the same).
"Similarly, A056841 appears to count spanning trees of polyominoes (ordinary polyominoes, A000105), where the edges shared by two squares are the edges of the graph for the purposes of forming the spanning tree and A056787 may count spanning trees of polyplets where the graph has edges joining every pair of squares that share an edge or vertex (this definitely needs computations, but it does match the first three terms)."
The difference between this sequence and A030222 is illustrated through a comment and an image in A030222, also linked to here: the figures filled with identical color count as different here, but they represent the same polyplet and are counted only once in A030222. They all arise from adding one more square in three inequivalent positions (touching a corner, one side or two sides) to the (only) 4-polyplet with a hole (depicted here as not having a hole but rather a "bay", delimited to all but one (diagonal) direction). - M. F. Hasler, Sep 29 2014

Abaroth's World, Rounded Polyominoes
M. F. Hasler, Colored illustration of A056840(5)=99 and A056840(5)=94 (based on Vicher's r7.gif).
M. Vicher, Polyforms
M. Vicher, The 22 4-celled rounded polyominoes (local copy).
M. Vicher, The 99 5-celled rounded polyominoes

Cf. A030222, A056841, A000105, A362223, A362224.

Edited by N. J. A. Sloane, Jun 21 2001

a(7)-a(13) from John Mason, Apr 12 2023

A056787 Number of incongruental unlabeled undirected trees with n nodes on a square lattice and edges of length 1 or sqrt(2) admitted to the 4 nearest or 4 2nd nearest neighbors.

Original entry on oeis.org

1, 2, 6, 40, 303, 2929, 29752, 316935

Offset: 1

James Sellers, Aug 28 2000

a(n)>=A056841(n) since the trees of A056841 are a subset of these here. Edges along diagonals may cross.

			For n=2 we have
o-o
and
..o
./.
o..
as the only a(2)=2 candidates. Trees contributing to n=7 are
o.o-o
|\.\.
o.o-o
...\.
....o
or
o....
|\...
o.o-o
...X.
..o.o
./...
o....
where dashes are edges in E, NE, N, NW, W, SW, S or SE direction that connect nodes marked 'o' horizontally, vertically or along diagonals, and X's are crossing diagonal edges.

M. Vicher, Polyforms
R. J. Mathar, C++ program
R. J. Mathar, Polyforms (ASCII art)

A348095 Number of free n-polysticks embedded in the square lattice with at least one cycle.

Original entry on oeis.org

0, 0, 0, 1, 1, 10, 42, 254, 1331, 7358, 39543, 212911, 1135876, 6039878, 31975124, 168790048, 888664299, 4669177072

Offset: 1

R. J. Mathar, Sep 30 2021

The number of holes h = e - v + 1 (e = the number of edges and v the number of vertices). - John Mason, Feb 12 2023

			The 4-stick with a cycle is the unit square. The 5-stick with a cycle is the unit square with one protruding edge. The 10 6-sticks with a cycle are the unit square with two protruding edges (in various cis, meta, trans configurations) or with a protruding 2-stick at various angles, or a 2x1 rectangle.
Size 6 examples 1 through 5:
  +-+        +-+    +        +    +-+-+
  | |        | |    |        |      | |
  +-+-+-+  +-+-+-+  +-+-+  +-+-+    +-+-+
                    | |    | |
                    +-+    +-+
Examples 6 through 10:
  +        +-+ +    +      +-+-+  +-+-+
  |        | | |    |      | |    |   |
  +-+      +-+-+    +-+-+  +-+-+  +-+-+
  | |                 | |
  +-+-+               +-+

John Mason, Examples of size 6

Cf. A056841 (tree-like), A019988 (free polysticks).

a(n) + A056841(n+1) = A019988(n).

a(14)-a(18) from John Mason, Jun 01 2023

A333233 Number of free Tangles of size n.

Original entry on oeis.org

1, 1, 2, 5, 16, 55, 221, 947, 4239, 19452, 90791, 428839, 2043548, 9807941

Offset: 0

Douglas A. Torrance, Mar 12 2020

a(n) is the number of free Tangles (smooth simple closed curves piecewise-defined by quadrants of circles) which have a dual graph containing n edges, or equivalently, enclose an area of (4*n + Pi)*r^2, where 1/r is the curvature.  By 'free', we mean that we allow rotations and reflections.
Tangles may also be 'fixed', i.e., if we do not allow rotations and reflections (A333080).
Tangles whose dual graphs are trees correspond exactly to diagonal polyominoes (A056841).
Dual graphs of Tangles are polysticks (A019988), but the only chordless cycles allowed are squares, e.g., this is *not* the dual graph of a Tangle:
o-o-o
|   |
o-o-o
but this is:
o-o-o
| | |
o-o-o

Douglas A. Torrance, Enumeration of planar Tangles, arXiv:1906.01541 [math.CO], 2020. Sums of rows from Table 4.1 (C).

Cf. A019988, A056841, A333080.

a(11)-a(13) from John Mason, Feb 14 2023

A385120 Number of fixed tree-like polyedges on the square lattice with n edges, rooted at a vertex.

Original entry on oeis.org

1, 4, 18, 88, 435, 2184, 11018, 55888, 284229, 1448800, 7396290, 37804344, 193405121, 990117104, 5072380140

Offset: 0

Ben Samberg, Jun 18 2025

			a(0) = 1: empty structure.
a(1) = 4: a single vertical or horizontal edge, rooted at one of the two vertices.
a(2) = 18: six unrooted two-edge polyedges (a straight path oriented in 2 possible ways and an L-shaped path oriented in 4 possible ways), each rooted at one of the three vertices.

Ben Samberg, a(2) visualization
Ben Samberg, Python algorithm

Cf. A096267 (not necessarily treelike), A056841 (free), A066158 (polyominoes).

Cf. A308409.

a(n) = A308409(n) * (n+1). - Andrei Zabolotskii, Jul 02 2025

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

A056840 Number of rounded n-celled polyominoes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A056787 Number of incongruental unlabeled undirected trees with n nodes on a square lattice and edges of length 1 or sqrt(2) admitted to the 4 nearest or 4 2nd nearest neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A348095 Number of free n-polysticks embedded in the square lattice with at least one cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A333233 Number of free Tangles of size n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A385120 Number of fixed tree-like polyedges on the square lattice with n edges, rooted at a vertex.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula