|
%I #38 Feb 23 2022 17:02:38
%S 1,16,131,335,851,2207,5891,16175,45491,130367,378851,1112015,3286931,
%T 9762527,29091011,86879855,259853171,777986687,2330814371,6986151695,
%U 20945872211,62812450847,188387020931,565060399535,1694979872051,5084536963007,15252805582691
%N Number of ways to tile an n X n square with 1 X 1 squares and (n-1) X 1 vertical or horizontal strips.
%C It is assumed that 1 X 1 squares and 1 X 1 strips can be distinguished. - _Alois P. Heinz_, Feb 23 2022
%H Colin Barker, <a href="/A335560/b335560.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-11,6).
%F a(n) = 2*3^n + 12*2^n - 19, for n >= 3.
%F From _Colin Barker_, Jun 14 2020: (Start)
%F G.f.: x*(1 + 10*x + 46*x^2 - 281*x^3 + 186*x^4) / ((1 - x)*(1 - 2*x)*(1 - 3*x)).
%F a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) for n>5.
%F (End)
%e Here is one of the 131 ways to tile a 3 X 3 square, in this case using two horizontal and two vertical strips:
%e _ _ _
%e |_ _| |
%e | |_|_|
%e |_|_ _|
%t Join[{1, 16}, LinearRecurrence[{6, -11, 6}, {131, 335, 851}, 25]] (* _Amiram Eldar_, Jun 16 2020 *)
%o (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
%Y Cf. A063443 and A211348 (tiling an n X n square with smaller squares).
%Y Cf. A028420 (tiling an n X n square with monomers and dimers).
%K nonn,easy
%O 1,2
%A _Oluwatobi Jemima Alabi_, Jun 14 2020
|
