%I #58 Nov 04 2024 18:12:57
%S 1,2,6,13,29,68,156,357,821,1886,4330,9945,22841,52456,120472,276681,
%T 635433,1459354,3351598,7697381,17678037,40599916,93242996,214144685,
%U 491811165,1129508406,2594063186,5957604017,13682413681,31423445328,72168035504,165743294353
%N Number of tatami tilings of a 2 X n grid (with monomers allowed).
%C A tatami tiling consists of dimers (1 x 2) and monomers (1 x 1) where no four meet at a point.
%C Also, a(n) is the number of permutations of 1, ..., n+1 such that i can go to j only if |i-j| <= 2 and such that the pattern cdab (two consecutive pairs of elements swap position) is explicitly forbidden. - _Jean M. Morales_, Jun 02 2013
%H A.H.M. Smeets, <a href="/A180965/b180965.txt">Table of n, a(n) for n = 0..2770</a>
%H A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, <a href="http://dx.doi.org/10.1007/978-3-642-14031-0_32">Auspicious Tatami Mat Arrangements</a>, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.
%H A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, <a href="https://doi.org/10.37236/596">Monomer-Dimer Tatami Tilings of Rectangular Regions</a>, Electronic Journal of Combinatorics, 18(1) (2011) P109.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,2,-1).
%F G.f.: (1 + 2*x^2 - x^3)/(1 - 2*x - 2*x^3 + x^4).
%F Lim_{n -> inf} a(n)/a(n-1) = (sqrt(3) + 1)/2 + sqrt(sqrt(3)/2). - _A.H.M. Smeets_, Sep 10 2018
%F a(n) = 2*a(n-1) + 2*a(n-3) - a(n-4). - _Muniru A Asiru_, Sep 11 2018
%e Below we show the a(3) = 13 tatami tilings of a 2 X 3 rectangle where v = square of a vertical dimer, h = square of a horizontal dimer, m = monomer:
%e vvv vhh vmm vhh vmv vvm hhv hhm hhv mvv mhh mmv mvm
%e vvv vhh vhh vmm vmv vvm hhv mhh mmv mvv hhm hhv mvm
%p seq(coeff(series((1+2*x^2-x^3)/(x^4-2*x^3-2*x+1),x,n+1), x, n), n = 0 .. 35); # _Muniru A Asiru_, Sep 11 2018
%t CoefficientList[(1+2z^2-z^3)/(1-2z-2z^3+z^4) + O[z]^32, z] (* _Jean-François Alcover_, May 27 2015 *)
%t LinearRecurrence[{2,0,2,-1},{1,2,6,13},40] (* _Harvey P. Dale_, Jan 19 2023 *)
%o (Python)
%o from math import log
%o print(0,1)
%o print(1,2)
%o print(2,6)
%o print(3,13)
%o n,a0,a1,a2,a3 = 3,13,6,2,1
%o while log(a0)/log(10) < 1000:
%o n,a0,a1,a2,a3 = n+1,2*(a0+a2)-a3,a0,a1,a2
%o print(n,a0) # _A.H.M. Smeets_, Sep 10 2018
%o (PARI) my(x='x+O('x^50)); Vec((1+2*x^2-x^3)/(1-2*x-2*x^3+x^4)) \\ _Altug Alkan_, Sep 10 2018
%o (GAP) a:=[1,2,6,13];; for n in [5..35] do a[n]:=2*a[n-1]+2*a[n-3]-a[n-4]; od; a; # _Muniru A Asiru_, Sep 11 2018
%o (Magma) I:=[1,2,6,13]; [n le 4 select I[n] else 2*Self(n-1)+2*Self(n-3)-Self(n-4): n in [1..35]]; // _Vincenzo Librandi_, Sep 11 2018
%o (Sage)
%o def A180965_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( (1+2*x^2-x^3)/(1-2*x-2*x^3+x^4) ).list()
%o A180965_list(40) # _G. C. Greubel_, Apr 06 2021
%Y Cf. A000045 (1 X n grid), A180970 (3 X n grid).
%Y Row sums of A272471.
%K nonn
%O 0,2
%A _Frank Ruskey_, Sep 29 2010