A324009 The number of convex polyominoes whose smallest bounding rectangle has size w*h (w > 0, h > 0). The table is read by antidiagonals.
1, 1, 1, 1, 5, 1, 1, 13, 13, 1, 1, 25, 68, 25, 1, 1, 41, 222, 222, 41, 1, 1, 61, 555, 1110, 555, 61, 1, 1, 85, 1171, 3951, 3951, 1171, 85, 1, 1, 113, 2198, 11263, 19010, 11263, 2198, 113, 1, 1, 145, 3788, 27468, 70438, 70438, 27468, 3788, 145, 1
Offset: 1
Examples
For w=3 and h=2, the a(3,2)=13 polyominoes spanning a 3 X 2 rectangle are XXX X XX X XX XXX XXX XX XXX XXX plus all different horizontal and vertical reflections (1+2+2+4+4=13). Table begins 1 1 1 1 1 1 1 ... 1 5 13 25 41 61 ... 1 13 68 222 555 ... 1 25 222 1110 ... 1 41 555 ... 1 61 ... 1 ...
Links
- Mireille Bousquet-Mélou, Convex polyominoes and algebraic languages, Journal of Physics A25 (1992), 1935-1944.
- M.-P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration, Theoretical Computer Sci., 34 (1984), 169-206.
- Ira M. Gessel, On the number of convex polyominoes, Ann. Sci. Math. Québec 24 (2000), no. 1, 63-66.
- K. Y. Lin and S. J. Chang, Rigorous results for the number of convex polygons on the square and honeycomb lattices, Journal of Physics A21 (1988), 2635-2642.
Crossrefs
Programs
-
Mathematica
Table[Binomial[2 # + 2 h - 4, 2 # - 2] + ((2 # + 2 h - 5)/2) Binomial[2 # + 2 h - 6, 2 # - 3] - 2 (# + h - 3) Binomial[# + h - 2, # - 1] Binomial[# + h - 4, # - 2] &[w - h + 1], {w, 10}, {h, w}] // Flatten (* Michael De Vlieger, Apr 15 2019 *) -
Sage
def a(w,h): s = w+h # half the perimeter return ( binomial(2*s-4,2*w-2) + binomial(2*s-6,2*w-3)*(s-5/2) - 2*(s-3)*binomial(s-2,w-1)*binomial(s-4,w-2) )
Formula
a(w, h) = binomial(2w+2h-4, 2w-2) + ((2w+2h-5)/2)*binomial(2w+2h-6, 2w-3) - 2(w+h-3)*binomial(w+h-2, w-1)*binomial(w+h-4, w-2), for w > 0, h > 0.
a(w, h) = A093118(w-1, h-1).