There are two triominoes. One is simple a 1x3 rectangle and the other is a small
L-shaped piece.
Using any combination of these two triominoes and in any orientation, how many ways can a 3 by N rectangle be tiled?
Rotations and reflections of an asymmetrical solution are to be considered distinct.
Answer, for a 3 x n grid:
n 1 2 3 4 5 6 7...
----------------------------------------------------------
f(n) 1 3 10 23 62 170 441... (unique tilings)
s(n) 1 2 5 2 2 4 (2 2 4 ) ... (novel blocks)
----------------------------------------------------------
Recursive equations:
f(1) = s(1)
f(2) = s(2) + s(1) f(1)
f(3) = s(3) + s(2) f(1) + s(1) f(2)
f(4) = s(4) + s(3) f(1) + s(2) f(2) + s(1) f(3)
etc.
The simplest recursive form is:
f(n) = f(n-1) + 2 f(n-2) + 6 f(n-3) + f(n-4) - f(n-6)
----------
This problem had the virtues of being easy to state,
hard to solve, and involving some nice math. I started
by writing a tree code that led to the sequence (program)
(output1, output2) and then I followed along with a paper
for this sequence which OEIS has as A134438 (Kreweras 1995)
It turns out that Jer had gotten almost all the way there.
He listed-out the full set of unique blocks (the assemblages
of triminos that are unbroken by any vertical lines).
Summarizing (repeating) his rogues gallery, there are
2 oddballs and then 3 infinite series. Here "AAA"
'BBB' etc. are the 3x1 horizontal trimino. XXX and YYY are
the "L-shape" trimino, and AAA rotated 90 degrees is:
Z
Z
Z
The two oddballs (length 1 and 3)
(made from 1 vertical trimino, 3 horizontal triminos,
respectively)
Z AAA
Z BBB
Z CCC
Series I (lengths 2 5 8 ...) (2 rotations possible)
XX XXAAA XXAAABBB
XY XBBBY XCCCDDDY etc.
YY CCCYY EEEFFFYY
Series II (lengths 3 6 9 ...) (4 rotations possible)
XXY XXAAAY XXAAABBBY
XYY XBBBYY XCCCDDDYY etc.
AAA CCCDDD EEEFFFGGG
Series III (lengths 4 7 10...) (2 rotations possible)
AAAY AAABBBY AAABBBCCCY
XXYY XXCCCYY XXDDDEEEYY etc.
XBBB XDDDEEE XFFFGGGHHH
The s(n) numbers above list the number of unique
blocks of length n as per the figures above. The list
becomes repeating as 2,2,4,2,2,4,2,2,4,... after the 4th n
Now here is the cool math (I didn't know!)
If you have s(n) different types of length n, (e.g. these
blocks) then the number of unique ways, f(n), these lengths may
be assembled to add to a length n is given recursively by:
f(1) = s(1)
f(2) = s(2) + s(1) f(1)
f(3) = s(3) + s(2) f(1) + s(1) f(2)
f(4) = s(4) + s(3) f(1) + s(2) f(2) + s(1) f(3)
etc.
This works for all s(n) >= 0. It can be understood with a more
familiar analogy: Suppose s(n) were all = 1 (here they are not!),
for example, this become the partition of the integers.
E.g. f(1) = 1, f(2) = 1 + f(1)= 2, f(3) = 1 + f(1) + f(2) = 4.
There are 4 = 2^(n-1) ways to make 3: (1+1+1) (1+2) (2+1) (3).
The expression reduces to the familiar f(n) = 2^(n-1).
To get each term to also include the multiplicity of triminos
of each length i <= n, we multiple each term of each series
by appropriate s(i).
Putting the s(n) values given at the top of this page into this
expression gives the f(n) values, also listed at the top, which
were verified by the simulation.
Using a generating function and the cyclic nature of s(n),
the recursion can also be be reduced to the 6 terms, as above.
(This is something I am still learning to do, maybe
to put in a subsequent post)
Edited on October 26, 2023, 10:16 am
soln
