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

Author

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

Keywords

• tabf
• nonn

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.

Examples

			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:
        _ _ _      _ _ _
       |_ _|_|    |_|_ _|
       |_|_ _|    |_ _|_|
       |_ _|_|    |_|_ _|
		

Links

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