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

Links

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.

Formula

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

Example

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

Prog

(Sage)
@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.<x> = PolynomialRing(ZZ)
#call T(n, x) for the g.f. T_n(x)

Crossrefs

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.

Sequence in context: A277214 A278603 A248218 * A175328 A338776 A345933

Adjacent sequences: A182107 A182108 A182109 * A182111 A182112 A182113

Keyword

nonn,tabf

Author

Alejandro Erickson, Apr 12 2012

Extensions

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

Status

approved