A335242 a(n) = 2*a(n-1) + a(n-3) for n >= 4, with initial values a(0) = 1, a(1) = 0, a(2) = 2, and a(3) = 3.

1, 0, 2, 3, 6, 14, 31, 68, 150, 331, 730, 1610, 3551, 7832, 17274, 38099, 84030, 185334, 408767, 901564, 1988462, 4385691, 9672946, 21334354, 47054399, 103781744, 228897842, 504850083, 1113481910, 2455861662, 5416573407, 11946628724, 26349119110, 58114811627

Offset

0,3

Comments

a(n) is the number of ways to tile this 2 X n strip (with one extra square added at the top left) with dominoes and L-shaped trominoes (also called polyominoes):

._

|_|_ _ _ _

|_|_|_|_|_| . . .

|_|_|_|_|_| . . .

Links

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

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

Formula

a(n) = 2*a(n-1) + a(n-3) for n >= 4.

a(n) = A008998(n-2) + A052980(n-2) for n >= 2.

G.f.: (2*x^3-2*x^2+2*x-1)/(x^3+2*x-1).

Example

a(2) = 2 thanks to the following two tilings (where the L-shaped trominoes are tiled with X's and the dominoes are left blank):
._            _
|X|_         | |_
|X|X|  and   |_|X|
|_ _|        |X X|

Mathematica

Join[{1}, LinearRecurrence[{2, 0, 1}, {0, 2, 3}, 40]

Crossrefs

Cf. A052980, A008998.

Sequence in context: A211931 A264078 A006444 * A032047 A032065 A307231

Adjacent sequences: A335239 A335240 A335241 * A335243 A335244 A335245

Keyword

nonn,easy

Author

Greg Dresden, May 28 2020

Status

approved