A264872 Array read by antidiagonals: T(n,m) = 2^n*(1+2^n)^m; n,m >= 0.

1, 2, 2, 4, 6, 4, 8, 18, 20, 8, 16, 54, 100, 72, 16, 32, 162, 500, 648, 272, 32, 64, 486, 2500, 5832, 4624, 1056, 64, 128, 1458, 12500, 52488, 78608, 34848, 4160, 128, 256, 4374, 62500, 472392, 1336336, 1149984, 270400, 16512, 256, 512, 13122, 312500

Offset: 0

Author

R. J. Mathar, Nov 27 2015

Keywords

• nonn
• tabl
• easy

Comments

Start with an n X m rectangle and cut it vertically along any set of the m-1 separators. There are binomial(m-1,c) ways of doing this with 0 <= c < m cuts. Inside each of these 1+c regions cut vertically, for which there are 2^(n-1) choices. The total number of ways of dissecting the rectangle into rectangles in this way is Sum_{c=0..m-1} binomial(m-1,c) 2^((1+c)(n-1)) = 2^(n-1)*(1+2^(n-1))^(m-1) = T(n-1,m-1).

The symmetrized version of the array is S(n,m) = T(n,m) + T(m,n) - 2^(m+n) <= A116694(n,m), which counts tilings that start with guillotine cuts either horizontally or vertically, avoiding double counting of the tilings where the order of the cuts does not matter. - R. J. Mathar, Nov 29 2015

Examples

			   1,    2,     4,       8,       16,         32, ...
   2,    6,    18,      54,      162,        486, ...
   4,   20,   100,     500,     2500,      12500, ...
   8,   72,   648,    5832,    52488,     472392, ...
  16,  272,  4624,   78608,  1336336,   22717712, ...
  32, 1056, 34848, 1149984, 37949472, 1252332576, ...
.
The symmetrized version S(n,m) starts
   1,    2,     4,       8,       16,         32, ...
   2,    8,    30,     110,      402,       1478, ...
   4,   30,   184,    1116,     7060,      47220, ...
   8,  110,  1116,   11600,   130968,    1622120, ...
  16,  402,  7060,  130968,  2672416,   60666672, ...
  32, 1478, 47220, 1622120, 60666672, 2504664128, ...
		

Links

• R. J. Mathar, Counting 2-way monotonic terrace forms over rectangular landscapes, vixra:1511.0225 (2015), Section 6.

Crossrefs

Cf. A000079 (row and column 0), A008776 (row 1), A005054 (row 2), A055275 (row 3), A063376 (column 1).

Programs

Maple

A264872 := proc(n,m)
    2^n*(1+2^n)^m ;
end proc:
seq(seq(A264872(n,d-n),n=0..d),d=0..12) ; # R. J. Mathar, Aug 14 2024

Mathematica

Table[2^(n - m) (1 + 2^(n - m))^m, {n, 9}, {m, 0, n}] // Flatten (* Michael De Vlieger, Nov 27 2015 *)

Formula

T(n,m) = 2^n*A264871(n,m).

T(n,m) <= A116694(n+1,m+1).