cp's OEIS Frontend

A180965 Number of tatami tilings of a 2 X n grid (with monomers allowed).

%I A180965 #58 Nov 04 2024 18:12:57
%S A180965 1,2,6,13,29,68,156,357,821,1886,4330,9945,22841,52456,120472,276681,
%T A180965 635433,1459354,3351598,7697381,17678037,40599916,93242996,214144685,
%U A180965 491811165,1129508406,2594063186,5957604017,13682413681,31423445328,72168035504,165743294353
%N A180965 Number of tatami tilings of a 2 X n grid (with monomers allowed).
%C A180965 A tatami tiling consists of dimers (1 x 2) and monomers (1 x 1) where no four meet at a point.
%C A180965 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 A180965 A.H.M. Smeets, <a href="/A180965/b180965.txt">Table of n, a(n) for n = 0..2770</a>
%H A180965 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 A180965 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 A180965 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,2,-1).
%F A180965 G.f.: (1 + 2*x^2 - x^3)/(1 - 2*x - 2*x^3 + x^4).
%F A180965 Lim_{n -> inf} a(n)/a(n-1) = (sqrt(3) + 1)/2 + sqrt(sqrt(3)/2). - _A.H.M. Smeets_, Sep 10 2018
%F A180965 a(n) = 2*a(n-1) + 2*a(n-3) - a(n-4). - _Muniru A Asiru_, Sep 11 2018
%e A180965 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 A180965 vvv vhh vmm vhh vmv vvm hhv hhm hhv mvv mhh mmv mvm
%e A180965 vvv vhh vhh vmm vmv vvm hhv mhh mmv mvv hhm hhv mvm
%p A180965 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 A180965 CoefficientList[(1+2z^2-z^3)/(1-2z-2z^3+z^4) + O[z]^32, z] (* _Jean-François Alcover_, May 27 2015 *)
%t A180965 LinearRecurrence[{2,0,2,-1},{1,2,6,13},40] (* _Harvey P. Dale_, Jan 19 2023 *)
%o A180965 (Python)
%o A180965 from math import log
%o A180965 print(0,1)
%o A180965 print(1,2)
%o A180965 print(2,6)
%o A180965 print(3,13)
%o A180965 n,a0,a1,a2,a3 = 3,13,6,2,1
%o A180965 while log(a0)/log(10) < 1000:
%o A180965     n,a0,a1,a2,a3 = n+1,2*(a0+a2)-a3,a0,a1,a2
%o A180965     print(n,a0) # _A.H.M. Smeets_, Sep 10 2018
%o A180965 (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 A180965 (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 A180965 (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 A180965 (Sage)
%o A180965 def A180965_list(prec):
%o A180965     P.<x> = PowerSeriesRing(ZZ, prec)
%o A180965     return P( (1+2*x^2-x^3)/(1-2*x-2*x^3+x^4) ).list()
%o A180965 A180965_list(40) # _G. C. Greubel_, Apr 06 2021
%Y A180965 Cf. A000045 (1 X n grid), A180970 (3 X n grid).
%Y A180965 Row sums of A272471.
%K A180965 nonn
%O A180965 0,2
%A A180965 _Frank Ruskey_, Sep 29 2010