|
%I #41 Mar 08 2020 00:05:41
%S 0,0,2,2,0,0,10,20,0,0,114,210,0,0,1322,2460,0,0,16428,31122,0,0,
%T 214660,410378,0,0,2897424,5575682,0,0,40046134,77445152,0,0,
%U 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
%N 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.
%C 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.
%C 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.
%H Alejandro Erickson, <a href="/A182107/b182107.txt">Table of n, a(n) for n = 2..199</a>
%H Alejandro Erickson, Frank Ruskey, <a href="http://arxiv.org/abs/1304.0070">Enumerating maximal tatami mat coverings of square grids with v vertical dominoes</a>, arXiv:1304.0070 [math.CO], 2013.
%F 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).
%e For n=4 the a(4)=2 solutions are
%e ._ _ _ _.
%e |_| |_|_|
%e | |_|_ _|
%e |_|_ _| |
%e |_ _|_|_|
%e .
%e ._ _ _ _.
%e |_|_| |_|
%e |_ _|_| |
%e | |_ _|_|
%e |_|_|_ _|
%e .
%e For n=5 the a(5)=2 solutions are
%e ._ _ _ _ _.
%e |_|_ _| |_|
%e |_ _| |_|_|
%e |_| |_|_ _|
%e | |_|_ _| |
%e |_|_ _|_|_|
%e .
%e ._ _ _ _ _.
%e |_| |_ _|_|
%e |_|_| |_ _|
%e |_ _|_| |_|
%e | |_ _|_| |
%e |_|_|_ _|_|
%t 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];
%t 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]}];
%t Table[a[n], {n, 2, 60}] (* _Jean-François Alcover_, Jan 29 2019 *)
%o (Sage)
%o @cached_function
%o def genS(n,z):
%o out = 1
%o for i in [j+1 for j in range(n)]:
%o out = out*(1+z^i)
%o return out
%o 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
%o ZP.<x> = PolynomialRing(ZZ)
%o #4 divides n^2-n? coefficient of VH : 0
%o a = lambda n: (4.divides(n^2-n) and [ZP(VH(n,x))[(n^2-n)/4]] or [0])[0]
%Y Cf. A001787, A226300, A226301.
%Y Cf. A182110.
%K nonn
%O 2,3
%A _Alejandro Erickson_, Apr 12 2012
|
