OFFSET
0,2
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,2,2,1).
FORMULA
a(n) = a(n-1) + 2*a(n-2) + 2*a(n-3) + a(n-4) for n >= 4, with a(0)=1, a(1)=2, a(2)=5, a(3)=11.
G.f.: (1 + x + x^2)/(1 - x - 2*x^2 - 2*x^3 - x^4).
EXAMPLE
For n=1: two tilings -- a single red tile, or a single blue tile. a(1) = 2.
For n=2: five tilings -- using either two size-1 tiles (BB, BR, RB -- RR excluded) or one size-2 tile (red or blue). a(2) = 5.
MATHEMATICA
LinearRecurrence[{1, 2, 2, 1}, {1, 2, 5, 11}, 35] (* Paolo Xausa, Aug 17 2026 *)
PROG
(Python)
def a(n):
dp = {0: {-1: 1}}
for i in range(n+1):
if i not in dp:
continue
for last_color, cnt in dp[i].items():
for size in (1, 2):
ni = i + size
if ni > n:
continue
for color in (0, 1):
if color == 1 and last_color == 1:
continue
dp.setdefault(ni, {})
dp[ni][color] = dp[ni].get(color, 0) + cnt
return sum(dp.get(n, {}).values())
print([a(n) for n in range(1, 33)])
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Sajid Khan Hussain, Aug 09 2026
STATUS
approved