login
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
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, 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
KEYWORD
nonn
AUTHOR
Alejandro Erickson, Apr 12 2012
STATUS
approved