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

Links

Table of n, a(n) for n=1..55.

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.

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).

Example

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

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 *)

Prog

(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) )

Crossrefs

A093118 contains the same data in a different arrangement but without the entries for w=1 and for h=1.

Row sums are A005436.

Sequence in context: A300035 A130227 A114123 * A143007 A152654 A176487

Adjacent sequences: A324006 A324007 A324008 * A324010 A324011 A324012

Keyword

nonn,easy,tabl,walk

Author

Günter Rote, Feb 12 2019

Status

approved