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

193, 399, 783, 1601, 3283, 6947, 14897, 32607, 72175, 161649, 364611, 827555, 1885729, 4310639, 9874319, 22654881, 52032883, 119601123, 275058321, 632823743, 1456319215, 3352072913, 7716633443, 17765737443, 40904125825, 94182711375

Offset

5,1

Links

Table of n, a(n) for n=5..30.

Index entries for linear recurrences with constant coefficients, signature (3,1,-7,1,3).

Formula

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

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

Example

Here are two of the 193 possible tilings for a 5 X 5 square (using 1 X 1 squares and 3 X 2 rectangles):
._________   ._________
|_|     |_|  |_|_|     |
|_|_ _ _|_|  |   |_ _ _|
|   |_|   |  |   |_|   |
|   |_|   |  |___|_|   |
|___|_|___|  |_|_|_|___|

Crossrefs

Cf. A000045, A006130.

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.

Sequence in context: A100363 A142500 A328137 * A113000 A105129 A140631

Adjacent sequences: A347633 A347634 A347635 * A347637 A347638 A347639

Keyword

nonn,easy

Author

Greg Dresden and Osondu Ugochukwu, Sep 09 2021

Status

approved