login
Number of n-celled polyominoes with holes.
(Formerly M4226 N1767)
16

%I M4226 N1767 #70 Apr 21 2024 11:40:35

%S 0,0,0,0,0,0,1,6,37,195,979,4663,21474,96496,425449,1849252,7946380,

%T 33840946,143060339,601165888,2513617990,10466220315,43425174374,

%U 179630865835,741123699012,3050860717372,12534339432498,51408312232300,210526591157926,860989703302456

%N Number of n-celled polyominoes with holes.

%C From _John Mason_, Sep 06 2022: (Start)

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

%C 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:

%C n is the size (area) of the polyomino;

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

%C 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)

%D S. W. Golomb, Polyominoes. Scribner's, NY, 1965; second edition ( Polyominoes: Puzzles, Packings, Problems and Patterns) Princeton Univ. Press, 1994.

%D Joseph S. Madachy, "Pentominoes - Some Solved and Unsolved Problems", J. Rec. Math., 2 (1969), 181-188.

%D George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H John Mason, <a href="/A001419/b001419.txt">Table of n, a(n) for n = 1..40</a>

%H W. R. Muller, K. Szymanski, J. V. Knop, and N. Trinajstic, <a href="https://doi.org/10.1007/BF01130823">On the number of square-cell configurations</a>, Theor. Chim. Acta 86 (1993) 269-278.

%H Joseph Myers, <a href="http://www.polyomino.org.uk/mathematics/polyform-tiling/">Polyomino tiling</a>

%H T. R. Parkin, L. J. Lander, and D. R. Parkin, <a href="/A000104/a000104.pdf">Polyomino Enumeration Results</a>, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy).

%H R. C. Read, <a href="http://dx.doi.org/10.4153/CJM-1962-001-2">Contributions to the cell growth problem</a>, Canad. J. Math., 14 (1962), 1-20.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Polyomino.html">Polyomino.</a>

%H Wikipedia, <a href="https://commons.wikimedia.org/wiki/File:Octominoes_with_holes.svg">The 6 Octominoes with holes</a>

%H Wikipedia, <a href="https://commons.wikimedia.org/wiki/File:The_37_Nonominoes_with_Holes.svg">The 37 Nonominoes with holes</a>

%F a(n) >= A057418(n). - _R. J. Mathar_, Jun 15 2014

%F a(n) = A000105(n) - A000104(n). - _Jean-François Alcover_, Jan 04 2020, after _R. J. Mathar_ in A000105.

%t A[s_] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import[ "https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {_, _}][[All, 2]]];

%t A000104 = A@104;

%t A000105 = A@105;

%t a[n_] := A000105[[n + 1]] - A000104[[n + 1]];

%t a /@ Range[40] (* _Jean-François Alcover_, Jan 04 2020, updated Apr 21 2024 after _John Mason_'s b-file *)

%Y Cf. A000104, A000105.

%K nonn,hard

%O 1,8

%A _N. J. A. Sloane_

%E More terms from _Joseph Myers_, May 05 2002

%E More terms from _Joseph Myers_, Nov 04 2003

%E a(24)-a(26) from _Joseph Myers_, Nov 17 2010

%E More terms from _John Mason_, Oct 10 2022