login
A110476
Table of number of partitions of an m X n rectangle, read by descending antidiagonals.
4
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. A108808, A145835. - Brian Kell, Oct 21 2008
Sequence in context: A219569 A202795 A256890 * A330762 A059343 A285944
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