login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of ways to tile an n X n square with 1 X 1 squares and (n-2) X 2 vertical or horizontal rectangles.
0

%I #23 Sep 25 2021 07:25:36

%S 193,399,783,1601,3283,6947,14897,32607,72175,161649,364611,827555,

%T 1885729,4310639,9874319,22654881,52032883,119601123,275058321,

%U 632823743,1456319215,3352072913,7716633443,17765737443,40904125825,94182711375

%N Number of ways to tile an n X n square with 1 X 1 squares and (n-2) X 2 vertical or horizontal rectangles.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-7,1,3).

%F a(n) = 2*A006130(n) + 12*F(n + 1) + 16*F(n - 1) - 31 for F(n) = A000045(n) the Fibonacci sequence.

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

%e Here are two of the 193 possible tilings for a 5 X 5 square (using 1 X 1 squares and 3 X 2 rectangles):

%e ._________ ._________

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

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

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

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

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

%Y Cf. A000045, A006130.

%Y Cf. A335560 which is the same problem but with 1 X 1 squares and (n-1) X 1 rectangles, and A337024 which uses 1 X 1 squares and 2 X 2 squares.

%K nonn,easy

%O 5,1

%A _Greg Dresden_ and _Osondu Ugochukwu_, Sep 09 2021