Date: Sun, 17 Feb 2002 18:08:38 -0800
From: Dean Hickerson
.___.
a(1)=1: |___|
.___.
._______. |___|
a(2)=2: |___|___| |___|
._____. ._____.
.___________. |___| | | | | |
a(3)=3: |___|___|___| |___|_| |_|_|_|
._______. ._______. ._______.
._______________. |___| | | | |___| | | | | | |
a(4)=4: |___|___|___|___| |___|_|_| |_|___|_| |_|_|_|_|
We abbreviate the last three arrangement to 211, 121, 112, using the
convention that 1 means vertical mat, 2 means 2 horizontal mats.
For n=5, there's 1 way to cover a 1x10 room and 4 ways to cover a 2x5
(212, 2111, 1211, 11111). So a(5) = 1+4 = 5.
For n=6, there's 1 way to cover 1x12, 6 ways to cover 2x6 (2112, 2121,
21111, 12111, 11211, 111111), and 2 ways to cover 3x4:
._______. ._______.
| | |___| | |___| |
|_|_| | | |_|___|_|
|___|_|_| |___|___|
So a(6) = 1+6+2 = 9.
For n=7, there's 1 way to cover 1x14 and 8 ways to cover 2x7 (21112, 21121,
21211, 12121, 211111, 121111, 112111, 1111111), so a(7) = 1+8 = 9.