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

%I #44 Mar 13 2022 09:49:55

%S 1,1,2,6,19,71,300,1370,6563,32272,161700,820166,4198764,21647353,

%T 112262033,585049063,3061951973,16084816384,84773694223

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

%C 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.

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

%C 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

%H Peter Kagey, <a href="/A343417/a343417_1.hs.txt">Haskell program for computing sequence</a>.

%e For n = 3, the a(3) = 6 polyominoes with k cells and 3-k distinguished vertices are:

%e +---+ *---+ +---+

%e | | | | | |

%e + +---+ +---+---+---+ + + * + *---+ *---+

%e | | | | | | | | | | | |

%e +---+---+, +---+---+---+, +---+, +---+, *---+, +---*,

%e where distinguished vertices are marked with asterisks.

%e 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.

%Y Cf. A000105, A343577.

%K nonn,more,hard

%O 0,3

%A _Peter Kagey_, Apr 15 2021

%E a(11)-a(18) from _John Mason_, Mar 11 2022