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

Offset: 1

Author

Pontus von Brömssen, Feb 28 2023

Keywords

• nonn
• tabl
• more

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?

Examples

			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.

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