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

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.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

Cf. A000045 (1 X n grid), A180970 (3 X n grid).

Row sums of A272471.

Sequence in context: A173009 A212586 A276411 * A075632 A288979 A289048

Adjacent sequences: A180962 A180963 A180964 * A180966 A180967 A180968

Keyword

nonn

Author

Frank Ruskey, Sep 29 2010

Status

approved