A348095 -id:A348095

Search: a348095 -id:a348095

Displaying 1-2 of 2 results found.

page 1

A019988

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

+10
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

Table of n, a(n) for n=1..18.

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

FORMULA

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

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.

KEYWORD

nonn,nice,hard,more,changed

AUTHOR

Russ Cox

EXTENSIONS

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

a(18) from John Mason, Jun 01 2023

STATUS

approved

A056841

Number of diagonal polyominoes with n cells.

+10
6

1, 1, 2, 5, 15, 54, 212, 908, 4011, 18260, 84320, 394462, 1860872, 8843896, 42275308, 203113670, 980101070, 4747504560, 23074132601

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Apparently the cells are circular blobs which must be connected diagonally and the polyominoes can be rotated by 90 degrees and turned over.

Also the number of essentially different (i.e., not related by reflections, translations or rotations) diagrams consisting of n nodes in Z^2 and n-1 horizontal or vertical edges of length 1 between pairs of nodes such that the resulting graph is connected (hence a tree). - Paul Boddington, Jul 27 2004

They are thus equivalent to a subset of the polyedges, counted by A019988, i.e., those that are treelike. - John Mason, Aug 20 2021

The number of treelike polyedges with n edges is a(n+1). - John Mason, Feb 12 2023

LINKS

Table of n, a(n) for n=1..19.

R. J. Mathar, Table of all such polyominoes with n <= 10 cells (gzipped)

R. J. Mathar, C++ program

Douglas A. Torrance, Enumeration of planar Tangles, arXiv:1906.01541 [math.CO], 2019-2020. See Table 4.1 (C).

M. Vicher, Polyforms

M. Vicher, The 15 5-celled diagonal polyominoes

FORMULA

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

EXAMPLE

The diagonal polyominoes with 1, 2, 3 and 4 cells are

O O O O O

\ \ \ /

O O O

O O O O O O

\ \ \ / \ / /

O O O O O O O

\ / \ \ / /

O O O O O

\ \

O O

CROSSREFS

See also A056840, A056787, A019988 (free polysticks), A348095 (with cycles).

KEYWORD

nonn,nice,more

AUTHOR

James A. Sellers, Aug 28 2000

EXTENSIONS

Description revised by N. J. A. Sloane, Jun 21 2001

a(10) from R. J. Mathar, Apr 10 2006

a(11) from Douglas A. Torrance, Mar 06 2020

a(12)-a(14) from John Mason, Aug 14 2021

a(15)-a(19) from John Mason, Jun 01 2023

STATUS

approved

page 1

Search completed in 0.005 seconds