cp's OEIS Frontend

A019988 Number of ways of embedding a connected graph with n edges in the square lattice.

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