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

Author

Russ Cox

Keywords

• nonn
• nice
• hard
• more

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

• 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

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.

Formula

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

Extensions

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

a(18) from John Mason, Jun 01 2023