login
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
1, 3, 30, 177, 1281, 8520, 58629, 397887, 2715510, 18490533, 126023349, 858595560, 5850498441, 39863005323, 271617783150, 1850725023657, 12610357769721, 85923544106760, 585460036653789, 3989166905015367, 27181111280961990, 185204779320272253
OFFSET
0,2
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 | |/ \| | |/ \| | |/
\ | / \ | / \ | /
\|/ \|/ \|/
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).
MATHEMATICA
LinearRecurrence[{5, 15, -18}, {1, 3, 30}, 25] (* Paolo Xausa, May 28 2024 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gerhard Kirchner, Feb 15 2023
STATUS
approved