login
A222659
Table a(m,n) read by antidiagonals, m, n >= 1, where a(m,n) is the number of divide-and-conquer partitions of an m X n rectangle into integer sub-rectangles.
0
1, 2, 2, 4, 8, 4, 8, 34, 34, 8, 16, 148, 320, 148, 16, 32, 650, 3118, 3118, 650, 32, 64, 2864, 30752, 68480, 30752, 2864, 64, 128, 12634, 304618, 1525558, 1525558, 304618, 12634, 128
OFFSET
1,2
COMMENTS
The divide-and-conquer partition of an integer-sided rectangle is one that can be obtained by repeated bisections into adjacent integer-sided rectangles.
The table is symmetric: a(m,n) = a(n,m).
EXAMPLE
Table begins:
1, 2, 4, 8, 16, 32, 64, ...
2, 8, 34, 148, 650, 2864, 12634, ...
4, 34, 320, 3118, 30752, 304618, 3022112, ...
8, 148, 3118, 68480, 1525558, ...
16, 650, 30752, 1525558, ...
32, 2864, 304618, ...
64, 12634, 3022112, ...
Not every partition (cf. A116694) into integer sub-rectangles is divide-and-conquer. For example, the following partition of a 3 X 3 rectangle into 5 sub-rectangles is not divide-and-conquer:
112
342
355
CROSSREFS
a(1,n) = a(n,1) = A000079(n-1)
a(2,n) = a(n,2) = A034999(n)
Cf. A116694 (all partitions).
Sequence in context: A317517 A300182 A317532 * A116694 A220810 A221024
KEYWORD
tabl,nonn,more
AUTHOR
Arsenii Abdrafikov, May 29 2013
STATUS
approved