[seqfan] Re: Tatami

[zbi74583.boat at orange.zero.jp]

    Hi,Seqfans


    I think that most of mathematicians don't know what "Tatami Sequence" is

    So,I asked my friend who obtained the formula to write an explanation of how
to compute it

    I copied it



    Yasutoshi





> -------------------------------------------
> (Mar. 6, 2016)
>
> ********CONTENTS********
> 1.INTRODUCTION
> 2.BASIC IDEA TO OBTAIN S(n)
> 3.METHOD OF COMPUTATION
> 4.SUMMARY
>
> ****1.INTRODUCTION****
> Let S(n) be the number of ways to tile a 3xn (n:odd number) room with a
monomer
> and dimers under the following rule:
> [R] At most three Tatami mats meet at a point.
> Here, monomer is a 1x1 Tatami mat, and a dimer is a 1x2 or 2x1 Tatami mat.
> Note that only one monomer is used. This restriction comes from traditional
way
> of Japanese Tatami tiling.
>
> Let us say that the room has 3 rows and n columns.
>
> In the following we show that S(n) is expressed as shown in the following
page:
> http://list.seqfan.eu/pipermail/seqfan/2016-February/016160.html
>
> Let us have some terminologies.
> A "block" is a subset of Tatami mats which tile 3xk (k<n) room of rectangular
> shape.
> If a block has k columns, that is, the block is a rectangle with 3 rows and k
> columns, we call the block "a 3xk block".
>
> Examples:
> (B1) A 3x1 block is composed of a monomer and a dimer, which are in the same
> column. There are two 3x1 blocks, which are vertically symmetric each other.
>
> (B2) A 3x3 block is composed of a monomer and 4 dimers. There are two types of
> 3x3 blocks, one which has a monomer in its center, and one which has a monomer
> in its corner (vertex). Let us call the first type "type C" because it has
> monomer at its center, and the second type "type V" because it has monomer at
> its vertex.
> There are 2 ways to tile the "type C", clockwise and counter clockwise, and 4
> ways to tile the "type V". Note that, for the "type V", one can extend tiling
> for only one columnar direction  because of the rule [R].
>
> (B3) A 3x2 block is composed of 3 dimers. This block occupies 2 columns. One
> dimer lies in the top or bottom row. The other two dimers are put to make a
2x2
> square and aligned perpendicular to the previous one. If all the three dimers
> are set in parallel, then no Tatami mat can be put in the next of this block
> because of the rule [R].  There are 2 types of 3x2 block.
>
> (B4) A 3x4 block is composed of 6 dimers. This block occupies 4 columns.  One
> way of tile the 3x4 block is first to put two dimers in the bottom row, then
put
> two dimers at the vertical edges of the 2x4 room, then fill the rest of the
> space by two dimers. There are 2 types of 3x4 block.
>
>
> In the next section we explain the basic idea to obtain S(n). Then we explain
> the method of computation in detail.
>
>
> ****2.BASIC IDEA TO OBTAIN S(n)****
> Suppose the monomer is included in a 3xq block. Number of ways of such  tiling
> is expressed as
>
> MxN, where M=[number of ways to tile a block of 3xq (which include the
monomer)]
> and N=[number of ways to tile the rest of the room] -------(1)
>
> One can show the following:
> (i) q, the number of columns of the block which include the monomer, is 1 or
3.
> (ii) The rest of the room is tiled by combination of  3x2 blocks (made of 3
> dimers) and 3x4 blocks  (made of 6 dimers).
>
> Both (i) and (ii) results from the rule [R].
>
>
> Let us write
>
> S1(n) = number of ways to tile the 3xn room with q=1, i.e., the monomer is
> included in a 3x1 block  ,   -------(2)
>
> and
>
> S3(n) = number of ways to tile the 3xn room with q=3, i.e., the monomer is
> included in a 3x3 block  .   -------(3)
>
> Thus we have
> S(n) = S1(n) + S3(n) --(4).
>
>
>
>
> ****3.METHOD OF COMPUTATION****
> We compute S1(n) and S3(n) using the equation (1).
> The first part "M" in the equation (1) is counted by, say, directly writing
down
> the tiling.
> The second part "N" is counted by combinatorial method.
> The rest of the room is made of 3 rows and n-q columns. Suppose the number of
> 3x2 and 3x4 blocks we use to tile the rest of the room is
> j and k,
> respectively.
>
> Remember that the rest of the room is tiled by combination of 3x2 blocks and
3x4
> blocks.Both blocks have two tiling patterns. Suppose we have a block and put
> another block at its right side. Then  one of the two types of the blocks
> satisfies the rule [R] for both 3x2 blocks and 3x4 blocks. Hence, in the
tiling
> of the rest of the room, the number of specifying 3x2 or 3x4 blocks is equal
to
> the ways of tiling the rest of the room.
>
> Now we consider the ways to specify how we choose 3x2 and 3x4 to fill the rest
> of the room.
>
> Since a 3x2 block occupies 2 columns and a 3x4 block occupies 4 columns, one
> have
> n-q = 2*j + 4*k    , ----(5)
> that is,
> (n-q)/2-k = j+k  . ----(6)
>
> Using this equation one can calculate the way of tiling as follows:
> 1. Specify q as  1 or 3
> 2. Specify k, the number of 3x4 block to tile the rest of the room
>
> Then, from (6) we see that the value of N in equation (1) is the way to select
k
> from (n-q)/2-k, that is,
>
> N=C[(n-q)/2-k,l] = ((n-q)/2-k)!/(k!*((n-q)/2-2*k)!)  .  ----(7)
>
> Having determined the sequence of 3x2 and 3x4 blocks, the whole tiling is
> determined by putting the 3xq block which contain the monomer in the sequence
of
> 3x2 and 3x4.
>
>
> From equation (5) we see that The range of k, the number of 3x4 blocks is
> k=0,1,...,[(n-q)/4], where [i]=Floor[i] ----(8)
>
>
>
> **3.1 CALCULATION OF S1(n) (q=1)**
> There are two way to put 3x1 block: the monomer is in the top row or in the
> bottom row. For each 3x1 block, the number of  ways to put the 3x1 block in
the
> sequence of 3x2 and 3x4 blocks is
> (n-q)/2-k +1  = (n-1)/2-k +1 = (n+1)/2-k ----(9)
> where  k is the number of 3x4 blocks.
>
> Using (1),(7),(8),(9), we have
>
> S1(n)=2*(  Sum_{0<=k<=[(n-1)/4]} ((n+1)/2-k)*C[(n-1)/2-k,k]  )
>      =2*(  Sum_{0<=k<=[(n-1)/4]} (n+1)/2-k)*((n-1)/2-k)!/(k!*((n-1)/2-2*k)!)
)
> ----(10)
>
>
> **3.2 CALCULATION OF S3(n) (q=3)**
> Now let us calculate S3(n), when the monomer is included in 3x3 block (q=3).
In
> this case S3(n) is calculated as
> S3(n) = S3c(n) + S3v(n) ,  ----(11)
> where
> S3c(n) = number of the ways to tile the room when q=3 and 3x3 block is "type
C"
> ---(12)
> and
> S3v(n) = number of the ways to tile the room when q=3 and 3x3 block is "type
V"
> ---(13)
>
> Let us consider when the 3x3 block which contains the monomer  is "type C",
that
> is, monomer is at the center of 3x3 block. In this case, calculation is quite
> similar to S1(n). In this case the number of ways to put 3x3 block in the
> sequence of 3x2 and 3x4 blocks is
> (n-q)/2-k +1  = (n-3)/2-k +1 = (n-1)/2-k ----(14)
> we have
> S3c(n)=2*(  Sum_{0<=k<=[(n-3)/4]} ((n-1)/2-k)*C[(n-1)/2-k,k]  ) . ----(15)
>
> Let us consider when the 3x3 block which contains the monomer is "type V",
that
> is, monomer is at the vertex (corner) of the 3x3 block. In this case, the
> sequence of 3x2 and 3x4 blocks can be put at only one columnar side of the 3x3
> block and one cannot put 3x3 block in between the 3x2 and 3x4 blocks, because
of
> the rule [R]. Since there are 4 type V 3x3 blocks, we have
> S3v(n)=4*(  Sum_{0<=k<=[(n-3)/4]} C[(n-1)/2-k,k]  ) . ----(16)
>
> Substituting (15) and (16) into (11), we have
>
> S3(n) = 2*(  Sum_{0<=k<=[(n-3)/4]} ((n+3)/2-k)*C[(n-1)/2-k,k]  ) . ----(17)
>
>
> ****4.SUMMARY****
> Let us summarize the results.
> Let S(n) be the number of ways to tile a 3xn (n:odd number) room with a
monomer
> and dimers under the following rule:
> [R] At most three Tatami mats meet at a point.
> Here, monomer is a 1x1 Tatami mat, and a dimer is a 1x2 or 2x1 Tatami mat.
> Then we have
>
> S(n)=S1(n)+S3(n),
> where
> S1(n)=2*(  Sum_{0<=k<=[(n-1)/4]} (n+1)/2-k)*((n-1)/2-k)!/(k!*((n-1)/2-2*k)!)
)
> ----(10)
> and
> S3(n) = 2*(  Sum_{0<=k<=[(n-3)/4]} ((n+3)/2-k)*C[(n-1)/2-k,k]  ) . ----(17)
>
> -------------------------------------------
>