A137200 Number of ways to tile an n X 1 strip with 1 X 1 squares and 2 X 1 dominoes with the restriction that no three consecutive tiles are of the same type.

1, 1, 2, 2, 4, 5, 7, 9, 13, 18, 25, 34, 47, 65, 90, 124, 171, 236, 326, 450, 621, 857, 1183, 1633, 2254, 3111, 4294, 5927, 8181, 11292, 15586, 21513, 29694, 40986, 56572, 78085, 107779, 148765, 205337, 283422, 391201, 539966, 745303, 1028725, 1419926, 1959892

Offset: 0

Author

Barry Cipra, Mar 03 2008

Keywords

• nonn

Comments

Without the restriction one gets the Fibonacci numbers, A000045.

Might be called the no-tri-bonacci numbers.

Examples

			For example (using 1's to denote squares and 2's to denote dominoes), a(6)=7 because you have the tilings 11211, 1122, 1212, 1221, 2112, 2121 and 2211 and no others.
		

Links

• Brian Rice, Proof of the recurrence
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Crossrefs

Cf. A000045.

Programs

Mathematica

Join[{1},LinearRecurrence[{1,0,0,1},{1,2,2,4},50]] (* Harvey P. Dale, Jul 26 2011 *)

Formula

a(n) = a(n-1) + a(n-4) for n>4; g.f.: (1+x^2+x^4)/(1-x-x^4). Also a(n) = a(n-2) + a(n-4) + a(n-5).