A342430 Number of prime polyominoes with n cells.

0, 0, 1, 2, 1, 12, 5, 108, 145, 974, 2210, 17073, 31950, 238591, 587036, 3174686, 9236343, 50107909

Offset: 0

Author

Drake Thomas, Mar 11 2021

Keywords

• nonn
• hard
• more
• nice

Comments

We say that a free polyomino is prime if it cannot be tiled by any other free polyomino besides the 1 X 1 square and itself.

The tiling of P must be with a single polyomino, and that single polyomino may not be the unique monomino or P itself. For example, decomposing the T-tetromino into a 3 X 1 and a 1 X 1 would use multiple tiles, and this is not permitted.

It can be shown that a(n) > 0 for all n >= 4, by considering the polyomino whose cells are at (0,1), (-1,1), (0,2), and (x,0) for all x = 0, 1, ..., n-4.

Examples

			For n = 4, the T-tetromino cannot be decomposed into smaller congruent polyominoes:
      +---+
      |   |
  +---+   +---+
  |           |
  +-----------+
The other four free tetrominoes can, however:
  +---+
  |   |
  |   |    +---+
  |   |    |   |
  +---+    |   |         +---+---+        +---+---+
  |   |    |   |         |   |   |        |       |
  |   |    +---+---+     |   |   |    +---+---+---+
  |   |    |       |     |   |   |    |       |
  +---+    +-------+     +---+---+    +---+---+
Thus a(4) = 1.
		

Links

• Cibulis, Liu, and Wainwright, Polyomino Number Theory (I), Crux Mathematicorum, 28(3) (2002), 147-150.

Crossrefs

Cf. A000105, A125759, A213376.

Formula

a(n) = A000105(n) if n is prime.

Extensions

a(14)-a(17) from John Mason, Sep 16 2022

a(1) corrected by John Mason, Feb 27 2023