login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,1

LINKS

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

Kevin Buchin, Man-Kwun Chiu, Stefan Felsner, Günter Rote, 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.

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: A018678 A149575 A156101 * A087506 A068487 A075063

Adjacent sequences:  A093115 A093116 A093117 * A093119 A093120 A093121

KEYWORD

nonn,tabl,easy,walk

AUTHOR

Ralf Stephan, Mar 21 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 13 05:16 EDT 2021. Contains 344981 sequences. (Running on oeis4.)