A110476 Table of number of partitions of an m X n rectangle, read by descending antidiagonals.

1, 2, 2, 4, 12, 4, 8, 74, 74, 8, 16, 456, 1434, 456, 16, 32, 2810, 27780, 27780, 2810, 32, 64, 17316, 538150, 1691690, 538150, 17316, 64, 128, 106706, 10424872, 103015508, 103015508, 10424872, 106706, 128, 256, 657552, 201947094, 6273056950

Offset

1,2

Comments

We count the partitions of the rectangle into regions of orthogonally connected unit squares. a(2, 2) = 12 comprising one partition of the 2 X 2 region; 4 partitions into a 3-square 'L' shape and an isolated corner; 2 partitions into two 1 X 2 bricks; 4 partitions into a 1 X 2 brick and two isolated squares; and 1 partition into four isolated squares.

Links

Walter Trump, Table of n, a(n) for n = 1..220 (first 40 terms from Hugo van der Sanden).

Brian Kell, Values for m+n < 16 [except (7,7), (7,8) and (8,7)]

A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumeration, Integers, 1 (2001), 1-11. [From Brian Kell, Oct 21 2008]

Yulka Lipkova, Miso Forisek, Tom Zathurecky, and Davidko Pal, Delicious cake. [From Brian Kell, Oct 21 2008]

J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart., 42 (2004), 222-230. [From Brian Kell, Oct 21 2008]

Frank Simon, Algebraic Methods for Computing the Reliability of Networks, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012. - From N. J. A. Sloane, Jan 04 2013

F. Simon, P. Tittmann and M. Trinks, Counting Connected Set Partitions of Graphs, Electron. J. Combin., 18(1) (2010), #P14, 12pp.

Formula

a(m,n) = a(n,m).

a(1,n) = 2^(n-1) = a(n,1).

a(2,n) = A078469(n) = a(n,2).

From Petros Hadjicostas, Feb 27 2021: (Start)

The following two equations seem to follow from the work of Brian Kell and Frank Simon:

a(3,n) = A108808(n) = a(n,3).

a(4,n) = A221157(n) = a(n,4). (End)

Example

Array A(m,n) (with rows m >= 1 and columns n >= 1) begins
    1,      2,        4,         8,        16,       32,     64, 128, ...
    2,     12,       74,       456,      2810,    17316, 106706, ...
    4,     74,     1434,     27780,    538150, 10424872, ...
    8,    456,    27780,   1691690, 103015508, ...
   16,   2810,   538150, 103015508, ...
   32,  17316, 10424872, ...
   64, 106706, ...
  128, ...
  ...

Crossrefs

Cf. A000041, A000079, A078469, A221157.

Cf. A108808, A145835. - Brian Kell, Oct 21 2008

Sequence in context: A219569 A202795 A256890 * A379100 A330762 A059343

Adjacent sequences: A110473 A110474 A110475 * A110477 A110478 A110479

Keyword

nonn,tabl

Author

Hugo van der Sanden, Sep 08 2005

Extensions

Corrected by Chuck Carroll (chuck(AT)chuckcarroll.org), Jun 06 2006

Name edited by Michel Marcus, Jul 02 2020

Status

approved