OFFSET
1,2
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.
FORMULA
T(n,1) = A000041(n), the partition numbers.
EXAMPLE
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 ? ?
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".
PROG
(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)}
CROSSREFS
KEYWORD
AUTHOR
M. F. Hasler, Feb 09 2023
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
STATUS
approved