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

Author

Frank Ruskey, Sep 29 2010

Keywords

• nonn

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

Examples

			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
		

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

Crossrefs

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

Row sums of A272471.

Programs

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

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 *)

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

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

Sage

def A180965_list(prec):
    P. = 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

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