A360631 Number of sets of integer-sided rectangular pieces that can tile a 2 X n rectangle.

1, 2, 4, 10, 22, 44, 91, 172, 326, 595, 1066, 1849, 3204, 5365, 8921, 14581, 23558, 37440, 59127, 91957, 142060, 217015, 328939, 493917, 737249, 1090432, 1603439, 2341094, 3398313, 4900740, 7032809, 10031010, 14241165, 20112575, 28276657, 39566635, 55140425, 76499692, 105731884, 145550924

Offset

0,2

Links

Robin Visser, Table of n, a(n) for n = 0..40

Krystian Gajdzica, Robin Visser, and Maciej Zakarczemny, Rectangle partitions generalizing integer partitions, Ann. Comb. (2026). See also arXiv:2509.20495 [math.CO], 2025.

Example

From Robin Visser, May 01 2025: (Start)
For n = 1, there are a(1) = 2 possible sets of rectangular pieces that can tile a 2 x 1 rectangle: one 1 x 2 piece; or two 1 x 1 pieces.
For n = 2, there are a(2) = 4 possible sets of rectangular pieces that can tile a 2 x 2 rectangle: one 2 x 2 piece; two 1 x 2 pieces; one 1 x 2 piece and two 1 x 1 pieces; or four 1 x 1 pieces.
For n = 3, there are a(3) = 10 possible sets of rectangular pieces that can tile a 2 x 3 rectangle: one 2 x 3 piece; one 2 x 2 piece and one 1 x 2 piece; one 2 x 2 piece and two 1 x 1 pieces; two 1 x 3 pieces; one 1 x 3 piece, one 1 x 2 piece, and one 1 x 1 piece; one 1 x 3 piece and three 1 x 1 pieces; three 1 x 2 pieces; two 1 x 2 pieces and two 1 x 1 pieces; one 1 x 2 piece and four 1 x 1 pieces; or six 1 x 1 pieces. (End)

Prog

(Python)
def a(n):
    A, B = [set() for i in range(n+1)], [set() for i in range(n+1)]
    A[0].add(()); B[0].add(());
    for (m, k) in [(x, y) for x in range(1, n+1) for y in range(1, x+1)]:
        for p in A[m-k]: A[m].add(tuple(sorted(list(p)+[k])))
        for (p, q) in [(x, y) for x in A[m] for y in A[m]]:
            B[m].add(tuple(sorted([(1, c) for c in p]+[(1, c) for c in q])))
        for p in B[m-k]: B[m].add(tuple(sorted(list(p)+[tuple(sorted((2, k)))])))
    return len(B[n])  # Robin Visser, May 01 2025

Crossrefs

Second column of A360629.

Cf. A000041 (1 x n rectangle), A360632 (3 x n rectangle).

Sequence in context: A263661 A005306 A075898 * A337654 A369491 A274313

Adjacent sequences: A360628 A360629 A360630 * A360632 A360633 A360634

Keyword

nonn

Author

Pontus von Brömssen, Feb 14 2023

Extensions

More terms from Robin Visser, May 04 2025

a(0) = 1 prepended by Robin Visser, May 05 2025

Status

approved