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,3

Comments

Without the restriction one gets the Fibonacci numbers, A000045.

Might be called the no-tri-bonacci numbers.

Links

Table of n, a(n) for n=0..45.

Brian Rice, Proof of the recurrence

Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

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).

Example

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.

Mathematica

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

Crossrefs

Cf. A000045.

Sequence in context: A240508 A174068 A135833 * A026930 A211862 A286948

Adjacent sequences: A137197 A137198 A137199 * A137201 A137202 A137203

Keyword

nonn

Author

Barry Cipra, Mar 03 2008

Status

approved