login
A180965
Number of tatami tilings of a 2 X n grid (with monomers allowed).
3
1, 2, 6, 13, 29, 68, 156, 357, 821, 1886, 4330, 9945, 22841, 52456, 120472, 276681, 635433, 1459354, 3351598, 7697381, 17678037, 40599916, 93242996, 214144685, 491811165, 1129508406, 2594063186, 5957604017, 13682413681, 31423445328, 72168035504, 165743294353
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. 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.
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
Cf. A000045 (1 X n grid), A180970 (3 X n grid).
Row sums of A272471.
Sequence in context: A173009 A212586 A276411 * A075632 A288979 A289048
KEYWORD
nonn
AUTHOR
Frank Ruskey, Sep 29 2010
STATUS
approved