A360645 Number of 4-dimensional tilings of a 2 X 2 X 2 X n box with 2 X 2 X 1 X 1 plates.

1, 3, 30, 177, 1281, 8520, 58629, 397887, 2715510, 18490533, 126023349, 858595560, 5850498441, 39863005323, 271617783150, 1850725023657, 12610357769721, 85923544106760, 585460036653789, 3989166905015367, 27181111280961990, 185204779320272253

Offset: 0

Author

Gerhard Kirchner, Feb 15 2023

Keywords

• nonn

Comments

The figure shows three 2 X 2 X 2 cubes as intersections of three successive hyperplanes (distance 1) with the box. The 3-d cross-section of a 2 X 2 X 1 X 1 plate is a 2 X 2 X 1 plate (p4) as part of one cube or a 2 X 1 X 1 domino if the plate (p2) connects two cubes. p4 or p2 indicates the number of unit cubes on the current level (hyperplane). PQRS and P'Q'R'S' (not visible: P') is one of three ways to select a pair of p4-plates. Q'Q"R"S' represents a p2-plate.

Suppose the box is completely tiled up to a certain level. Then the next (current) level may be empty (profile A0) or not (profile B0). The index 0 is used for the current level and continued with 1,2... Transitions:

a) A0->3*A1 (3 ways of selecting a pair of p4-plates, also A001045(2)=3).

b) A0->9*A2 (9 ways of tiling a 2 X 2 X 2 cube with 3d-dominos, also A006253(2)=9).

c) A0->12*B1. One p4-plate and two p2-plates can be selected in 12 ways: 6 faces of the 2 X 2 X 2 cube and two ways of selecting a pair of dominos on each face. They tile the next level with corresponding dominos. A further nonempty profile does not occur. Also, A359884(2)-A006253(2)-A001045(2)=24-9-3=12.

d) B0->1*A1 (one accomplishing p4-plate is placed on B0).

e) B0->*2B1 (2 ways of selecting a pair of dominos on B0).

Let a(n) and b(n) be the number of tilings of the 2 X 2 X 2 X n box ending with an A- or a B-profile respectively. With the transitions above, one obtains recurrence 1.

/\ /\ /\

/ \ / \ / \

/ \ S' /\ / \ /\ / \ /\

/ \ / \ / \ / \ / \ / \

|\ / \ /||\ / \ /||\ / \ /|

| \ / \ / || \ / \ / || \ / \ / |

| S |\ /| R'|| |\ /| R"|| |\ /| |---> 4th dimension

|\ | \ / | /||\ | \ / | /||\ | \ / | /|

| \| R | |/ || \| | |/ || \| | |/ |

| P |\ | /| Q'|| |\ | /| Q"|| |\ | /| |

\ | \|/ | / \ | \|/ | / \ | \|/ | /

\| Q | |/ \| | |/ \| | |/

\ | / \ | / \ | /

\|/ \|/ \|/

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (5,15,-18).

Crossrefs

Cf. A001045, A006253, A359884.

Programs

Mathematica

LinearRecurrence[{5, 15, -18}, {1, 3, 30}, 25] (* Paolo Xausa, May 28 2024 *)

Formula

Recurrence 1: a(n) = 3*a(n-1) + b(n-1) + 9*a(n-2), b(n) = 12*a(n-1) + 2*b(n-1), with a(0) = 1 and a(-1) = b(0) = 0.

Recurrence 2: a(n) = 5*a(n-1) + 15*a(n-2) - 18*a(n-3).

G.f.: (1-2*x) / (1-5*x-15*x^2+18*x^3).