A093118 Triangle T read by rows: T(m,n) = number of convex polyominoes with an m+1 X n+1 minimal bounding rectangle, m > 0, n <= m.

5, 13, 68, 25, 222, 1110, 41, 555, 3951, 19010, 61, 1171, 11263, 70438, 329126, 85, 2198, 27468, 216618, 1245986, 5693968, 113, 3788, 59676, 579330, 4022546, 21832492, 98074332, 145, 6117, 118605, 1389927, 11462495, 72887139, 379145115, 1680306750

Offset

1,1

Links

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened).

Mireille Bousquet-Mélou, Convex polyominoes and algebraic languages, Journal of Physics A25 (1992), 1935-1944.

Kevin Buchin, Man-Kwun Chiu, Stefan Felsner, Günter Rote, and André Schulz, The Number of Convex Polyominoes with Given Height and Width, arXiv:1903.01095 [math.CO], 2019.

Ira Gessel, On the number of convex polyominoes, Annales des Sciences Mathématiques du Québec, 24 (2000), 63-66.

V. J. W. Guo and J. Zeng, The number of convex polyominoes and the generating function of Jacobi polynomials, arXiv:math/0403262 [math.CO], 2004.

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

T(m,n) = ((m+n+m*n)*C(2*m+2*n, 2*m) - 2*m*n*C(m+n, m)^2)/(m+n), for m + n > 0.

T(m,n) = C(2*m+2*n,2*m) + ((2*m+2*n-1)/2)*C(2*m+2*n-2,2*m-1) - 2*(m+n-1) *C(m+n,m)*C(m+n-2,m-1), for m >= 0, n >= 0. - Günter Rote, Feb 12 2019

Example

Triangle begins:
   5,
  13,   68,
  25,  222,  1110,
  41,  555,  3951,  19010,
  61, 1171, 11263,  70438,  329126,
  85, 2198, 27468, 216618, 1245986, 5693968,
  ...
This is the lower half of an infinite square table that is symmetric at the main diagonal (T(m,n)=T(n,m)).
From Günter Rote, Feb 12 2019: (Start)
For m=2 and n=1, the T(2,1)=13 polyominoes in a 3 X 2 rectangle are the five polyominoes
.
  +---+---+---+       +---+       +---+---+
  |   |   |   |       |   |       |   |   |
  +---+---+---+   +---+---+---+   +---+---+---+
  |   |   |   |   |   |   |   |       |   |   |
  +---+---+---+   +---+---+---+       +---+---+
.
          +---+           +---+---+
          |   |           |   |   |
          +---+---+---+   +---+---+---+
          |   |   |   |   |   |   |   |
          +---+---+---+   +---+---+---+
.
  plus all their different horizontal and vertical reflections (1 + 2 + 2 + 4 + 4 = 13 polyominoes in total). (End)

Maple

T:= (m, n)-> (m+n+m*n)/(m+n)*binomial(2*m+2*n, 2*m)
             -2*m*n/(m+n)*binomial(m+n, m)^2:
seq(lprint(seq(T(m, n), n=1..m)), m=1..10);  # Alois P. Heinz, Feb 24 2019

Mathematica

T[m_, n_] := (m+n+m n)/(m+n) Binomial[2m + 2n, 2m] - 2 m n/(m+n) Binomial[ m+n, m]^2;
Table[T[m, n], {m, 1, 8}, {n, 1, m}] // Flatten (* Jean-François Alcover, Aug 17 2018 *)

Prog

(Sage)
def T(m, n):
         w, h = m+1, n+1 # width and height
         p = w+h         # half the perimeter
         return ( binomial(2*p-4, 2*w-2) + binomial(2*p-6, 2*w-3)*(p-5/2) - 2*(p-3)*binomial(p-2, w-1)*binomial(p-4, w-2) )  # Günter Rote, Feb 13 2019
(PARI) {T(n, k) = ((n+k+n*k)*binomial(2*n+2*k, 2*n) - 2*n*k*binomial(n+k, n)^2)/(n+k)};
for(n=1, 8, for(k=1, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Feb 18 2019
(Magma) [[((n+k+n*k)*Binomial(2*n+2*k, 2*n) - 2*n*k*Binomial(n+k, n)^2)/(n+k): k in [1..n]]: n in [1..8]]; // G. C. Greubel, Feb 18 2019

Crossrefs

Columns T(m, 1) = A001844(m), T(m, 2) = A093119(m). Diagonal T(n, n) = A093120(n).

Sums of T(m,n) with fixed sum m+n (including entries with n > m and the trivial ones: T(0,x)=T(y,0)=1), are A005436. - Günter Rote, Feb 12 2019

Sequence in context: A149575 A156101 A372799 * A359690 A087506 A068487

Adjacent sequences: A093115 A093116 A093117 * A093119 A093120 A093121

Keyword

nonn,tabl,easy,walk

Author

Ralf Stephan, Mar 21 2004

Status

approved