login
A187276
Number of d+/d- diagonally convex polyominoes with n cells.
2
1, 2, 6, 19, 61, 196, 630, 2024, 6499, 20860, 66941, 214797, 689201, 2211347, 7095226, 22765414, 73044113, 234366327, 751978494, 2412768983, 7741517800, 24839137696, 79697907919, 255715662623
OFFSET
1,2
COMMENTS
A polyomino is d+ [d-] convex if the intersection of its interior with any line of slope 1 [-1] through the centers of the cells is connected.
REFERENCES
M. Bousquet-Mélou and R. Brak, "Exactly Solved Models", in A. J. Guttmann, ed., Polygons, Polyominoes and Polycubes, Springer, 2009, pp. 46 & 76.
EXAMPLE
A(5) = 61 = A001168(5) - 2, omitting two of the orientations of the V pentomino.
MATHEMATICA
ab[n_, m_, q_]:=Sum[q[n-m-r, k], {r, 1, m}, {k, m+1-r, n-m-r}]
bb[n_, m_, q_]:=Sum[q[n-m-r, m-r], {r, 1, m-1}]+Sum[q[n-m-r, k], {r, 1, m-1}, {k, m-r, n-m-r}]
cb[n_, m_, q_]:=Sum[q[n-m-r, m-1-r], {r, 1, m-2}]
a[n_, m_]:=0/; n<=1||m<=0
a[n_, m_]:=a[n, m]=Sum[(k-m)p[n-m, k], {k, m+1, n-m}]+ab[n, m, b]+2ab[n, m, c]+Sum[(r-1)c[n-m-r, m+1-r], {r, 2, m}]
b[1, 1]=1;
b[n_, m_]:=0/; n<=1||m<=0
b[n_, m_]:=b[n, m]=2Sum[p[n-m, k], {k, m, n-m}]+bb[n, m, b]+2bb[n, m, c]+2Sum[(r-1)c[n-m-r, m-r], {r, 2, m-1}]
c[n_, m_]:=0/; n<=1||m<=0
c[n_, m_]:=c[n, m]=p[n-m, m-1]+cb[n, m, b]+2cb[n, m, c]+Sum[(r-1)c[n-m-r, m-1-r], {r, 2, m-2}]
p[n_, m_]:=a[n, m]+b[n, m]+c[n, m]
Table[Sum[p[n, m], {m, (n+1)/2}], {n, 20}]
CROSSREFS
Cf. A001168 (fixed polyominoes), A001169 (row-convex polyominoes).
Sequence in context: A371708 A318127 A001169 * A022041 A018906 A014010
KEYWORD
nonn
AUTHOR
David Bevan, Mar 07 2011
EXTENSIONS
Typo in example corrected by David Bevan, Mar 23 2013
STATUS
approved