A365860 -id:A365860 - 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.

1, 4, 16, 62, 204, 776, 2936, 12030, 48783, 202734, 839239, 3489810, 14462593, 59906626, 247553908, 1021545890

Offset: 1

Rodolfo Kurchan and Omar E. Pol, Sep 19 2023

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.
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.?
The answer is: Yes. And the sum of the b values is equal to 3*(n - 2) + 4 = A016777(n-1), the minimum possible.
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.
Resembles the art gallery problem.
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.
For another version see A365860, which first differs at a(5).

			For n = 1 the monomino has only one cell, so a(1) = 1.
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.
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.
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.
Three examples from the twelve pentominoes:
The I-pentomino with its b values looks like this:
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
The sum of the b values is 5 + 5 + 5 + 5 + 5 = 5^2 = A000290(5) = 25, the maximum possible.
.
The U-pentomino with its b values looks like this:
  +---+   +---+
  | 2 |   | 2 |
  +---+---+---+
  | 4 | 3 | 4 |
  +---+---+---+
The sum of the b values is 4 + 4 + 3 + 2 + 2 = 15.
.
The W-pentomino with its b values looks like this:
  +---+
  | 2 |
  +---+---+
  | 3 | 3 |
  +---+---+---+
      | 3 | 2 |
      +---+---+
The sum of the b values is 3 + 3 + 3 + 2 + 2 = 3*(5-2) + 4 = A016777(5-1) = 13, the minimum possible.
.

Rodolfo Kurchan, Puzzle Fun, Problems, Colored Polyominoes.
George Sicherman, A colored version of the free pentominoes.
Wikipedia, Polyomino.
Wikipedia, Art gallery problem.

Row sums of A365906.

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

a(n) == A057766(n) (mod 2). - Pontus von Brömssen, Sep 21 2023

a(6)-a(9) from George Sicherman, Sep 20 2023
a(6)-a(9) corrected and a(10)-a(13) added by Pontus von Brömssen, Sep 21 2023
a(14)-a(16) from Pontus von Brömssen, Apr 03 2024

A365906 Irregular triangle T(n,k) read by rows, n>=1, k>=1, in which row n lists in nonincreasing order the sum of the b values (described in A365835) of the cells of every free polyomino with n cells.

Original entry on oeis.org

1, 4, 9, 7, 16, 12, 12, 12, 10, 25, 19, 19, 17, 17, 17, 17, 15, 15, 15, 15, 13, 36, 28, 28, 28, 24, 24, 24, 24, 24, 24, 24, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 20, 20, 20, 20, 20, 20, 20, 18, 18, 18, 18, 18, 16, 49, 39, 39, 39, 33, 33, 33, 33, 33, 33

Offset: 1

Rodolfo Kurchan and Omar E. Pol, Sep 22 2023

Observation: at least for 1 <= n <= 6 the parity of the terms in row n coincides with the parity of n. If n is odd then every polyomino has an odd number of odd b values, otherwise if n is even then every polyomino has an even number of odd b values.

The preceding observation is true for all n, because the b-values count each cell once (it is in the same row/column as itself) and pairs of distinct cells in the same row or column (with no gaps in between) twice (once in each direction). - Pontus von Brömssen, Oct 15 2023

			Triangle begins:
   1;
   4;
   9,  7;
  16, 12, 12, 12, 10;
  25, 19, 19, 17, 17, 17, 17, 15, 15, 15, 15, 13;
  ...
For n = 5 the twelve pentominoes and the b values of their cells are as shown below:
.
      I     L         Y      P        T       V           X
.     _     _         _     _ _     _ _ _     _           _
     |_|   |_|      _|_|   |_|_|   |_|_|_|   |_|        _|_|_
     |_|   |_|     |_|_|   |_|_|     |_|     |_|_ _    |_|_|_|
     |_|   |_|_      |_|   |_|       |_|     |_|_|_|     |_|
     |_|   |_|_|     |_|
     |_|
      5     4         4     4 3     3 5 3     3           3
      5     4       2 5     4 3       3       3         3 5 3
      5     4         4     3         3       5 3 3       3
      5     5 2       4
      5
.
      F        N        U         Z         W
.     _ _       _     _   _     _ _       _
    _|_|_|    _|_|   |_|_|_|   |_|_|     |_|_
   |_|_|     |_|_|   |_|_|_|     |_|_    |_|_|_
     |_|     |_|                 |_|_|     |_|_|
             |_|
      4 2       2     2   2     2 4       2
    2 4       4 3     4 3 4       3       3 3
      3       3                   4 2       3 2
              3
.
T(5,k) is the sum of the b values of all cells of the k-th pentomino from the diagram.
For further information see also A365835.

Pontus von Brömssen, Table of n, a(n) for n = 1..6473 (first 10 rows)
Rodolfo Kurchan, Puzzle Fun, Problems, Colored Polyominoes
George Sicherman, A colored version of the free pentominoes

Row lengths give A000105, n >= 1.
Right border gives A016777.
Row sums give A365835.
Cf. A000035, A000290, A002378, A057766, A117950, A279019, A365860.

For n >= 1; T(n,1) = n^2.
For n >= 3; T(n,2) = (n - 1)^2 + 3 = A117950(n-1).
For n >= 4; T(n,3) = (n - 1)^2 + 3 = A117950(n-1).

Terms a(61) and beyond from Pontus von Brömssen, Oct 15 2023

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions