A380286 Number of distinct values of the number of regions between the free polyominoes with n cells and their bounding boxes.

1, 1, 2, 3, 5, 5, 5, 6, 7, 7, 7, 8, 9, 9, 9, 10, 11, 11, 11, 12, 13, 13, 13, 14, 15, 15, 15, 16, 17, 17, 17, 18, 19, 19, 19, 20, 21, 21, 21, 22, 23, 23, 23, 24, 25, 25, 25, 26, 27, 27, 27, 28, 29, 29, 29, 30, 31, 31, 31, 32, 33, 33, 33, 34, 35, 35, 35, 36, 37, 37, 37

Offset

1,3

Comments

The regions include any holes in the polyominoes.

From Andrew Howroyd, Mar 01 2025: (Start)

Consider the following sequence of polyominoes for n >= 5:

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 O O O O O O O O O

O O O O O O O O

This construction shows how the number of regions between the polyomino and its bounding box can be increased by 2 with the addition of 4 cells. It is also easy to see that any number of fewer holes can also be realized. Moreover, this construction gives the greatest number of regions since except for four corner regions every other region must be bounded on 3 sides by at least one cell separating it from a neighboring region. This leads to a formula for a(n). (End)

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Index entries for sequences related to polyominoes.

Index entries for linear recurrences with constant coefficients, signature (2,-2,2,-1).

Formula

From Andrew Howroyd, Mar 01 2025: (Start)

a(n) = A004525(n + 4) for n >= 5.

G.f.: x*(1 - x + 2*x^2 - x^3 + 2*x^4 - 2*x^5 + x^6 - x^7)/((1 - x)^2*(1 + x^2)). (End)

E.g.f.: (exp(x)*(4 + x) + sin(x))/2 - 2 - 2*x - x^2 - x^3/6 - x^4/24. - Stefano Spezia, Mar 03 2025

Example

Illustration for n = 4:
The free polyominoes with four cells are also called free tetrominoes.
The five free tetrominoes are as shown below:
    _
   |_|     _       _       _
   |_|    |_|     |_|_    |_|_     _ _
   |_|    |_|_    |_|_|   |_|_|   |_|_|
   |_|    |_|_|     |_|   |_|     |_|_|
.
The bounding boxes are respectively as shown below:
    _
   | |     _ _     _ _     _ _
   | |    |   |   |   |   |   |    _ _
   | |    |   |   |   |   |   |   |   |
   |_|    |_ _|   |_ _|   |_ _|   |_ _|
.
From left to right the number of regions between the free tetrominoes and their bounding boxes are respectively [0, 1, 2, 2, 0], hence there are three distinct values of the number of regions, they are [0, 1, 2], so a(4) = 3.
.

Mathematica

LinearRecurrence[{2, -2, 2, -1}, {1, 1, 2, 3, 5, 5, 5, 6}, 100] (* Paolo Xausa, Mar 02 2025 *)

Crossrefs

Row lengths of A380282.

Cf. A000105, A379627, A379628, A380283, A380284, A380285.

Sequence in context: A102642 A183228 A133304 * A246401 A003660 A065688

Adjacent sequences: A380283 A380284 A380285 * A380287 A380288 A380289

Keyword

nonn,easy,changed

Author

Omar E. Pol, Jan 24 2025

Extensions

a(8)-a(16) from Pontus von Brömssen, Jan 24 2025

a(17)-a(18) from John Mason, Feb 14 2025

a(19) onwards from Andrew Howroyd, Feb 17 2025

Status

approved