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,3

Links

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

John Mason, Counting free tilings of a rectangle

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.

Example

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

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.

Sequence in context: A105205 A302311 A160805 * A246424 A012776 A240198

Adjacent sequences: A359017 A359018 A359019 * A359021 A359022 A359023

Keyword

nonn

Author

John Mason, Dec 12 2022

Status

approved