3
$\begingroup$

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

enter image description here

$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ 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://math.stackexchange.com/questions/1533637/generating-function-for-number-of-different-tessellation-checkered-rectangle.

Thank you for any help!

$\endgroup$
  • 2
    $\begingroup$ Why are you considering reflected tilings as identical? Why not start with the count of all tlings oeis.org/A049086, then count the symmetric ones? $\endgroup$ – Douglas Zare Nov 17 '15 at 16:28
  • $\begingroup$ What is the relevance to machine learning? $\endgroup$ – Douglas Zare Nov 17 '15 at 16:48
  • 2
    $\begingroup$ As far as I can tell, given the OEIS reference I gave, this question is only an exercise, not research level, and because relatively few tilings are symmetric, the practical savings by excluding duplicates are negligible. $\endgroup$ – Douglas Zare Nov 17 '15 at 17:27
  • 1
    $\begingroup$ What is a checkered rectangle, and how does it differ from an uncheckered rectangle? $\endgroup$ – Gerry Myerson Nov 17 '15 at 22:53
  • 2
    $\begingroup$ Also posted to m.se, with no mention on either site. math.stackexchange.com/questions/1533637/… $\endgroup$ – Gerry Myerson Nov 19 '15 at 12:32
3
+50
$\begingroup$

It is clear that $a_n = 0$ unless $n$ is divisible by 3, so I let $b_n = a_{3n}$. According to the OEIS link provided by Douglas Zare in his comment above, we have (with a short calculation to obtain the numerator) $$ \sum_{n=0}^\infty c_n t^n = F(t) := \frac{1 - 2t + t^2}{1 - 5t + 3t^2 - t^3}, $$ where $c_n$ denotes the number of tesselations of a $4 \times 3n$-rectangle without identifying tesselations in the same orbit of the symmetry group.

Now we have to consider the possible symmetries. It is easy to see that the number of tesselations that are invariant under the rotation by 180 degrees is $c_{\lfloor n/2 \rfloor}$ (if $n$ is even, there can be no tile extending across the axis, so the tesselation is given by its left half; if $n$ is odd, the middle part of the tesselation has to consist of four horizontal tiles, and a similar argument applies).

The same is true for tesselations invariant under the reflection about the vertical axis when $n$ is even. When $n$ is odd, the middle part can consist of four horizontal tiles or of one vertical and one horizontal tile (at top or bottom). Denoting the number of tesselations of a $4 \times 3n$-rectangle with a vertical $1 \times 3$ rectangle removed at one end by $d_n$, we obtain $c_{(n-1)/2} + 2 d_{(n+1)/2}$ possibilities. The generating function of the $d_n$ can be fairly easily obtained from that for the $c_n$; it is $$ \sum_{n=0}^\infty d_n t^n = G(t) := \frac{t - t^2}{1 - 5t + 3t^2 - t^3}. $$

There is exactly one tesselation that has both (and therefore all) symmetries (the one with all tiles horizontal); it is also the only one that is symmetric with respect to the reflection about the horizontal axis.

So there is one orbit of size 1 and there are $2(c_{n/2} - 1)$ orbits of size 2 when $n$ is even and $2(c_{(n-1)/2} - 1 + d_{(n+1)/2})$ when $n$ is odd, so there must be $$ b_n = \frac{1}{4}(c_n + \#\text{(orbits of size 2)} + 3) = \frac{1}{4}(c_n + 1) + \frac{1}{2} c_{\lfloor n/2 \rfloor} \Bigl[+ \frac{1}{2} d_{(n+1)/2} \text{ if $n$ is odd}\Bigr]$$ orbits in total. Therefore $$ \sum_{n=0}^\infty b_n t^n = \frac{1}{4} \Bigl(F(t)+\frac{1}{1-t}\Bigr) + \frac{1}{2}\bigl((1 + t) F(t^2) + t^{-1} G(t^2)\bigr), $$ which is $$ \frac{1-4t-4t^2+20t^3-8t^4-13t^5+10t^6+t^7-3t^8+t^9}{(1-t)(1-5t+3t^2-t^3)(1-5t^2+3t^4-t^6)}. $$

$\endgroup$
  • $\begingroup$ I posted a proof of the formula for $F(t)$ to the parallel Math Stackexchange question (after accidentally posting it here and then deleting). $\endgroup$ – Noam D. Elkies Nov 23 '15 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.