Alejandro Erickson - cp's OEIS frontend

User: Alejandro Erickson

Alejandro Erickson has authored 2 sequences.

A182110 Irregular triangle read by rows: generating function counting rotationally distinct n X n tatami tilings with n monomers and exactly k vertical dimers.

1, 1, 2, 1, 2, 3, 2, 1, 2, 3, 6, 4, 2, 2, 1, 2, 3, 6, 9, 8, 7, 6, 2, 2, 2, 1, 2, 3, 6, 9, 14, 15, 14, 14, 10, 8, 6, 4, 2, 2, 2, 1, 2, 3, 6, 9, 14, 22, 24, 25, 28, 25, 22, 19, 14, 10, 10, 8, 4, 4, 2, 2, 2, 1, 2, 3, 6, 9, 14, 22, 32, 37, 42, 49, 48, 49, 46, 38, 34, 30, 24, 20, 16, 12, 12, 10, 6, 4, 4, 2, 2, 2

Offset: 0

Alejandro Erickson, Apr 12 2012

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. a(n) applies to tilings of this type which have monomers in their top corners.

a(n) is the table T(2,0); T(3,0), T(3,1); T(4,0), T(4,1), T(4,2), T(4,3); T(5,0), T(5,1) ... where T(n,k) is the number of n X n tilings of the type described above with exactly k vertical dimers when n is even and exactly k horizontal dimers when n is odd.

			T_5(z) = 1 + 2*z + 3*z^2 + 6*z^3 + 4*z^4 + 2*z^5 + 2*z^6;
T(5,2) = 3, and the tilings are as follows:
._ _ _ _ _.
|_|_ _| |_|
|_ _| |_| |
|_| |_| |_|
| |_| |_| |
|_|_|_|_|_|
.
._ _ _ _ _.
|_| |_ _|_|
| |_| |_ _|
|_| |_| |_|
| |_| |_| |
|_|_|_|_|_|
.
._ _ _ _ _.
|_| |_| |_|
| |_| |_| |
|_| |_| |_|
|_|_| |_|_|
|_ _|_|_ _|
The triangle begins:
1
1,2
1,2,3,2
1,2,3,6,4,2,2
1,2,3,6,9,8,7,6,2,2,2
1,2,3,6,9,14,15,14,14,10,8,6,4,2,2,2
1,2,3,6,9,14,22,24,25,28,25,22,19,14,10,10,8,4,4,2,2,2
1,2,3,6,9,14,22,32,37,42,49,48,49,46,38,34,30,24,20,16,12,12,10,6,4,4,2,2,2
1,2,3,6,9,14,22,32,46,56,66,78,84,90,92,88,81,76,69,58,51,44,38,34,28,22,20,16,14,12,8,6,4,4,2,2,2
...

Alejandro Erickson, Table of n, a(n) for n = 0..9999
Alejandro Erickson, Table of coefficients of T_n(z)
Alejandro Erickson, Frank Ruskey, Enumerating maximal tatami mat coverings of square grids with v vertical dominoes, arXiv:1304.0070 [math.CO], 2013.

S_k(z) is entry A053632.
T_n(z) is a partition of A001787(n)/4.
Tatami tilings with the same number of vertical and horizontal dimers is A182107.

@cached_function
def S(n,z):
    out = 1
    for i in [j+1 for j in range(n)]:
        out = out*(1+z^i)
    return out
T = lambda n,z: 2*sum([S(n-i-2,z)*S(i-1,z)*z^(n-i-1) for i in range(1,floor((n-1)/2)+1)]) + S(floor((n-2)/2),z)^2
ZP. = PolynomialRing(ZZ)
#call T(n,x) for the g.f. T_n(x)

G.f.: T_n(z) = Sum_{k>=0} T(n,k)*z^k is equal to

T_n(z) = 2*Sum_{i=1..floor((n-1)/2)} S_{n-i-2}(z)*S_{i-1}(z)*z^{n-i-1} + (S_{floor((n-2)/2))^2, where S_k(z) = Product_{i=1..k} (1+z^i). Note that deg(T_n(z)) = binomial(n-1,2).

Entry revised by N. J. A. Sloane, Jun 06 2013

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.

Original entry on oeis.org

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

Alejandro Erickson, Apr 12 2012

nonn

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.

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

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.

Cf. A001787, A226300, A226301.

Cf. A182110.

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

@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]

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

cp's OEIS Frontend

User: Alejandro Erickson

A182110 Irregular triangle read by rows: generating function counting rotationally distinct n X n tatami tilings with n monomers and exactly k vertical dimers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions