Smallest Baiocchi figures¶
Smallest Baiocchi figure (area 12):
Formulas¶
$N(w; h)$ - number of ways to tile $w\times h$ rectangle (including symmetric solutions)
$T(w; h) = \begin{cases} 1, & N(w; h) \geq 1 \\ 0, & \text{else} \end{cases}$ - tileability function, $1$ if tiles rectangle, $0$ otherwise
$A(w; h) = \left(N(w; h)\right)^{\frac{1}{wh}}$ - average number of ways to tile cell in $w\times h$ rectangle (including symmetric solutions)
$G(T; x; y) = \sum_{w=1}^{\infty}\sum _{h=1}^{\infty}T(w; h)x^wy^h$ - bivariate generating function of $T(w; h)$
$G(A; x; y) = \sum_{w=1}^{\infty}\sum _{h=1}^{\infty}A(w; h)x^wy^h$ - bivariate generating function of $A(w; h)$
$N(1; n) = T(1; n) = 0, \qquad n \geq 1 \tag{1}$
"L" triomino has width and height of $2$ thus it does not fit into $1 \times n$ rectangle. Q.E.D.
$N(3n + 1; 3m + 1) = T(3n + 1; 3m + 1) = 0, \qquad n,m \geq 0 \tag{2}$
$N(3n + 1; 3m + 2) = T(3n + 1; 3m + 2) = 0, \qquad n,m \geq 0 \tag{3}$
$N(3n + 2; 3m + 2) = T(3n + 2; 3m + 2) = 0, \qquad n,m \geq 0 \tag{4}$
Area of rectangle should be divisible by triomino area. Since $(3n + 1)(3m + 1)\equiv 1\pmod{3}$, $(3n + 1)(3m + 2)\equiv 2\pmod{3}$, $(3n + 2)(3m + 2)\equiv 1\pmod{3}$, neither of those rectangles can be tiled by "L" triomino. Q.E.D.
$N(2; n) = 2 \times N(2; n - 3), \qquad n \geq 4 \tag{5}$
If triomino tiles $2 \times n$ rectangle then all rectangle cells should filled. Top left corner (marked with dot on image) may be covered in only three ways. Only two of them are valid, because third leaves untileable hole (marked with cross on image). When placing next triomino in remaining two tilings, a $2 \times 3$ rectangle is covered. Remaining part is a $2 \times (n - 3)$ rectangle. So whole rectangle can be tiled in $2 \times N(2; n - 3)$ ways. Q.E.D.
$N(3; n) = 2 \times N(3; n - 2), \qquad n \geq 3 \tag{6}$
$N(3; 2n + 1) = T(3; 2n + 1) = 0, \qquad n \geq 0 \tag{7}$
First, prove $(6)$. If triomino tiles $3 \times n$ rectangle then all rectangle cells should filled. Top left corner (marked with dot on image) may be covered in only three ways. Only two of them are valid, because third leaves untileable hole (marked with cross on image). When filling other corner on remaining two tilings, a $2 \times 3$ rectangle is covered. Remaining part is a $3 \times (n - 2)$ rectangle. So whole rectangle can be tiled in $2 \times N(3; n - 2)$ ways. Q.E.D.
Second, prove $(7)$. Assume that triomino tiles $3 \times (2n + 1)$ rectangle. Applying formula $(6)$ $n$ times, $N(3; 2n + 1) = N(3; 2n + 1 - 2 \times n) = N(3; 1) = N(1; 3) = 0$, with final step by formula $(1)$. Contradiction, therefore triomino does not tile $3 \times (2n + 1)$ rectangle. Q.E.D.
$N(4; n) = 10 \times N(4; n - 3) - 22 \times N(4; n - 6) - 4 \times N(4; n - 9), \qquad n \geq 10 \tag{8}$
$G(N(4); x) = \frac{1 - 6x^3}{1 - 10x^3 + 22x^6 + 4x^9} \tag{9}$
$G(N(5); x) = \frac{1 - 2x^3 - 31x^6 - 40x^9 - 20x^{12}}{1 - 2x^3 - 103x^6 - 280x^9 - 380x^{12}} \tag{10}$
$G(N(6); x) = \frac{1 - 2x - 4x^2 - 2x^3 + 13x^4 + 6x^5 - 6x^6 - 6x^7}{1 - 2x - 8x^2 - 2x^3 + 43x^4 + 42x^5 - 36x^6 - 102x^7 + 44x^9 + 8x^{10} + 8x^{11}} \tag{10}$
$G(T; x; y) = \frac{x^2 y^2 \left(x^2 y+x y^2+x y+x+y\right)}{\left(1-x^3\right) \left(1-y^3\right)}-\frac{x^3 y^3 \left(1-x^2 y^2\right)}{\left(1-x^2\right) \left(1-y^2\right)} = \\ = \frac{x^9 y^9+x^9 y^7+x^9 y^5+x^7 y^9+x^7 y^6+x^6 y^7+x^6 y^6+x^6 y^5+x^6 y^4+x^6 y^3+x^6 y^2+x^5 y^9+x^5 y^6+x^4 y^6+x^4 y^3+x^3 y^6+x^3 y^4+x^3 y^2+x^2 y^6+x^2 y^3}{\left(1-x^6\right) \left(1-y^6\right)} \tag{11}$
Attributions¶
- Prime rectangles first have been found by Michael Reid (http://www.cflmath.com/~reid/Polyomino/l3_rect.html).
- Smallest rectangle first have been found by Michael Reid.
- Smallest odd rectangle first have been found by David A. Klarner, Packing a Rectangle with Congruent N-ominoes, "Journal of Combinatorial Theory 7" (1969) pp. 107-115. (http://www.sciencedirect.com/science/article/pii/S002198006980044X)