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

A096267 Number of fixed polyedges with n edges (number of ways of embedding connected undirected graphs with n edges into the plane square lattice, inequivalent up to translation).

Original entry on oeis.org

2, 6, 22, 88, 372, 1628, 7312, 33466, 155446, 730534, 3466170, 16576874, 79810756, 386458826, 1880580352, 9190830700, 45088727820, 221945045488, 1095798917674, 5424898610958, 26922433371778, 133906343014110, 667370905196930, 3332257266746004

Offset: 1

Alexander Malkis, Jun 22 2004

nonn

Found using the rooted method (also known as Redelmeier's algorithm).

			_|_|_ is a polyedge with 5 edges

Alexander Malkis, Polyedges, polyominoes and the 'Digit' game, diploma thesis in computer science, Universität des Saarlandes, 2003, Saarbrücken.
Stephan Mertens and Cristopher Moore, Series expansion of the percolation threshold on hypercubic lattices, J. Phys. A: Math. Theor., 51 (2018), 475001. See Table 1.

Cf. A019988 for "free" polyedges, A348096.

6th row of A366767.

a(22)-a(24) from Mertens & Moore added by Andrey Zabolotskiy, Feb 01 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