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,3

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

Links

Table of n, a(n) for n=0..18.

Peter Kagey, Haskell program for computing sequence.

Example

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.

Crossrefs

Cf. A000105, A343577.

Sequence in context: A038392 A044045 A150118 * A150119 A361489 A378586

Adjacent sequences: A343414 A343415 A343416 * A343418 A343419 A343420

Keyword

nonn,more,hard

Author

Peter Kagey, Apr 15 2021

Extensions

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

Status

approved