login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A182107 Number of monomer-dimer tatami tilings (no four tiles meet) of the n X n grid with n monomers and equal numbers of vertical and horizontal dimers, up to rotational symmetry. 4
0, 0, 2, 2, 0, 0, 10, 20, 0, 0, 114, 210, 0, 0, 1322, 2460, 0, 0, 16428, 31122, 0, 0, 214660, 410378, 0, 0, 2897424, 5575682, 0, 0, 40046134, 77445152, 0, 0, 563527294, 1093987598, 0, 0, 8042361426, 15660579168, 0, 0, 116083167058, 226608224226, 0, 0, 1691193906828, 3308255447206, 0, 0, 24830916046462, 48658330768786, 0, 0, 366990100477712, 720224064591558, 0, 0, 5454733737618820 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

Monomer-dimer tatami tilings are arrangements of 1 X 1 monomers, 2 X 1 vertical dimers and 1 X 2 horizontal dimers on subsets of the integer grid, with the property that no four tiles meet at any point.  The maximum possible number of monomers in an n X n tatami tiling is n.  Balanced tatami tilings are those with an equal number of vertical and horizontal dimers.

Equals the ((n^2-n)/4)-th term of g.f. T_n(z) for A182110 if 4 divides n^2-n, and 0 otherwise.

LINKS

Alejandro Erickson, Table of n, a(n) for n = 2..199

Alejandro Erickson, Frank Ruskey, Enumerating maximal tatami mat coverings of square grids with v vertical dominoes, arXiv:1304.0070 [math.CO], 2013.

FORMULA

a(n) = 2 * Sum_{i=1..floor((n-1)/2)} (Sum_{j+k == (n^2-n)/4-(n-i-1)} S(n-i-2,j) * S(i-1,k) + Sum_{j+k == (n^2-n)/4} S(floor((n-2)/2), j) * S(floor((n-2)/2), k) ), where S(n,k) = S(n-1, k) + S(n-1, k-n), S(0,0)=1, S(0,k) = 0, S(n,k) = 0 if k < 0 or k > binomial(n+1,2).

EXAMPLE

For n=4 the a(4)=2 solutions are

._ _ _ _.

|_| |_|_|

| |_|_ _|

|_|_ _| |

|_ _|_|_|

.

._ _ _ _.

|_|_| |_|

|_ _|_| |

| |_ _|_|

|_|_|_ _|

.

For n=5 the a(5)=2 solutions are

._ _ _ _ _.

|_|_ _| |_|

|_ _| |_|_|

|_| |_|_ _|

| |_|_ _| |

|_|_ _|_|_|

.

._ _ _ _ _.

|_| |_ _|_|

|_|_| |_ _|

|_ _|_| |_|

| |_ _|_| |

|_|_|_ _|_|

MATHEMATICA

S[0, 0]=1; S[0, _]=0; S[n_, k_] /; k<0 || k>Binomial[n+1, 2] =0; S[n_, k_]:= S[n, k] = S[n-1, k] + S[n-1, k-n];

a[n_]:= 2 Sum[Sum[k2 = (n^2-n)/4 - (n-i-1) - k1; S[n-i-2, k1] S[i-1, k2], {k1, 0, (n^2-n)/4 - (n-i-1)}] + Sum[k2 = (n^2-n)/4; S[Floor[(n-2)/2], k1] S[Floor[(n-2)/2], k2], {k1, 0, (n^2-n)/4}], {i, 1, Floor[(n-1)/2]}];

Table[a[n], {n, 2, 60}] (* Jean-Fran├žois Alcover, Jan 29 2019 *)

PROG

(Sage)

@cached_function

def genS(n, z):

    out = 1

    for i in [j+1 for j in range(n)]:

        out = out*(1+z^i)

    return out

VH = lambda n, z: 2*sum([genS(n-i-2, z)*genS(i-1, z)*z^(n-i-1) for i in range(1, floor((n-1)/2)+1)]) + genS(floor((n-2)/2), z)^2

ZP.<x> = PolynomialRing(ZZ)

#4 divides n^2-n? coefficient of VH : 0

a = lambda n: (4.divides(n^2-n) and [ZP(VH(n, x))[(n^2-n)/4]] or [0])[0]

CROSSREFS

Cf. A001787, A226300, A226301.

Cf. A182110.

Sequence in context: A230275 A230592 A282699 * A337999 A037224 A122670

Adjacent sequences:  A182104 A182105 A182106 * A182108 A182109 A182110

KEYWORD

nonn

AUTHOR

Alejandro Erickson, Apr 12 2012

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 April 11 12:38 EDT 2021. Contains 342886 sequences. (Running on oeis4.)