A359886 Number of 3-dimensional tilings of a 2 X 2 X n box using 2 X 2 X 1 plates and trominos (three 1 X 1 X 1 cubes).

1, 1, 3, 49, 231, 789, 4771, 27225, 122799, 607469, 3255979, 16253649, 80098519, 409480005, 2079921395, 10411734921, 52523676351, 266059774429, 1341128940795, 6758479842689, 34138205819239, 172324729379509, 869131661400259, 4386075013348025, 22138673661637327

Offset: 0

Author

Gerhard Kirchner, Jan 20 2023

Keywords

• nonn
• easy

Comments

Recurrence 1 is derived in A359884, "3d-tilings of a 2 X 2 X n box" as a special case of a more general tiling problem: III, example 6.

Examples

			a(3) = 49.
The number of tilings only using plates is A001045(3) = 5.
The number of tilings only using trominos is A359885(1) = 44.
These terms are to be added as, for n=3, there is no tiling using both tiles.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000
• Gerhard Kirchner, Maxima code
• Index entries for linear recurrences with constant coefficients, signature (2,1,58,72,32,-128).

Crossrefs

Cf. A006253, A001045, A335559, A359884, A359885.

Programs

Mathematica

LinearRecurrence[{2, 1, 58, 72, 32, -128}, {1, 1, 3, 49, 231, 789}, 30] (* Paolo Xausa, Jun 24 2024 *)

Maxima

/* See link "Maxima code". */

Formula

G.f.: (1 - x - 16*x^3) / (1 - 2*x - x^2 - 58*x^3 - 72*x^4 - 32*x^5 + 128*x^6).

Recurrence 1:

a(n) = a(n-1) + 3*c(n-2) + 2*a(n-2) + 4*c(n-3) + 8*a(n-3),

c(n) = 12*a(n-1) + c(n-1) + 16*a(n-2) + 16*c(n-3),

with a(n),c(n) <= 0 for n <= 0 except for a(0)=1.

Recurrence 2:

a(n) = 2*a(n-1) + a(n-2) + 58*a(n-3) + 72*a(n-4) + 32*a(n-5) - 128*a(n-6) for n >= 6.

For n < 6, recurrence 1 can be used.