cp's OEIS Frontend

A365835 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.

%I A365835 #102 Apr 03 2024 15:26:45
%S A365835 1,4,16,62,204,776,2936,12030,48783,202734,839239,3489810,14462593,
%T A365835 59906626,247553908,1021545890
%N A365835 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 A365835 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 A365835 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 A365835 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 A365835 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 A365835 Resembles the art gallery problem.
%C A365835 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 A365835 For another version see A365860, which first differs at a(5).
%H A365835 Rodolfo Kurchan, <a href="https://www.puzzlefun.online/problems">Puzzle Fun, Problems, Colored Polyominoes</a>.
%H A365835 George Sicherman, <a href="http://static.wixstatic.com/media/799cc4_0fb1e118c87c4e84903509920c43f42e~mv2.png">A colored version of the free pentominoes</a>.
%H A365835 Wikipedia, <a href="https://en.wikipedia.org/wiki/Polyomino">Polyomino</a>.
%H A365835 Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Art_gallery_problem">Art gallery problem</a>.
%F A365835 a(n) == A057766(n) (mod 2). - _Pontus von Brömssen_, Sep 21 2023
%e A365835 For n = 1 the monomino has only one cell, so a(1) = 1.
%e A365835 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 A365835 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 A365835 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 A365835 Three examples from the twelve pentominoes:
%e A365835 The I-pentomino with its b values looks like this:
%e A365835       +---+
%e A365835       | 5 |
%e A365835       +---+
%e A365835       | 5 |
%e A365835       +---+
%e A365835       | 5 |
%e A365835       +---+
%e A365835       | 5 |
%e A365835       +---+
%e A365835       | 5 |
%e A365835       +---+
%e A365835 The sum of the b values is 5 + 5 + 5 + 5 + 5 = 5^2 = A000290(5) = 25, the maximum possible.
%e A365835 .
%e A365835 The U-pentomino with its b values looks like this:
%e A365835   +---+   +---+
%e A365835   | 2 |   | 2 |
%e A365835   +---+---+---+
%e A365835   | 4 | 3 | 4 |
%e A365835   +---+---+---+
%e A365835 The sum of the b values is 4 + 4 + 3 + 2 + 2 = 15.
%e A365835 .
%e A365835 The W-pentomino with its b values looks like this:
%e A365835   +---+
%e A365835   | 2 |
%e A365835   +---+---+
%e A365835   | 3 | 3 |
%e A365835   +---+---+---+
%e A365835       | 3 | 2 |
%e A365835       +---+---+
%e A365835 The sum of the b values is 3 + 3 + 3 + 2 + 2 = 3*(5-2) + 4 = A016777(5-1) = 13, the minimum possible.
%e A365835 .
%Y A365835 Row sums of A365906.
%Y A365835 Cf. A000105, A000290, A002378, A016777, A057766, A279019, A365860.
%K A365835 nonn,more
%O A365835 1,2
%A A365835 _Rodolfo Kurchan_ and _Omar E. Pol_, Sep 19 2023
%E A365835 a(6)-a(9) from _George Sicherman_, Sep 20 2023
%E A365835 a(6)-a(9) corrected and a(10)-a(13) added by _Pontus von Brömssen_, Sep 21 2023
%E A365835 a(14)-a(16) from _Pontus von Brömssen_, Apr 03 2024