OFFSET
0,2
COMMENTS
A tatami tiling consists of dimers (1 x 2) and monomers (1 x 1) where no four meet at a point.
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
LINKS
A.H.M. Smeets, Table of n, a(n) for n = 0..2770
A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.
A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Monomer-Dimer Tatami Tilings of Rectangular Regions, Electronic Journal of Combinatorics, 18(1) (2011) P109.
Index entries for linear recurrences with constant coefficients, signature (2,0,2,-1).
FORMULA
G.f.: (1 + 2*x^2 - x^3)/(1 - 2*x - 2*x^3 + x^4).
Lim_{n -> inf} a(n)/a(n-1) = (sqrt(3) + 1)/2 + sqrt(sqrt(3)/2). - A.H.M. Smeets, Sep 10 2018
a(n) = 2*a(n-1) + 2*a(n-3) - a(n-4). - Muniru A Asiru, Sep 11 2018
EXAMPLE
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:
vvv vhh vmm vhh vmv vvm hhv hhm hhv mvv mhh mmv mvm
vvv vhh vhh vmm vmv vvm hhv mhh mmv mvv hhm hhv mvm
MAPLE
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
MATHEMATICA
CoefficientList[(1+2z^2-z^3)/(1-2z-2z^3+z^4) + O[z]^32, z] (* Jean-François Alcover, May 27 2015 *)
LinearRecurrence[{2, 0, 2, -1}, {1, 2, 6, 13}, 40] (* Harvey P. Dale, Jan 19 2023 *)
PROG
(Python)
from math import log
print(0, 1)
print(1, 2)
print(2, 6)
print(3, 13)
n, a0, a1, a2, a3 = 3, 13, 6, 2, 1
while log(a0)/log(10) < 1000:
n, a0, a1, a2, a3 = n+1, 2*(a0+a2)-a3, a0, a1, a2
print(n, a0) # A.H.M. Smeets, Sep 10 2018
(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
(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
(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
(Sage)
def A180965_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P( (1+2*x^2-x^3)/(1-2*x-2*x^3+x^4) ).list()
A180965_list(40) # G. C. Greubel, Apr 06 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Frank Ruskey, Sep 29 2010
STATUS
approved