login
a(n) = 2*a(n-1) + a(n-3), where a(0) = 0, a(1) = 1, a(2) = 4.
1

%I #14 Jun 08 2020 09:02:53

%S 0,1,4,8,17,38,84,185,408,900,1985,4378,9656,21297,46972,103600,

%T 228497,503966,1111532,2451561,5407088,11925708,26302977,58013042,

%U 127951792,282206561,622426164,1372804120,3027814801,6678055766

%N a(n) = 2*a(n-1) + a(n-3), where a(0) = 0, a(1) = 1, a(2) = 4.

%C a(n) is the number of ways to tile a 2 x n strip, with a bent tromino added to the top, with dominos and L-shaped trominos:

%C ._

%C |_|_

%C |_|_|_ _ _

%C |_|_|_|_|_| . . .

%C |_|_|_|_|_| . . .

%H Colin Barker, <a href="/A335274/b335274.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,1).

%F a(n) = 2*a(n-1) + a(n-3).

%F a(n) = 2*A008998(n-1) - A008998(n-4).

%F a(n) = A008998(n-1) + 2*A008998(n-2).

%F G.f.: x*(1 + 2*x) / (1 - 2*x - x^3). - _Colin Barker_, Jun 04 2020

%e a(2) = 4 as shown by these four tilings:

%e ._ _ _ _

%e |X|_ | |_ |X|_ | |_

%e |X|X| , |_|X| , |X|X| , |_| |

%e |_ _| |X X| | | | |X|_|

%e |_ _| |_ _| |_|_| |X X|

%o (PARI) concat(0, Vec(x*(1 + 2*x) / (1 - 2*x - x^3) + O(x^35))) \\ _Colin Barker_, Jun 04 2020

%Y Cf. A008998, A335242.

%K nonn,easy

%O 0,3

%A _Michael Tulskikh_, May 30 2020