A001419 Number of n-celled polyominoes with holes.

0, 0, 0, 0, 0, 0, 1, 6, 37, 195, 979, 4663, 21474, 96496, 425449, 1849252, 7946380, 33840946, 143060339, 601165888, 2513617990, 10466220315, 43425174374, 179630865835, 741123699012, 3050860717372, 12534339432498, 51408312232300, 210526591157926, 860989703302456

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• hard

Comments

From John Mason, Sep 06 2022: (Start)

Conjecture: Almost all polyominoes are holey. In other words, a(n)/A000105(n) tends to 1 for increasing n.

The number of holes in a polyomino is given by the formula (based on a generalization of Pick's Theorem): H = n + 1 - i - s / 2, where:

n is the size (area) of the polyomino;

i is the number of completely internal vertices; i.e., the number of vertices that are surrounded by 4 squares;

s is the number of vertices on a single border; i.e., vertices that are the corners of 1, 2 or 3 squares, but excluding those that touch only 2 squares that are diagonally adjacent. (End)

References

• S. W. Golomb, Polyominoes. Scribner's, NY, 1965; second edition ( Polyominoes: Puzzles, Packings, Problems and Patterns) Princeton Univ. Press, 1994.
• Joseph S. Madachy, "Pentominoes - Some Solved and Unsolved Problems", J. Rec. Math., 2 (1969), 181-188.
• George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• John Mason, Table of n, a(n) for n = 1..40
• W. R. Muller, K. Szymanski, J. V. Knop, and N. Trinajstic, On the number of square-cell configurations, Theor. Chim. Acta 86 (1993) 269-278.
• Joseph Myers, Polyomino tiling
• T. R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy).
• R. C. Read, Contributions to the cell growth problem, Canad. J. Math., 14 (1962), 1-20.
• Eric Weisstein's World of Mathematics, Polyomino.
• Wikipedia, The 6 Octominoes with holes
• Wikipedia, The 37 Nonominoes with holes

Crossrefs

Cf. A000104, A000105.

Programs

Mathematica

A[s_] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import[ "https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A000104 = A@104;
A000105 = A@105;
a[n_] := A000105[[n + 1]] - A000104[[n + 1]];
a /@ Range[40] (* Jean-François Alcover, Jan 04 2020, updated Apr 21 2024 after John Mason's b-file *)

Formula

a(n) >= A057418(n). - R. J. Mathar, Jun 15 2014

a(n) = A000105(n) - A000104(n). - Jean-François Alcover, Jan 04 2020, after R. J. Mathar in A000105.

Extensions

More terms from Joseph Myers, May 05 2002

More terms from Joseph Myers, Nov 04 2003

a(24)-a(26) from Joseph Myers, Nov 17 2010

More terms from John Mason, Oct 10 2022