login
A343417
a(n) is the number of free polyominoes with k cells and n-k distinguished vertices.
3
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
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
Sequence in context: A038392 A044045 A150118 * A150119 A361489 A268569
KEYWORD
nonn,more,hard
AUTHOR
Peter Kagey, Apr 15 2021
EXTENSIONS
a(11)-a(18) from John Mason, Mar 11 2022
STATUS
approved