A359019 Number of inequivalent tilings of a 3 X n rectangle using integer-sided square tiles.

1, 1, 2, 3, 6, 10, 21, 39, 82, 163, 347, 717, 1533, 3232, 6927, 14748, 31645, 67690, 145322, 311535, 668997, 1435645, 3083301, 6619842, 14218066, 30533005, 65580338, 140847132, 302522253, 649759735, 1395611508, 2997573501, 6438470626, 13829057884, 29703388721, 63799607283, 137035047576, 294336860797, 632205714741

Offset

0,3

Comments

If only symmetries of the rectangle are considered then a(3) is still 3. - Andrew Howroyd, Nov 16 2025

Links

John Mason, Table of n, a(n) for n = 0..1000

John Mason, Counting free tilings of a rectangle

Index entries for linear recurrences with constant coefficients, signature (1,3,0,0,-3,-3,-3,-2,-1).

Formula

For n <= 1, a(n)=1;

otherwise for odd n > 1, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 1) / 2) + 2 * A002478((n - 3) / 2)) / 4;

and for even n, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 2) / 2) + 2 * A002478(n / 2)) / 4.

Alternatively, from Walter Trump:

For n <= 1, a(n)=1;

otherwise for odd n > 1, a(n)=(A000930(2n) + A000930(n) + 2 * A000930(n - 1) + 2 * A000930(n - 3)) / 4;

and for even n, a(n)=(A000930(2n) + 2 * A000930(n - 2) + 3 * A000930(n)) / 4.

G.f.: (1 - 2*x^2 - 2*x^3 - 3*x^4 - 2*x^5 - x^6)/((1 - x - x^3)*(1 + x + x^3)*(1 - x - 2*x^2 - x^3)). - Andrew Howroyd, Nov 16 2025

Example

a(4) is 6 because of:
  +-+-+-+  +-+-+-+  +-+-+-+  +-+-+-+  +-+-+-+  +-+-+-+
  | | | |  |     |  |   | |  |   | |  |   | |  | | | |
  +-+-+-+  +     +  +   +-+  +   +-+  +   +-+  +-+-+-+
  | | | |  |     |  |   | |  |   | |  |   | |  |   | |
  +-+-+-+  +     +  +-+-+-+  +-+-+-+  +-+-+-+  +   +-+
  | | | |  |     |  |   | |  | |   |  | | | |  |   | |
  +-+-+-+  +-+-+-+  +   +-+  +-+   +  +-+-+-+  +-+-+-+
  | | | |  | | | |  |   | |  | |   |  | | | |  | | | |
  +-+-+-+  +-+-+-+  +-+-+-+  +-+-+-+  +-+-+-+  +-+-+-+

Prog

(PARI) Vec((1-2*x^2-2*x^3-3*x^4-2*x^5-x^6)/((1-x-x^3)*(1+x+x^3)*(1-x-2*x^2-x^3))+O(x^99)) \\ Charles R Greathouse IV, May 13 2026

Crossrefs

Column k = 3 of A227690.

Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:

Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.

Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

Cf. A000930.

Sequence in context: A324407 A032291 A063687 * A002988 A138347 A211180

Adjacent sequences: A359016 A359017 A359018 * A359020 A359021 A359022

Keyword

nonn,easy

Author

John Mason, Dec 12 2022

Status

approved