|
|
A019988
|
|
Number of ways of embedding a connected graph with n edges in the square lattice.
|
|
20
|
|
|
1, 2, 5, 16, 55, 222, 950, 4265, 19591, 91678, 434005, 2073783, 9979772, 48315186, 235088794, 1148891118, 5636168859, 27743309673
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
D. Knuth, Dancing Links, arXiv:cs/0011047 [cs.DS], 2000. (A discussion of backtracking algorithms which mentions some problems of polystick tiling.)
Eric Weisstein's World of Mathematics, Polyedge
|
|
FORMULA
|
|
|
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
|
|
KEYWORD
|
nonn,nice,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Brendan Owen (brendan_owen(AT)yahoo.com), Feb 20 2002
|
|
STATUS
|
approved
|
|
|
|