A116694 -id:A116694 - cp's OEIS frontend

A220300 Number of ways to cut a 7 X n rectangle into rectangles with integer sides.

1, 64, 12634, 3149674, 846280548, 233276449488, 64878517290010, 18100579400986674, 5055501014135301068, 1412555471061355121760, 394736020870056624585954, 110313635920498690779144346, 30828978488622550052903902112, 8615722882208603126215501978476

Offset: 0

Alois P. Heinz, Dec 10 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
Alois P. Heinz, G.f. and Maple program for A220300
David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

Column m=7 of A116694.

Maple
```
# see link above.
```

G.f.: see link above.

A220301 Number of ways to cut an 8 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 128, 55756, 31544384, 19415751782, 12300505521832, 7871769490695758, 5055501014135301068, 3250879178100782348462, 2091366508168264152856116, 1345636228678678520218159342, 865863320865232237151806089380, 557159535051149816106032278432958

Offset: 0

Alois P. Heinz, Dec 10 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100
David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

Column m=8 of A116694.

A220302 Number of ways to cut a 9 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 256, 246098, 315981452, 445550465628, 648782777031100, 955411617212520670, 1412555471061355121760, 2091366508168264152856116, 3097923464622249063718465240, 4589736231595259523509695756270, 6800359836887612382212923755420792

Offset: 0

Alois P. Heinz, Dec 10 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100
David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

Column m=9 of A116694.

A361523 Triangle read by rows: T(n,k) is the number of ways of dividing an n X k rectangle into integer-sided rectangles, up to rotations and reflections.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 1, 3, 17, 54, 1, 6, 61, 892, 9235, 1, 10, 220, 8159, 406653, 10538496

Offset: 0

Pontus von Brömssen, Mar 15 2023

			Triangle begins:
  n\k| 0  1   2    3      4        5
  ---+------------------------------
  0  | 1
  1  | 1  1
  2  | 1  2   4
  3  | 1  3  17   54
  4  | 1  6  61  892   9235
  5  | 1 10 220 8159 406653 10538496
The 3 X 2 rectangle can be divided in T(3,2) = 17 inequivalent ways:
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
  |       |   |       |   |   |   |   |   |   |   |   |   |   |   |   |
  +       +   +---+---+   +---+---+   +   +   +   +   +---+   +   +---+
  |       |   |       |   |       |   |   |   |   |   |   |   |   |   |
  +       +   +       +   +       +   +   +   +   +   +   +   +   +---+
  |       |   |       |   |       |   |   |   |   |   |   |   |   |   |
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
.
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
  |       |   |   |   |   |   |   |   |   |   |   |       |   |   |   |
  +---+---+   +   +   +   +---+---+   +   +---+   +---+---+   +---+---+
  |       |   |   |   |   |       |   |   |   |   |   |   |   |   |   |
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +   +   +
  |       |   |       |   |       |   |       |   |       |   |   |   |
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
.
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
  |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  +---+   +   +---+---+   +---+---+   +---+---+   +---+---+
  |   |   |   |   |   |   |   |   |   |       |   |   |   |
  +   +---+   +---+---+   +   +---+   +---+---+   +---+---+
  |   |   |   |       |   |   |   |   |   |   |   |   |   |
  +---+---+   +---+---+   +---+---+   +---+---+   +---+---+

Main diagonal: A361524.
Columns: A000012 (k = 0), A005418 (k = 1), A347825 (k = 2; with an exception for n = 2), A361525 (k = 3), A361526 (k = 4).
Cf. A116694 (rotations and reflections are considered distinct), A227690 (square pieces), A360629.

T(n,k) >= A116694(n,k)/4 if n != k.

T(n,n) >= A116694(n,n)/8.

A220303 Number of ways to cut a 10 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 512, 1086296, 3165414034, 10225294476962, 34223109012944482, 115973945786899746170, 394736020870056624585954, 1345636228678678520218159342, 4589736231595259523509695756270, 15657867573050419014814618149422562, 53420457933273164607876918293027444742

Offset: 0

Alois P. Heinz, Dec 10 2012

nonn

David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

Column m=10 of A116694.

A333495 Number of ways of dividing a 2n X n rectangle into integer-sided rectangles.

Original entry on oeis.org

1, 2, 148, 314662, 19415751782, 34223109012944482, 1709004742525016740261850, 2407826816243421894252785348151226, 95524923938130486476975763614521056527129262, 106619635380815059627115813538573777241948002538356771858, 3346744054257695722669927876858961813239867346217968957293126431564898

Offset: 0

Alois P. Heinz, Mar 24 2020

nonn

David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

Cf. A116694, A333476.

a(n) = A116694(2n,n) = A333476(2n,n).

A360451 Triangle read by rows: T(n,k) = number of partitions of an n X k rectangle into one or more integer-sided rectangles, 1 <= k <= n = 1, 2, 3, ...

Original entry on oeis.org

1, 2, 6, 3, 14, 50, 5, 34, 179, 892, 7, 72, 548, 3765, 21225, 11, 157, 1651, 14961, 108798, 700212, 15, 311, 4485, 53196, 491235, 3903733

Offset: 1

M. F. Hasler, Feb 09 2023

Partitions are considered as ordered lists or multisets of rectangles or pairs (height, width). They are not counted with multiplicity in case there are different "arrangements" of the rectangles yielding the same "big" rectangle.

For example, for (n,k) = (3,1) (rectangle of height 3 and width 1) we have the A000041(3) = 3 partitions [(3,1)] and [(2,1), (1,1)] (2 X 1 rectangle above a 1 X 1 square) and [(1,1), (1,1), (1,1)]. The partition [(1,1), (2,1)] (1 X 1 square above the 2 X 1 rectangle) does not count as distinct.

			Triangle begins:
  n\k|  1   2    3     4      5       6  7
  ---+------------------------------------
  1  |  1
  2  |  2   6
  3  |  3  14   50
  4  |  5  34  179   892
  5  |  7  72  548  3765  21225
  6  | 11 157 1651 14961 108798  700212
  7  | 15 311 4485 53196 491235 3903733  ?
For n = k = 2, we have the following six partitions of the 2 X 2 square:
  { [ (2,2) ], [ (2,1), (2,1) ], [ (2,1), (1,1), (1,1) ], [ (1,2), (1,2) ],
    [ (1,2), (1,1), (1,1) ], [ (1,1), (1,1), (1,1), (1,1) ] }.
They can be represented graphically as follows:
     AA   AB   AB   AA   AA   AB
     AA   AB   AC   BB   BC   CD
where in each figure a given letter corresponds to a given rectangular part.
For n = 3, k = 2, we have the fourteen partitions { [(3,2)], [(3,1), (3,1)],
  [(3,1), (2,1), (1,1)], [(3,1), (1,1), (1,1), (1,1)], [(2,2), (1,2)],
  [(2,2), (1,1), (1,1)], [(2,1), (2,1), (1,2)], [(2,1), (2,1), (1,1), (1,1)],
  [(2,1), (1,2), (1,1), (1,1)], [(2,1), (1,1), (1,1), (1,1), (1,1)],
  [(1,2), (1,2), (1,2)], [(1,2), (1,1), (1,1), (1,1), (1,1)],
  [(1,2), (1,2), (1,1), (1,1)], [(1,1), (1,1), (1,1), (1,1), (1,1), (1,1)] },
        AA   AB   AB   AB   AA   AA   AB   AB   AC   AC   AA   AA   AA   AB
  i.e.: AA   AB   AB   AC   AA   AA   AB   AB   AD   AD   BB   BB   BC   CD .
        AA   AB   AC   AD   BB   BC   CC   CD   BB   BE   CC   CD   DE   EF
For n = k = 3, we have 50 distinct partitions. Only one of them, namely
                                                          AAB
  [(2,1), (2,1), (1,2), (1,2), (1,1)]  corresponding to:  DEB
                                                          DCC
  cannot be obtained by repeatedly slicing the full square, and subsequently the resulting smaller rectangles, in two rectangular parts at each step.
  Note that the arrangement: ABC
                             ABD  which also cannot be obtained in that way,
  ABD                        AED  corresponds to the equivalent partition:
  ABD , i.e., the multiset [(3,1), (2,1), (2,1), (1,1), (1,1)],
  AEC   which can be obtained by subsequent "slicing in two rectangles".

Cf. A000041, A116694, A224697, A360629 (pieces are free to rotate by 90 degrees).

A360451(n,k) = if(min(n,k)<3 || n+k<7, #Part(k,n), error("Not yet implemented"))
PartM = Map(); ROT(S) = if(type(S)=="t_INT", [1,10]*divrem(S,10), apply(ROT, S))
Part(a,b) = { if ( mapisdefined(PartM, [a,b]), mapget(PartM, [a,b]),
  a == 1, [[10+x | x <- P ] | P <- partitions(b) ],
  b == 1, [[x*10+1 | x <- P ] | P <- partitions(a) ],
  a > b, ROT(Part(b,a)),  my(S = [[a*10+b]],
    U(x,y,a,b, S, B = Part(x,y)) = foreach(Part(a,b), P,
      foreach(B, Q, S = setunion([vecsort(concat(P,Q))], S) )); S);
  for(x=1,a\2, S = U(x,b, a-x,b, S)); for(x=1,b\2, S = U(a,x, a,b-x, S));
  a==3 && S=setunion(S, [[11,12,12,21,21]]);
  mapput(PartM, [a,b], S); S)}

T(n,1) = A000041(n), the partition numbers.

T(3,3) corrected following a remark by Pontus von Brömssen. - M. F. Hasler, Feb 10 2023
Last two terms of 4th row, 5th row, and first five terms of 6th row from Pontus von Brömssen, Feb 11 2023
Last term of 6th row from Pontus von Brömssen, Feb 13 2023
First five terms of 7th row from Pontus von Brömssen, Feb 16 2023
T(7,6) added by Robin Visser, May 09 2025

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

Original entry on oeis.org

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

R. J. Mathar, Nov 27 2015

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

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

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

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

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

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

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

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

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.

Original entry on oeis.org

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

Arsenii Abdrafikov, May 29 2013

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

			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

a(1,n) = a(n,1) = A000079(n-1)
a(2,n) = a(n,2) = A034999(n)
Cf. A116694 (all partitions).

cp's OEIS Frontend

A220300 Number of ways to cut a 7 X n rectangle into rectangles with integer sides.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A220301 Number of ways to cut an 8 X n rectangle into rectangles with integer sides.

Views

Author

Keywords

Links

Crossrefs

A220302 Number of ways to cut a 9 X n rectangle into rectangles with integer sides.

Views

Author

Keywords

Links

Crossrefs

A361523 Triangle read by rows: T(n,k) is the number of ways of dividing an n X k rectangle into integer-sided rectangles, up to rotations and reflections.

Views

Author

Keywords

Examples

Crossrefs

Formula

A220303 Number of ways to cut a 10 X n rectangle into rectangles with integer sides.

Views

Author

Keywords

Links

Crossrefs

A333495 Number of ways of dividing a 2n X n rectangle into integer-sided rectangles.

Views

Author

Keywords

Links

Crossrefs

Formula

A360451 Triangle read by rows: T(n,k) = number of partitions of an n X k rectangle into one or more integer-sided rectangles, 1 <= k <= n = 1, 2, 3, ...

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs