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

1, 16, 131, 335, 851, 2207, 5891, 16175, 45491, 130367, 378851, 1112015, 3286931, 9762527, 29091011, 86879855, 259853171, 777986687, 2330814371, 6986151695, 20945872211, 62812450847, 188387020931, 565060399535, 1694979872051, 5084536963007, 15252805582691

Offset

1,2

Comments

It is assumed that 1 X 1 squares and 1 X 1 strips can be distinguished. - Alois P. Heinz, Feb 23 2022

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Formula

a(n) = 2*3^n + 12*2^n - 19, for n >= 3.

From Colin Barker, Jun 14 2020: (Start)

G.f.: x*(1 + 10*x + 46*x^2 - 281*x^3 + 186*x^4) / ((1 - x)*(1 - 2*x)*(1 - 3*x)).

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) for n>5.

(End)

Example

Here is one of the 131 ways to tile a 3 X 3 square, in this case using two horizontal and two vertical strips:
   _ _ _
  |_ _| |
  | |_|_|
  |_|_ _|

Mathematica

Join[{1, 16}, LinearRecurrence[{6, -11, 6}, {131, 335, 851}, 25]] (* Amiram Eldar, Jun 16 2020 *)

Prog

(PARI) Vec(x*(1 + 10*x + 46*x^2 - 281*x^3 + 186*x^4) / ((1 - x)*(1 - 2*x)*(1 - 3*x)) + O(x^30)) \\ Colin Barker, Jun 14 2020

Crossrefs

Cf. A063443 and A211348 (tiling an n X n square with smaller squares).

Cf. A028420 (tiling an n X n square with monomers and dimers).

Sequence in context: A196595 A055914 A255816 * A253224 A334979 A183535

Adjacent sequences: A335557 A335558 A335559 * A335561 A335562 A335563

Keyword

nonn,easy

Author

Oluwatobi Jemima Alabi, Jun 14 2020

Status

approved