A359020 Number of inequivalent tilings of a 4 X n rectangle using integer-sided square tiles.

1, 1, 4, 6, 13, 39, 115, 295, 861, 2403, 7048, 20377, 60008, 175978, 519589, 1532455, 4531277, 13395656, 39639758, 117301153, 347248981, 1028011708, 3043852214, 9012879842, 26689014028, 79033362580, 234045889421, 693101137571, 2052569508948

Offset: 0

Author

John Mason, Dec 12 2022

Keywords

• nonn

Examples

			a(3) 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 = 4 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.

Formula

For even n > 4

a(n) = (A054856(n) + compo(n) + 4 * A054856((n - 2) / 2) +

2 * A054856((n - 4) / 2) + 2 * A054856(n / 2) +

2 * Sum_{k=0..(n - 2) / 2} (A054856(k))) / 4

For odd n > 4

a(n) = (A054856(n) + compo(n) + 2 * A054856((n - 3) / 2) +

2 * A054856((n - 1) / 2) + 2 * Sum_ {k=0..(n - 3) / 2} (A054856(k))) / 4

Where compo(n) is the number of distinct compositions of n as a sum of 1, 2, (1+1) and 4.