A365835 - OEIS

%I #102 Apr 03 2024 15:26:45

%S 1,4,16,62,204,776,2936,12030,48783,202734,839239,3489810,14462593,

%T 59906626,247553908,1021545890

%N For each cell of a polyomino let b be the number of cells that are in the same row or in the same column (including itself). Cells beyond gaps do not count. a(n) is the sum of the b values of all cells of all free polyominoes with n cells.

%C The sum of the b values of a polyomino seems to give an idea of its "alignment". It seems the highest values correspond to the most aligned polyominoes and the lowest values correspond to the least aligned polyominoes. For example, in an I-polyomino with n cells the sum of the b values equals n^2 = A000290(n), which is the maximum possible. Other polyominoes with k cells have a lower value.

%C A question from _Jon E. Schoenfield_: Is it true that the minimum sum of the b values (for a given value of n, the number of cells) is always obtained by only one polyomino, and that that is the one that can be built using a tight zigzag pattern (turning alternately to the left or right at each step) -- i.e., the monomino, the domino, the "L"-tromino, the "S"-tetromino, the "W"-pentomino, etc.?

%C The answer is: Yes. And the sum of the b values is equal to 3*(n - 2) + 4 = A016777(n-1), the minimum possible.

%C Hence the difference between the maximum possible and the minimum possible sum of the b values is A000290(n) - A016777(n-1) = A279019(n+3), n >= 1. Also it's equal to A002378(n-1) if n >= 2. See examples.

%C Resembles the art gallery problem.

%C Note that the concept "b value" for a cell or vertex can also be applied in other polyforms and in other types of graphs, for example: cellular automata, partitions, etc.

%C For another version see A365860, which first differs at a(5).

%H Rodolfo Kurchan, <a href="https://www.puzzlefun.online/problems">Puzzle Fun, Problems, Colored Polyominoes</a>.

%H George Sicherman, <a href="http://static.wixstatic.com/media/799cc4_0fb1e118c87c4e84903509920c43f42e~mv2.png">A colored version of the free pentominoes</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Polyomino">Polyomino</a>.

%H Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Art_gallery_problem">Art gallery problem</a>.

%F a(n) == A057766(n) (mod 2). - _Pontus von Brömssen_, Sep 21 2023

%e For n = 1 the monomino has only one cell, so a(1) = 1.

%e For n = 2 the domino has two cells. Each cell sees the other cell. The sum of the b values is 2 + 2 = 4, so a(2) = 4.

%e For n = 3 the sum of the b values of the I-tromino is 3 + 3 + 3 = 9 and the sum of the b values of the L-tromino is 3 + 2 + 2 = 7. The total sum is 9 + 7 = 16, so a(3) = 16.

%e For n = 4 the b values of the five tetrominoes (I, L, O, T, S) are 16, 12, 12, 12, 10, so the total sum of the b values is a(4) = 62.

%e Three examples from the twelve pentominoes:

%e The I-pentomino with its b values looks like this:

%e       +---+

%e       | 5 |

%e       +---+

%e       | 5 |

%e       +---+

%e       | 5 |

%e       +---+

%e       | 5 |

%e       +---+

%e       | 5 |

%e       +---+

%e The sum of the b values is 5 + 5 + 5 + 5 + 5 = 5^2 = A000290(5) = 25, the maximum possible.

%e .

%e The U-pentomino with its b values looks like this:

%e   +---+   +---+

%e   | 2 |   | 2 |

%e   +---+---+---+

%e   | 4 | 3 | 4 |

%e   +---+---+---+

%e The sum of the b values is 4 + 4 + 3 + 2 + 2 = 15.

%e .

%e The W-pentomino with its b values looks like this:

%e   +---+

%e   | 2 |

%e   +---+---+

%e   | 3 | 3 |

%e   +---+---+---+

%e       | 3 | 2 |

%e       +---+---+

%e The sum of the b values is 3 + 3 + 3 + 2 + 2 = 3*(5-2) + 4 = A016777(5-1) = 13, the minimum possible.

%e .

%Y Row sums of A365906.

%Y Cf. A000105, A000290, A002378, A016777, A057766, A279019, A365860.

%K nonn,more

%O 1,2

%A _Rodolfo Kurchan_ and _Omar E. Pol_, Sep 19 2023

%E a(6)-a(9) from _George Sicherman_, Sep 20 2023

%E a(6)-a(9) corrected and a(10)-a(13) added by _Pontus von Brömssen_, Sep 21 2023

%E a(14)-a(16) from _Pontus von Brömssen_, Apr 03 2024