cp's OEIS Frontend

Tilings that are rotations or reflections of each other are considered distinct.

Pieces can have any combination of integer side lengths, but for the optimal sets computed so far (up to (n,k) = (7,5)), all pieces have one side of length 1.

The (n,k)-tiling difficulty level of a set of integer-sided rectangular pieces is defined as follows. Pieces are free to rotate, so an s X t piece and a t X s piece are equivalent. Consider a random permutation of the pieces together with a random choice of orientation of each nonsquare piece. Take one piece at a time, in the chosen order and with the chosen orientation, and try to put it with its lower left corner in the leftmost free cell in the lowest currently incomplete row of the n X k rectangle. The (n,k)-tiling difficulty level of the set of pieces is the inverse of the probability that this process results in a complete tiling of the n X k rectangle. It equals C(m; m_1, ..., m_j)*2^r/x, where m_1, ..., m_j are the number of pieces of different shapes, m is the total number of pieces, C(m; m_1, ..., m_j) is the multinomial coefficient, r is the number of nonsquare pieces, and x is the number of ways in which an n X k rectangle can be tiled with the set of pieces (where rotations and reflections are considered distinct).

The minimum possible difficulty level is 1, for example for tiling the n X k rectangle with 1 X 1 pieces only.

The difficulty level as defined here is a very crude measure of the perceived difficulty of a tiling puzzle. For example, it does not take into consideration whether a certain piece can fit in the rectangle in only one orientation. This means that the "puzzle" to put a 2 X 1 piece in a 2 X 1 rectangle, for example, has difficulty level 2, the "difficulty" being to orient the piece in the right way.

The only rectangle sizes, currently known to the author, for which the maximum difficulty level is not an integer, are 7 X 2 (difficulty level 160/3) and 13 X 2 (difficulty level 8960/3).

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?

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.