[seqfan] Re: Tatami

[Neil Sloane]

Very interesting.  So could you give the first 20 terms (say) of S1(n),
S3(n) and S(n) ?


Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Wed, Mar 23, 2016 at 11:21 PM, <zbi74583.boat at orange.zero.jp> wrote:

>     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)
> >
> > -------------------------------------------
> >
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>