A343417 a(n) is the number of free polyominoes with k cells and n-k distinguished vertices.

1, 1, 2, 6, 19, 71, 300, 1370, 6563, 32272, 161700, 820166, 4198764, 21647353, 112262033, 585049063, 3061951973, 16084816384, 84773694223

Offset: 0

Author

Peter Kagey, Apr 15 2021

Keywords

• nonn
• more
• hard

Comments

This sequence counts "free" polyominoes where holes are allowed. This means that two polyominoes are considered the same if one is a rigid transformation (translation, rotation, reflection or glide reflection) of the other.

A000105(n) <= a(n) <= A343577(n).

For an ordinary, asymmetrical polyomino, the number of free polyominoes with d distinguished cells is equal to C(v,d), where v is the number of vertices of the polyomino, and C is the binomial coefficient (A007318). - John Mason, Mar 11 2022

Examples

			For n = 3, the a(3) = 6 polyominoes with k cells and 3-k distinguished vertices are:
+---+                     *---+  +---+
|   |                     |   |  |   |
+   +---+  +---+---+---+  +   +  *   +  *---+  *---+
|       |  |           |  |   |  |   |  |   |  |   |
+---+---+, +---+---+---+, +---+, +---+, *---+, +---*,
where distinguished vertices are marked with asterisks.
For n = 4, a(4) = 19 because there are A000105(4) = 5 polyominoes with four cells and no distinguished vertices, 7 polyominoes with three cells and one distinguished vertex, 6 polyominoes with two cells and two distinguished vertices, and 1 polyomino with one cell and three distinguished vertices.
		

Links

• Peter Kagey, Haskell program for computing sequence.

Crossrefs

Cf. A000105, A343577.

Extensions

a(11)-a(18) from John Mason, Mar 11 2022