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

Author

Oluwatobi Jemima Alabi, Jun 14 2020

Keywords

• nonn
• easy
• changed

Comments

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

Examples

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

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

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).

Programs

Mathematica

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

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

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)

E.g.f.: 5 - 19*exp(x) +12 *exp(2*x) + 2*exp(3*x) - 10*x - 31*x^2/2. - Stefano Spezia, Aug 25 2025