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

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

Author

M. F. Hasler, Feb 09 2023

Keywords

• nonn
• tabl
• more

Comments

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.

Examples

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

Crossrefs

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

Programs

PARI

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

Formula

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

Extensions

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