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,2

Comments

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

References

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

Links

Table of n, a(n) for n=1..18.

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

Formula

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

Crossrefs

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.

Sequence in context: A308027 A066642 A333233 * A137732 A119611 A057973

Adjacent sequences: A019985 A019986 A019987 * A019989 A019990 A019991

Keyword

nonn,nice,hard,more

Author

Russ Cox

Extensions

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

a(18) from John Mason, Jun 01 2023

Status

approved