A rectangle has dimensions of 3 by 30. How many ways can this rectangle be tiled with 1 by 2 dominoes?
The dominoes can go in either orientation. A rotation or reflection of an asymmetric solution is considered distinct.
Provide a formula for a generalized 3 by 2n rectangle.
A classic version of this puzzle is for a 2 by n rectangle.
Rather than focus on 3 by 2n I thought about 3 by m with one blank square on the right edge if m is odd.
This led pretty quickly to the recursion which is different for even or odd m.
a(0)=1
a(1)=2 (the blank can be top or bottom)
a(2)=3
For even m, a(m)=a(m-1)+a(m-2) [same as the usual 2xm rule]
For odd m, a(m)=2*m(m-1)+a(m-2)
The next few terms are a(3)=8, a(4)=11, a(5)=30
Which was enough terms to find https://oeis.org/A048788
There is no reference to this problem, but the recursion is there. We just need an offset. For a 3x30 rectangle, term 31 is given as 299303201
|
|
Posted by Jer
on 2023-08-29 11:19:51 |
Solution
