%I #67 Nov 05 2023 09:00:46
%S 1,2,5,16,55,222,950,4265,19591,91678,434005,2073783,9979772,48315186,
%T 235088794,1148891118,5636168859,27743309673
%N Number of ways of embedding a connected graph with n edges in the square lattice.
%C It is assumed that all edges have length one. - _N. J. A. Sloane_, Apr 17 2019
%C These are referred to as 'polysticks', 'polyedges' or 'polyforms'. - _Jack W Grahl_, Jul 24 2018
%C 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
%C The solution for n=5 features in the card game Digit. - Paweł Rafał Bieliński, Apr 17 2019
%D Brian R. Barwell, "Polysticks," Journal of Recreational Mathematics, 22 (1990), 165-175.
%H D. Goodger, <a href="http://puzzler.sourceforge.net/docs/polysticks-intro.html">An introduction to Polysticks</a>
%H M. Keller, <a href="http://www.solitairelaboratory.com/polyenum.html">Counting polyforms</a>
%H D. Knuth, <a href="https://arxiv.org/abs/cs/0011047">Dancing Links</a>, arXiv:cs/0011047 [cs.DS], 2000. (A discussion of backtracking algorithms which mentions some problems of polystick tiling.)
%H Ed Pegg, Jr., <a href="http://demonstrations.wolfram.com/PolyformExplorer/">Illustrations of polyforms</a>
%H N. J. A. Sloane, <a href="/A019988/a019988.png">Illustration of a(1)-a(4)</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Polyedge.html">Polyedge</a>
%H Wikicommons, <a href="https://commons.wikimedia.org/wiki/File:Polysticks.svg">Polysticks</a> <a href="https://commons.wikimedia.org/wiki/File:Free_connected_5-sticks_square_lattice.svg">5-sticks</a> <a href="https://commons.wikimedia.org/wiki/File:Free_connected_6-sticks_square_lattice.svg">6-sticks</a> <a href="https://commons.wikimedia.org/wiki/File:Free_connected_7-sticks_square_lattice.svg">7-sticks</a>
%F A348095(n) + A056841(n+1) = a(n). - _R. J. Mathar_, Sep 30 2021
%Y If only translations (but not rotations) are factored, consider fixed polyedges (A096267).
%Y If reflections are considered different, we obtain the one-sided polysticks, counted by (A151537). - _Jack W Grahl_, Jul 24 2018
%Y Cf. A001997, A003792, A006372, A059103, A085632, A056841 (tree-like), A348095 (with cycles), A348096 (refined by symmetry), A181528.
%Y See A336281 for another version.
%Y 6th row of A366766.
%K nonn,nice,hard,more
%O 1,2
%A _Russ Cox_
%E More terms from Brendan Owen (brendan_owen(AT)yahoo.com), Feb 20 2002
%E a(18) from _John Mason_, Jun 01 2023