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.

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

Links

Table of n, a(n) for n=1..36.

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

Adjacent sequences: A222656 A222657 A222658 * A222660 A222661 A222662

Keyword

tabl,nonn,more

Author

Arsenii Abdrafikov, May 29 2013

Status

approved