A365860 For every cell of a polyomino let c be the number of cells that are in the same row or in the same column (including itself). a(n) is the sum of the c values of all cells of all free polyominoes with n cells.

1, 4, 16, 62, 206, 790, 3042, 12648, 52181, 220372, 927333, 3917738, 16491489, 69356256, 290882884, 1217780926

Offset: 1

Author

Rodolfo Kurchan and Omar E. Pol, Sep 20 2023

Keywords

• nonn
• more

Comments

For a polyomino with n cells the maximum sum possible of the c values equals n^2 = A000290(n) and the minumum sum possible of the c values equals 3*(n - 2) + 4 = A016777(n-1). Hence the difference between the maximum possible and the minimum possible sum of the c 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.

Note that the concept "c 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 and further information see A365835, which first differs at a(5).

Examples

			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 c values is 2 + 2 = 4, so a(2) = 4.
For n = 3 the sum of the c values of the I-tromino is 3 + 3 + 3 = 9 and the sum of the c values of the L-tromino is 3 + 2 + 2 = 7. The total sum of the c values is 9 + 7 = 16, so a(3) = 16.
For n = 4 the c values of the five (I, L, O, T, S) tetrominoes are 16, 12, 12, 12, 10 so the total sum of the c values is a(4) = 62.
Three examples from the twelve pentominoes:
The I-pentomino with its c values looks like this:
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
      | 5 |
      +---+
The sum of the c values is 5 + 5 + 5 + 5 + 5 = 5^2 = 25, the maximum possible.
.
The U-pentomino with its c values looks like this:
  +---+   +---+
  | 3 |   | 3 |
  +---+---+---+
  | 4 | 3 | 4 |
  +---+---+---+
The sum of the c values is 4 + 4 + 3 + 3 + 3 = 17.
.
The W-pentomino with its c values looks like this:
  +---+
  | 2 |
  +---+---+
  | 3 | 3 |
  +---+---+---+
      | 3 | 2 |
      +---+---+
The sum of the c values is 3 + 3 + 3 + 2 + 2 = 3*(5-2) + 4 = 13, the minimum possible.
.
		

Links

• Rodolfo Kurchan, Puzzle Fun, Problems, Colored Polyominoes

Crossrefs

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

Formula

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

Extensions

a(7)-a(9) from George Sicherman, Sep 20 2023

a(10)-a(13) from Pontus von Brömssen, Sep 21 2023

a(14)-a(16) from Pontus von Brömssen, Apr 03 2024