login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019988 Number of ways of embedding a connected graph with n edges in the square lattice. 20

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)