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

Author

John Mason, Dec 12 2022

Keywords

• nonn

Examples

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

Links

• John Mason, Table of n, a(n) for n = 0..1000
• John Mason, Counting free tilings of a rectangle

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.

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