A360998 - OEIS

A360998

Triangle read by rows: T(n,k) is the number of tilings of an n X k rectangle by integer-sided rectangular pieces that cannot be rearranged to produce a different tiling of the rectangle (including rotations and reflections of the original tiling), 1 <= k <= n.

1, 2, 2, 2, 3, 2, 3, 4, 4, 3, 2, 3, 3, 4, 2, 4, 6, 5, 7, 5, 4

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

It seems that each solution consists of n*k/(r*s) copies of an r X s piece (arranged in a simple grid, all pieces oriented in the same way), where r is a divisor of n, s is a divisor of k, and either r = s or r is not a divisor of k or s is not a divisor of n. If this is true, T(n,k) <= d(n)*d(k) - d(m)*(d(m)-1), where d = A000005 is the divisor count function and m = gcd(n,k). Equality does not always hold; for (n,k) = (3,2), for example, (r,s) = (1,2) satisfies the condition, but three 1 X 2 pieces can tile the 3 X 2 rectangle in more than one way.

Is d(n)*d(k) - T(n,k) eventually periodic in n for each k?

LINKS

Table of n, a(n) for n=1..21.

FORMULA

T(n,1) = d(n) = A000005(n).

T(n,2) = A360999(n) = 2*d(n) - 1 - [n even] for n >= 2.

T(n,3) = A361000(n) = 2*d(n) - A083039(n) for n >= 3.

It appears that T(n,4) = 3*d(n) - 2 - 2*[n even] - [n divisible by 3] - 2*[n divisible by 4] for n >= 4.

It appears that T(n,n) = d(n). (It is easy to see that T(n,n) >= d(n).)

EXAMPLE

Triangle begins:

n\k| 1 2 3 4 5 6

---+------------------

1 | 1

2 | 2 2

3 | 2 3 2

4 | 3 4 4 3

5 | 2 3 3 4 2

6 | 4 6 5 7 5 4

The T(4,3) = 4 nonrearrangeable tilings of the 4 X 3 rectangle are:

+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+

| | | | | | | | | | | |

+ + + + + + + + +---+---+---+

| | | | | | | | | | | |

+ + +---+---+---+ + + + + +---+---+---+

| | | | | | | | | | | |

+ + + + + + + + +---+---+---+

| | | | | | | | | | | |

+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+

CROSSREFS

Columns: A000005 (k = 1), A360999 (k = 2), A361000 (k = 3).

Cf. A083039, A360629, A361001.

Sequence in context: A348369 A068324 A167505 * A165015 A178994 A306608

Adjacent sequences: A360995 A360996 A360997 * A360999 A361000 A361001

KEYWORD

nonn,tabl,more

AUTHOR

Pontus von Brömssen, Feb 28 2023

STATUS

approved