login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 + 2z^2 - z^3)/(1 - 2z - 2z^3 + z^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 *)

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 18 04:50 EDT 2019. Contains 326072 sequences. (Running on oeis4.)