login
Number of tilings of a 2 X n rectangle with dominoes and long L-shaped 4-minoes.
0

%I #29 Nov 11 2024 09:01:15

%S 1,1,2,7,15,32,79,185,422,987,2307,5352,12451,29005,67478,156991,

%T 365391,850304,1978615,4604465,10715078,24934611,58024779,135028632,

%U 314222011,731218981,1701605078,3959769367,9214694391,21443322032,49900304047,116121942377

%N Number of tilings of a 2 X n rectangle with dominoes and long L-shaped 4-minoes.

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

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

%F Sum_{j=0..n} a(n) = (1/7)(a(n+4) - a(n+2) - 5*a(n+1) - 1).

%F G.f.: 1/(1 - x - x^2 - 4*x^3 - 2*x^4). - _Stefano Spezia_, Jun 19 2021

%F a(n) = F(n+1) + 2*Sum_{j=3..n} a(n-j)*F(j) for F(i) = A000045(i) the i-th Fibonacci number. - _Greg Dresden_, Nov 10 2024

%e For n = 3 the a(3)=7 tilings are:

%e ._____. ._____. ._____. ._____.

%e | |___| |___| | | ___| |___ |

%e |_____| |_____| |_|___| |___|_|

%e ._____. ._____. ._____.

%e |___| | | |___| | | | |

%e |___|_| |_|___| |_|_|_|

%t LinearRecurrence[{1, 1, 4, 2}, {1, 1, 2, 7}, 40]

%Y Cf. A052980.

%K nonn,easy

%O 0,3

%A _Greg Dresden_ and _Yiwen Zhang_, Jun 19 2021