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.

Ira M. Gessel, On the number of convex polyominoes, Ann. Sci. Math. Québec 24 (2000), no. 1, 63-66.

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