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.

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

Offset: 2

Author

Alejandro Erickson, Apr 12 2012

Keywords

• nonn

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.

Examples

			For n=4 the a(4)=2 solutions are
._ _ _ _.
|_| |_|_|
| |_|_ _|
|_|_ _| |
|_ _|_|_|
.
._ _ _ _.
|_|_| |_|
|_ _|_| |
| |_ _|_|
|_|_|_ _|
.
For n=5 the a(5)=2 solutions are
._ _ _ _ _.
|_|_ _| |_|
|_ _| |_|_|
|_| |_|_ _|
| |_|_ _| |
|_|_ _|_|_|
.
._ _ _ _ _.
|_| |_ _|_|
|_|_| |_ _|
|_ _|_| |_|
| |_ _|_| |
|_|_|_ _|_|
		

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.

Crossrefs

Cf. A001787, A226300, A226301.

Cf. A182110.

Programs

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

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

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