Generating function for number of different tessellation checkered rectangle

Question

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$.

Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$.

$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ Example tiling for $R_9$.

We assume the same tilings $A'$ and $A''$ if $A' = G_1 \circ \ldots \circ G_k \circ A''$, $G_1,\ldots,G_k$ are reflections about both axes of symmetry $R_n$.

I want to find generating function for $a_n$, $a_0 = 1$, $a_1 = 0$.

Also posted in https://mathoverflow.net/questions/223833/generating-function-for-number-of-different-tessellation-checkered-rectangle.

Thank you for any help!

Answer 1

mercio's technique (a.k.a. "transfer-matrix method", "dynamical programming") works but is overkill for this question. Here's a simpler way to get the generating function $$ A(x) = \sum_{n=0}^\infty a_n x^n = \frac{(1-X)^2}{1-5X+3X^2-X^3} $$ where $X=x^3$ (a natural substitution because clearly $a_n = 0$ unless $n$ is a multiple of $3$).

For $m=1,2,3,\ldots$, say that a $3m \times 4$ rectangle tiled by $1 \times 3$'s is prime if it does not decompose into tiled $3m_1 \times 4$ and $3m_2 \times 4$ rectangles for any positive $m_1, m_2$ with $m_1 + m_2 = m$. These "primes" are easy to enumerate: there are $3$ for $m=1$, and $2m$ for each $m \geq 2$; the generating function for these counts, call it $p(X)$, is elementary: $$ p(X) = 3X + 4X^2 + 6X^3 + 8X^4 + 10X^5 + \cdots = \frac{3X-2X^2+X^3}{(1-X)^2}. $$ Now every tiled $3m \times 4$ rectangle decomposes uniquely into prime tiled rectangle. Hence the desired generating function $A = \sum_{n=0}^\infty a_n x^n = \sum_{m=0}^\infty a_{3m} X^m$ is $1/(1-p)$. (This can be seen either by writing $A = 1 + pA$ and solving for $A$, or recognizing $p^k$ ($k=0,1,2,\ldots$) as the generating function for tilings that decompose into $k$ primes and summing over $k$.) Simplifying the fraction $1/(1-p)$ yields $A = (1-X)^2 / (1-5X+3X^2-X^3)$ as claimed.

The count of tilings of the $3m \times 4$ rectangle up to symmetry is then just over $a_{3m}/4$. The formula for the generating function was exhibited by Michael Stoll in his answer to the parallel Mathoverflow question. As mercio explained, it can be obtained by expressing, for each possible symmetry class, the number of $3m \times 4$ tilings with that symmetry in terms of the known $a_n$. There is a unique tiling symmetrical about the horizontal axis, and it is symmetrical about the vertical axis too. So it remains to count all tilings symmetrical about the vertical axis. If $n$ is even the count is just $a_{n/2}$. If $n$ is odd, we get a tiling by choosing some $m' < m/2$, tiling a $3m'\times 4$ rectangle arbitrarily, and inserting a symmetrical prime tiling of the $3(m-2m') \times 4$ rectangle between the $3m'\times 4$ tiing and its reflection. The number of symmetrical primes is $3$ for the $3 \times 4$ and $2$ for each of $9 \times 4$, $15 \times 4$, $21 \times 4$, $27 \times 4$ etc.; the generating function for the sequence $3, 2, 2, 2, 2, \ldots$ is also elementary, and we soon recover Michael Stoll's formula.

Once we have obtained the sequence $a_{3m} = 1, 3, 13, 57, 249, \ldots$ for $m=0,1,2,3,4,\ldots$ it is easy to find it on the OEIS: it is sequence A049086, with generating function attributed to "Colin Barker, Feb 03 2012". The OEIS entry also gives a reference to this recent arXiv preprint, which tabulates the $a_n$ in the second column of Table 19 (bottom of page 14) and gives (but apparently does not prove) the generating function as Theorem 14 (page 12). The enumeration of the symmetry classes, up to the 8210019 tilings of the $36 \times 4$, is given in the second column of Table 26 (top of page 19), but no generating function is exhibited.

Answer 2

Count all the way to tile a rectangle without identifying symmetric patterns first.

For each subset $S$ of a $4 \times 2$ rectangle, consider the number $a_{S,n}$ of ways to tile a $4 \times n$ rectangle with the squares in $S$ removed on the left border of the rectangle. Focus on the squares that are still on the leftmost column, consider all the ways to fill those (it might be impossible because of the choice of $S$). After covering the leftmost column in any manner, you are left with a rectangle $4 \times (n-1)$ to cover with another set $S'$ of missing squares on its two leftmost columns.

Hence you have a big chunk of relationships like $a_{S,n} = \sum c_{S,S'} a_{S',n-1}$ where the $c_{S,S'}$ are integers.

Now if you're clever you don't need to consider all possible subsets $S$, because starting from a clean rectangle, there are only $15$ reachable states, and with symmetry considerations, you can bring this number down to $9$ ($a_{S,n} = a_{S',n}$ if $S'$ is $S$ flipped upside down).

All of this means that there is a matrix $M \in M_9(\Bbb Z)$ such that $a_n$ is a certain coefficient of $M^n$ (the number of ways to get from a clean left border to a another clean left border $n$ columns later)

Let $P(T)$ be the characteristic polynomial of $M$. Then $P(M)=0$, hence if $f(T) = \sum a_n T^n$, in $f(T) P(1/T)$, every coefficient of $T^k$ for $k \ge 0$ has to vanish, and so $f(T) = Q(T)/ (T^9 P(1/T))$ where $Q$ is a polynomial of degree $8$ (or less).

Next you want to count the ways to tile the rectangle that are invariant by symmetry along an axis or by the rotation (or all three).

Counting the number $b_n$ of rectangles invariant by symmetry along the horizontal axis is pretty easy since they consist of horizontal tiles, and then the tiling is also invariant by the other two transformations. This gives you the generating function $\sum b_nT^n = 1/(1-T^3)$

To count the other two categories $c_n,d_n$, you use the same matrix but you start from the middle of the rectangle. This will give you two generating functions of the form $R(T)/T^{18}P(1/T^2)$ with $R$ of degree at most $17$ (hopefully, I'm not completely sure on that)

Since you're interested in the generating function of $A_n = (a_n-b_n-(c_n-b_n)-(d_n-b_n))/4 + (c_n-b_n)/2 + (d_n-b_n)/2 + b_n$,

you should end up with a generating function of the form $Q/T^{27}(1-T^3)P(1/T)P(1/T^2)$ with some polynomial $Q$ of degree less than $30$.

Now you can write down $M$ and compute its characteristic polynomial then brute force $a_n$ for $n=0 \ldots 7$ and $b_n,c_n$ for $n = 0 \ldots 16$ or so to get the smaller numerators, then combine everything.