A096267 -id:A096267 - cp's OEIS frontend

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

1, 2, 5, 16, 55, 222, 950, 4265, 19591, 91678, 434005, 2073783, 9979772, 48315186, 235088794, 1148891118, 5636168859, 27743309673

Offset: 1

Russ Cox

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

Brian R. Barwell, "Polysticks," Journal of Recreational Mathematics, 22 (1990), 165-175.

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

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.

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

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

a(18) from John Mason, Jun 01 2023

A366767 Array read by antidiagonals, where each row is the counting sequence of a certain type of fixed polyominoids.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 0, 2, 2, 0, 1, 0, 2, 4, 2, 0, 1, 0, 2, 12, 6, 1, 0, 1, 0, 2, 38, 22, 0, 1, 0, 1, 0, 2, 126, 88, 0, 2, 1, 0, 1, 0, 2, 432, 372, 0, 6, 2, 1, 0, 1, 0, 2, 1520, 1628, 0, 19, 6, 4, 3, 0, 1, 0, 2, 5450, 7312, 0, 63, 19, 20, 0, 3

Offset: 1

Pontus von Brömssen, Oct 22 2023

See A366766 (corresponding array for free polyominoids) for details.

			Array begins:
  n\k| 1  2  3   4   5    6     7      8      9      10       11        12
  ---+--------------------------------------------------------------------
   1 | 1  0  0   0   0    0     0      0      0       0        0         0
   2 | 1  1  1   1   1    1     1      1      1       1        1         1
   3 | 2  0  0   0   0    0     0      0      0       0        0         0
   4 | 2  2  2   2   2    2     2      2      2       2        2         2
   5 | 2  4 12  38 126  432  1520   5450  19820   72892   270536   1011722
   6 | 2  6 22  88 372 1628  7312  33466 155446  730534  3466170  16576874
   7 | 1  0  0   0   0    0     0      0      0       0        0         0
   8 | 1  2  6  19  63  216   760   2725   9910   36446   135268    505861
   9 | 1  2  6  19  63  216   760   2725   9910   36446   135268    505861
  10 | 1  4 20 110 638 3832 23592 147941 940982 6053180 39299408 257105146
  11 | 3  0  0   0   0    0     0      0      0       0        0         0
  12 | 3  3  3   3   3    3     3      3      3       3        3         3

Pontus von Brömssen, Python programs that relate row numbers and parameter sets.
Wikipedia, Polyominoid.
Index entries for sequences related to polyominoes.

Cf. A366766 (free), A366768.
The following table lists some sequences that are rows of the array, together with the corresponding values of D, d, and C (see A366766). Some sequences occur in more than one row. Notation used in the table:
  X: Allowed connection.
  -: Not allowed connection (but may occur "by accident" as long as it is not needed for connectedness).
  .: Not applicable for (D,d) in this row.
  !: d < D and all connections have h = 0, so these polyominoids live in d < D dimensions only.
  *: Whether a connection of type (g,h) is allowed or not is independent of h.
      |   |   | connections |
      |   |   |  g:112223   |
    n | D | d |  h:010120   | sequence
  ----+---+---+-------------+----------
| 1 | 1 |  * -.....   | A063524
| 1 | 1 |  * X.....   | A000012
|!2 | 1 |  * --....   | 2*A063524
|!2 | 1 |    X-....   | 2*A000012
| 2 | 1 |    -X....   | 2*A001168
| 2 | 1 |  * XX....   | A096267
| 2 | 2 |  * -.-...   | A063524
| 2 | 2 |  * X.-...   | A001168
| 2 | 2 |  * -.X...   | A001168
| 2 | 2 |  * X.X...   | A006770
|!3 | 1 |  * --....   | 3*A063524
|!3 | 1 |    X-....   | 3*A000012
| 3 | 1 |    -X....   | A365655
| 3 | 1 |  * XX....   | A365560
|!3 | 2 |  * ----..   | 3*A063524
|!3 | 2 |    X---..   | 3*A001168
| 3 | 2 |    -X--..   | A365655
| 3 | 2 |  * XX--..   | A075678
|!3 | 2 |    --X-..   | 3*A001168
|!3 | 2 |    X-X-..   | 3*A006770
| 3 | 2 |    -XX-..   | A365996
| 3 | 2 |    XXX-..   | A365998
| 3 | 2 |    ---X..   | A366000
| 3 | 2 |    X--X..   | A366002
| 3 | 2 |    -X-X..   | A366004
| 3 | 2 |    XX-X..   | A366006
| 3 | 2 |  * --XX..   | A365653
| 3 | 2 |    X-XX..   | A366008
| 3 | 2 |    -XXX..   | A366010
| 3 | 2 |  * XXXX..   | A365651
| 3 | 3 |  * -.-..-   | A063524
| 3 | 3 |  * X.-..-   | A001931
| 3 | 3 |  * -.X..-   | A039742
| 3 | 3 |  * X.X..-   |
| 3 | 3 |  * -.-..X   | A039741
| 3 | 3 |  * X.-..X   |
| 3 | 3 |  * -.X..X   |
| 3 | 3 |  * X.X..X   |
|!4 | 1 |  * --....   | 4*A063524
|!4 | 1 |    X-....   | 4*A000012
| 4 | 1 |    -X....   | A366341
| 4 | 1 |  * XX....   | A365562
|!4 | 2 |  * -----.   | 6*A063524
|!4 | 2 |    X----.   | 6*A001168
| 4 | 2 |    -X---.   | A366339
| 4 | 2 |  * XX---.   | A366335
|!4 | 2 |    --X--.   | 6*A001168
|!4 | 2 |    X-X--.   | 6*A006770

A365560 Number of fixed n-polysticks (or polyedges) in 3 dimensions.

Original entry on oeis.org

3, 15, 95, 681, 5277, 43086, 365313, 3186444, 28414802, 257908020, 2375037477, 22136623447, 208438845633, 1979867655945, 18948498050586, 182549617674339, 1768943859449895, 17230208981859485

Offset: 1

Pontus von Brömssen, Sep 09 2023

Stephan Mertens and Cristopher Moore, Series expansion of the percolation threshold on hypercubic lattices, J. Phys. A: Math. Theor., 51 (2018), 475001; arXiv:1805.02701 [cond-mat.stat-mech], 2018.
Index entries for sequences related to polyominoes.

Cf. A096267 (2 dimensions), A365559 (free), A365562 (4 dimensions), A365564 (5 dimensions).

14th row of A366767.

a(9)-a(12) from John Mason, Mar 06 2025
a(13) from John Mason, Mar 23 2025
a(14)-a(18) from Mertens & Moore added by Andrei Zabolotskii, Jun 27 2025

A365562 Number of fixed n-polysticks (or polyedges) in 4 dimensions.

Original entry on oeis.org

4, 28, 252, 2600, 29248, 349132, 4351944, 56062681, 741132648, 10003860384, 137367013012, 1913480724898, 26980497086268, 384428067086544, 5527398761722192

Offset: 1

Pontus von Brömssen, Sep 09 2023

Stephan Mertens and Cristopher Moore, Series expansion of the percolation threshold on hypercubic lattices, J. Phys. A: Math. Theor., 51 (2018), 475001; arXiv:1805.02701 [cond-mat.stat-mech], 2018.
Index entries for sequences related to polyominoes.

Cf. A096267 (2 dimensions), A365560 (3 dimensions), A365561 (free), A365564 (5 dimensions).

42nd row of A366767.

a(8)-a(15) from Mertens and Moore (a(8)-a(12) computed from Appendix A, a(13)-a(15) from Table 1), added by Pontus von Brömssen, Jun 29 2025

A366335 Number of fixed (4,2)-polyominoids with n cells.

Original entry on oeis.org

6, 60, 916, 16698, 336210, 7218768, 162185112, 3769221330, 89924613880

Offset: 1

Pontus von Brömssen, Oct 07 2023

A (D,d)-polyominoid is a connected set of d-dimensional unit cubes with integer coordinates in D-dimensional space, where two cubes are connected if they share a (d-1)-dimensional facet. For example, (3,2)-polyominoids are normal polyominoids (A075678), (D,D)-polyominoids are D-dimensional polyominoes (A001168, A001931, A151830, ...), and (D,1)-polyominoids are polysticks in D dimensions (A096267, A365560, A365562, ...).

Wikipedia, Polyominoid.
Index entries for sequences related to polyominoes.

Cf. A366334 (free).
46th row of A366767.
Fixed (D,d)-polyominoids:
  D\d|    1       2       3       4
  ---+--------------------------------
   1 | A000012
   2 | A096267 A001168
   3 | A365560 A075678 A001931
   4 | A365562 A366335 A366337 A151830

a(7)-a(9) from John Mason, Jul 05 2025

A365564 Number of fixed n-polysticks (or polyedges) in 5 dimensions.

Original entry on oeis.org

5, 45, 525, 7065, 104097, 1632915, 26817465, 456137580, 7975932715, 142619162000, 2597695379665, 48053332283700, 900703198101845

Offset: 1

Pontus von Brömssen, Sep 09 2023

Stephan Mertens and Cristopher Moore, Series expansion of the percolation threshold on hypercubic lattices, J. Phys. A: Math. Theor., 51 (2018), 475001; arXiv:1805.02701 [cond-mat.stat-mech], 2018.
Index entries for sequences related to polyominoes.

Cf. A096267 (2 dimensions), A365560 (3 dimensions), A365562 (4 dimensions), A365563 (free).

a(7)-a(13) from Mertens and Moore (a(7)-a(12) computed from Appendix A, a(13) from the caption of Table 1), added by Pontus von Brömssen, Jun 29 2025

A385581 Square array read by antidiagonals: T(n,d) is the number of fixed d-dimensional polysticks of size n.

Original entry on oeis.org

1, 2, 1, 3, 6, 1, 4, 15, 22, 1, 5, 28, 95, 88, 1, 6, 45, 252, 681, 372, 1, 7, 66, 525, 2600, 5277, 1628, 1, 8, 91, 946, 7065, 29248, 43086, 7312, 1, 9, 120, 1547, 15696, 104097, 349132, 365313, 33466, 1, 10, 153, 2360, 30513, 285828, 1632915, 4351944, 3186444, 155446, 1

Offset: 1

Pontus von Brömssen, Jul 04 2025

The first 17 antidiagonals are from Mertens and Moore (2018), either directly from Table 1 or computed using the perimeter polynomials in Appendix A. T(14,5) is the only unknown value in the 18th antidiagonal.

T(13,6) = 14054816418877200 (Mertens and Moore).

			Table begins:
  n\d| 1     2       3        4         5          6          7           8
  ---+---------------------------------------------------------------------
  1  | 1     2       3        4         5          6          7           8
  2  | 1     6      15       28        45         66         91         120
  3  | 1    22      95      252       525        946       1547        2360
  4  | 1    88     681     2600      7065      15696      30513       53936
  5  | 1   372    5277    29248    104097     285828     661549     1356384
  6  | 1  1628   43086   349132   1632915    5551480   15314936    36449288
  7  | 1  7312  365313  4351944  26817465  113045832  372033993  1028383408
  8  | 1 33466 3186444 56062681 456137580 2386821009 9377038237 30118187174

Pontus von Brömssen, Table of n, a(n) for n = 1..153 (first 17 antidiagonals)
Stephan Mertens and Cristopher Moore, Series expansion of the percolation threshold on hypercubic lattices, J. Phys. A: Math. Theor., 51 (2018), 475001; arXiv:1805.02701 [cond-mat.stat-mech], 2018.
Index entries for sequences related to polyominoes.

Cf. A000384 (row n=2), A385291 (polyominoes), A385582, A385583 (free).

Columns: A096267 (d=2), A365560 (d=3), A365562 (d=4), A365564 (d=5).

T(n,d) = Sum_{k=1..d} binomial(n,k)*A385582(n,k) (with A385582(n,k) = 0 if d > n).

A151537 Number of 1-sided polyedges with n edges.

Original entry on oeis.org

1, 2, 7, 25, 99, 416, 1854, 8411, 38980, 182829, 867096, 4145168, 19955321, 96619260, 470157772

Offset: 1

Ed Pegg Jr, May 13 2009

Ishino Keiichiro, Polyedge, Puzzle will be played, 2009.
Ed Pegg, Jr., Illustrations of polyforms
Eric Weisstein's World of Mathematics, Polyedge

Cf. A019988, A096267, A037245, A151538, A333249.

a(11)-a(14) from Joseph Myers, Oct 03 2011

a(15) from Ishino Keiichiro's website added by Andrey Zabolotskiy, Dec 10 2023

A308409 Number of bond trees with n bonds on the square lattice.

Original entry on oeis.org

1, 2, 6, 22, 87, 364, 1574, 6986, 31581, 144880, 672390, 3150362, 14877317, 70726936, 338158676

Offset: 0

Douglas A. Torrance, May 25 2019

a(n-1) is the number of bond trees with n sites (vertices) on the square lattice.

a(n) is the number of fixed polyedges (A096267) with n edges and no cycles.

D. S. Gaunt et al., Universality in branched polymers on d-dimensional hypercubic lattices, Journal of Physics A: Mathematical and General 15.10 (1982): 3209.
Douglas A. Torrance, Enumeration of planar Tangles, arXiv:1906.01541 [math.CO], 2019. See Table 4.1 (A).
S. G. Whittington, G. M. Torrie, and D. S. Gaunt, Branched polymers with a prescribed number of cycles, Journal of Physics A: Mathematical and General 16.8 (1983): 1695.

A333080 Number of fixed Tangles of size n.

Original entry on oeis.org

1, 2, 6, 22, 88, 372, 1626, 7292, 33309, 154374, 723740, 3425124, 16336747, 78437858

Offset: 0

Douglas A. Torrance, Mar 07 2020

a(n) is the number of fixed Tangles (smooth simple closed curves piecewise-defined by quadrants of circles) which have a dual graph containing n edges, or equivalently, enclose an area of (4*n + Pi)*r^2, where 1/r is the curvature.  By 'fixed', we mean that we do not allow rotations or reflections.
Dual graphs of Tangles are polyedges (A096267), but the only chordless cycles allowed are squares, e.g., this is *not* the dual graph of a Tangle:
    o-o-o
    |   |
    o-o-o
  but this is:
    o-o-o
    | | |
    o-o-o

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

Dual graphs of Tangles which are trees are bond trees on the square lattice (A308409), free Tangles (A333233).

a(11)-a(13) from John Mason, Feb 14 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A366767 Array read by antidiagonals, where each row is the counting sequence of a certain type of fixed polyominoids.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A365560 Number of fixed n-polysticks (or polyedges) in 3 dimensions.

Views

Author

Keywords

Links

Crossrefs

Extensions

A365562 Number of fixed n-polysticks (or polyedges) in 4 dimensions.

Views

Author

Keywords

Links

Crossrefs

Extensions

A366335 Number of fixed (4,2)-polyominoids with n cells.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A365564 Number of fixed n-polysticks (or polyedges) in 5 dimensions.

Views

Author

Keywords

Links

Crossrefs

Extensions

A385581 Square array read by antidiagonals: T(n,d) is the number of fixed d-dimensional polysticks of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A151537 Number of 1-sided polyedges with n edges.

Views

Author

Keywords

Links

Crossrefs

Extensions

A308409 Number of bond trees with n bonds on the square lattice.

Views

Author

Keywords

Comments

Links

A333080 Number of fixed Tangles of size n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions