login
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, ...
2
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
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
Cf. A000041, A116694, A224697, A360629 (pieces are free to rotate by 90 degrees).
Sequence in context: A081469 A331441 A209664 * A072647 A100113 A300012
KEYWORD
nonn,tabl,more
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