A192095 Number of tatami tilings of an n X n square with exactly k horizontal dimers and n monomers (no restriction on the number of vertical dimers).

1, 2, 2, 2, 4, 4, 2, 2, 4, 6, 8, 6, 4, 2, 2, 4, 6, 12, 12, 8, 12, 12, 6, 4, 2, 2, 4, 6, 12, 18, 20, 18, 16, 16, 18, 20, 18, 12, 6, 4, 2, 2, 4, 6, 12, 18, 28, 34, 32, 32, 28, 28, 28, 28, 32, 32, 34, 28, 18, 12, 6, 4, 2, 2, 4, 6, 12, 18, 28, 44, 52, 54, 60, 58, 52, 54, 48, 40, 48, 54, 52, 58, 60, 54, 52, 44, 28, 18, 12, 6, 4, 2

Offset

1,2

Comments

A tatami tiling consists of dimers (1 X 2) and monomers (1 X 1) where no four meet at a point.

The (n, r) entry contains the number of tatami tilings of an n X n square with exactly r horizontal dimers and n monomers and arbitrarily many vertical dimers(n: row number, r: column number).

Rows are of length 1 + 1*0/2, 1 + 2*1/2, 1 + 3*2/2, 1 + 4*3/2, ... and in the range [1, 8].

Columns are counted from 0.

Here is the first three rows of the sequence:

1

2 2

2 4 4 2

The sum of all entries in the n-th row is n*2^(n-1) [1].

Note that numbers of horizontal dimers and vertical dimers are interchangeable.

Links

Table of n, a(n) for n=1..92.

1. A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.

2. A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Monomer-Dimer Tatami Tilings of Rectangular Regions, Electronic Journal of Combinatorics, 18(1) (2011) P109, 24 pages.

Example

Here are the tatami tilings of the 3 X 3 square with three monomers:
    No horizontal dimer:
        _ _ _      _ _ _
       |_| |_|    | |_| |
       | |_| |    |_| |_|
       |_|_|_|    |_|_|_|
    One horizontal dimer:
        _ _ _      _ _ _      _ _ _      _ _ _
       |_ _| |    |_| |_|    |_| |_|    | |_ _|
       |_| |_|    |_|_| |    | |_|_|    |_| |_|
       |_|_|_|    |_ _|_|    |_|_ _|    |_|_|_|
    Two horizontal dimers:
        _ _ _      _ _ _      _ _ _      _ _ _
       |_ _|_|    |_|_ _|    |_|_| |    | |_|_|
       | |_ _|    |_ _| |    |_ _|_|    |_|_ _|
       |_|_|_|    |_|_|_|    |_|_ _|    |_ _|_|
    Three horizontal dimers:
        _ _ _      _ _ _
       |_ _|_|    |_|_ _|
       |_|_ _|    |_ _|_|
       |_ _|_|    |_|_ _|

Crossrefs

Sequence in context: A332476 A179651 A139560 * A363710 A380272 A105080

Adjacent sequences: A192092 A192093 A192094 * A192096 A192097 A192098

Keyword

tabf,nonn

Author

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 14 2011

Status

approved