tiling a 2xn checkerboard with square tetrominoes and dominoes

[Jonathan Post]

The generating functions are lovely.

I was not aware of the S. Heubach citation.

Joshua Zucker and I earlier found the Jacobstahl connection, in two
different ways for two different sets of allowed tiles. We'll submit
that as a comment.

We also found as a comment that A005320  a(n) = 4a(n-1) - a(n-2)
enumerates 3xn tilings into dominoes.

Joshua Zucker and I are collating our notes on enumerations of 3xn
rectangles into 3x3 square nonominoes, 2x2 square tetrominoes and
dominoes (which break the squares-only pattern).

So your lovely "triangle" sequence and our comment on A005320, and a
new sequence of 3xn covered by 2x2 and 3x3 squares and dominoes (when
we submit) are all properly cross-referenced.

Thank you again!




Hello seqfans,

I would like to mention that the domino tiling of 2 by 2n rectangle and 3 by 2n rectangle are specialized cases of domino tiling of a star graph and an even path graph.

The general statement is:
The number of domino tilings of S(d-1) × P(2n) (product of a star graph and a path graph) is equal to a(n), where a(n) = d * a(n-1) - a(n-2) and a(0) = 1, a(1) = d-1. 

Here is the proof that this number is the same as the number of 01-avoiding words of length n on alphabet {0,1,2, ..., d-1} which do not end in 0:

Let us start with noticing that if we want to tile a star graph with dominoes we can only put one domino and it has to include the center of the star. Let us associate the center of the star graph with 0 and associate other vertices with numbers from 2 to d-1. Let us associate the domino tilings of S(d-1) × P2 with a number. If all dominoes are parallel to the path P2, then we associate this tiling with one. Otherwise exactly two dominoes are not parallel to P2 and they connect the center of the star with the vertex number k (k ≥ 2) and we associate this tiling with k. Now we would like to correspond to a number a domino tiling of Sd-1 × P2m which cannot be decomposed into two smaller domino tilings of that type. It is easy to see that in this tiling there are only two dominoes that are not parallel to P2m: one domino in the first star and one domino in the last star. They both have to connect the center of the star with the same numbered vertex - suppose this number is k. Then we associate this tiling with the word "000...000k", where we have m-1 zeroes. If the tiling can be decomposed into the minimal ones than we concatenate all the words corresponding to minimal tilings together. This way we created a correspondence between domino tilings of Sd-1 × P2n and the number of 01-avoiding words of length n on alphabet {0,1,2, ..., d-1} which do not end in 0. 

Here is the proof that the number of 01-avoiding words of length n on alphabet {0,1,2, ..., d-1} which do not end in 0 is equal to a(n), where a(n) = d * a(n-1) - a(n-2) and a(0) = 1, a(1) = d-1.

Tanya



_________________________________________________________________
Need personalized email and website? Look no further. It's easy
with Doteasy $0 Web Hosting! Learn more at www.doteasy.com