A361000 Number of tilings of an n X 3 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).

2, 3, 2, 4, 3, 5, 3, 6, 4, 6, 3, 9, 3, 6, 6, 8, 3, 9, 3, 10, 6, 6, 3, 13, 5, 6, 6, 10, 3, 13, 3, 10, 6, 6, 7, 15, 3, 6, 6, 14, 3, 13, 3, 10, 10, 6, 3, 17, 5, 10, 6, 10, 3, 13, 7, 14, 6, 6, 3, 21, 3, 6, 10, 12, 7, 13, 3, 10, 6, 14, 3, 21, 3, 6, 10, 10, 7, 13, 3

Offset

1,1

Links

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

Formula

a(n) = 2*A000005(n) - A083039(n) for n >= 3.

Proof: (Start)

Note that a nonrearrangeable tiling must have full symmetry, otherwise it could be rotated or reflected to another tiling.

Identical pieces of size m X 1 tile the n X 3 rectangle in a unique way exactly when m is a divisor of n, except m = 2 and m = 3. Identical pieces of size m X 3 tile the rectangle in a unique way exactly when m is a divisor of n, except m = 1. The only other pieces that fit in the rectangle are of size m X 2, where m = 2 or m >= 4, but it is easily seen that the rectangle cannot be tiled with identical pieces of those sizes, so there are 2*A000005(n) - 1 - [n even] - [n divisible by 3] = 2*A000005(n) - A083039(n) nonrearrangeable tilings of the rectangle with identical pieces.

We now prove that there is no nonrearrangeble tiling of the rectangle that contains pieces of different sizes. Assume that we have such a tiling of the rectangle of height n and width 3, for the smallest possible value of n.

A fault of a tiling is a line through the interior of the rectangle that does not pass through the interior of any piece. If the tiling has any horizontal (or vertical) faults, all the resulting horizontal (or vertical) strips between the faults must have the same size and be tiled in the same way, otherwise the strips could be permuted to another tiling.

If the tiling has any vertical faults, there must be three identically tiled vertical n X 1 strips. This implies that a single strip must contain pieces of different lengths, which is clearly impossible because those pieces could be permuted to another tiling.

If there are no vertical faults, there must be a piece in the tiling with a horizontal side of length at least 2, and by symmetry one of its horizontal edges must be part of a horizontal fault, otherwise another tiling could be obtained by reflection. The resulting strips (of width 3) must all be tiled in the same way (and thus contain pieces of different sizes), and the tiling of one strip must be nonrearrangeble. We have thus obtained a nonrearrangeable tiling with pieces of different sizes for a smaller height, a contradiction.

(End)

Crossrefs

Third column of A360998.

Cf. A000005, A083039, A360632, A361005.

Sequence in context: A157893 A331253 A264116 * A283368 A199474 A246694

Adjacent sequences: A360997 A360998 A360999 * A361001 A361002 A361003

Keyword

nonn

Author

Pontus von Brömssen, Feb 28 2023

Status

approved