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

Author

Hugo van der Sanden, Sep 08 2005

Keywords

• nonn
• tabl

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.

Examples

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

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.

Crossrefs

Cf. A000041, A000079, A078469, A221157.

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

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)

Extensions

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

Name edited by Michel Marcus, Jul 02 2020