A118797 Number of cells in smallest polyomino with n holes.

7, 11, 14, 17, 19, 23, 25, 28, 30, 33, 35, 38, 40, 43, 45, 48, 50, 53, 55, 57, 59, 62, 64, 67, 69, 71, 74, 76, 78, 81, 83, 85, 88, 90, 92, 95, 97, 99, 101, 104, 106, 108, 110, 113, 115, 117, 119, 122, 124, 126, 128, 131, 133, 135, 137, 140, 142, 144, 146, 149

Offset

1,1

Comments

The polyomino must be rook-wise connected and a hole is a collection of rook-wise connected empty cells from which a rook cannot escape. - N. J. A. Sloane, May 25 2006

From Dmitry Kamenetsky, Feb 28 2017: (Start)

There is a simple pattern that gives us a good upper bound. The idea is to use two rows of single-cell holes touching at their corners:

XXXXXXXXXXX

X X X X X X

XX X X X X X

XXXXXXXXXXX

Each new hole requires an additional 3 cells (X) to surround it. Hence we get a(n) <= 3n + 5. (End)

Links

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

Greg Malen and Érika Roldán, Topology and Geometry of Crystallized Polyominoes, arXiv:1910.10342 [math.CO], 2019.

Greg Malen and Erika Berenice Roldan-Roa, Extremal Topological and Geometric Problems for Polyominoes, El. J. Comb., 27 (2020), #P2.56. Has a typo in a(85) in Table 2.

Tomás Oliveira e Silva, Animal enumerations on the {4,4} Euclidean tiling

Example

a(1) = 7 from
  XX
  X X
  XXX

Prog

(Python)
def a(n): # Malen and Roldán (2020), Theorems 3, 4, 5
    if n < 36:
        return [7, 11, 14, 17, 19, 23, 25, 28, 30, 33, 35, 38, 40, 43, 45, 48, 50, 53, 55, 57, 59, 62, 64, 67, 69, 71, 74, 76, 78, 81, 83, 85, 88, 90, 92][n-1]
    for m in range(3, n):
        alpha = m**2
        if (m-1).bit_count() == 1: h, c = m*(m-2)//3, 1
        elif m%3 == 1: h, c = (m-1)**2//3-1, 3
        else: h, c = m*(m-2)//3-1, 4
        if h >= n: break
        alpha = m*(m+1)
        if m%3 == 2: h, c = (m+1)*(m-2)//3-1, 5
        else: h, c = m*(m-1)//3-1, 3
        if h >= n: break
    return alpha - c - 3*h + 2*n # Andrei Zabolotskii, Feb 20 2026

Crossrefs

Cf. A168339.

Cf. A239072 (h_{(n+2)^2} from Malen and Roldán (2020)), A183859 (h_{(n+2)*(n+3)}), A060919 (becomes a subsequence after subtracting 1).

Sequence in context: A004236 A153049 A065105 * A080837 A168135 A225858

Adjacent sequences: A118794 A118795 A118796 * A118798 A118799 A118800

Keyword

nonn

Author

Franklin T. Adams-Watters, May 22 2006

Extensions

a(8) added by Dmitry Kamenetsky, Feb 28 2017

a(9)-a(60) added by Peter Kagey, Oct 28 2019, from Table 2 of the Malen Roldán paper.

Status

approved