POLYOMINO TILINGS

Polyomino Tilings

Select polyominoes for a set (currently 1 or 2), for which tilings should be shown.

Then click "Show" button.

You may also see list of all polyomino sets for which data is available here.


L triomino

Area: 3.

Perimeter: 8.

Size: 2x2.

Is rectangular: no.

Is convex: yes.

Holes: 0.

Order: 2.

Square order: 12.

Odd order: 15.

Prime rectangles: 2.

Smallest rectangle tilings

Smallest rectangle (2x3):

Smallest square (6x6):

Smallest odd rectangle (5x9):

Rectangle tilings' solutions count (including symmetric)

Blue number - strongly prime rectangle (which cannot be divided into two or more number of rectangles tileable by this set).

Green number - weakly prime rectangle (which cannot be divided into two rectangles tileable by this set, but which can be divided into three or more rectangles).

Purple number - prime rectangle (unknown if weakly or strongly prime).

Red number - composite rectangle (which can be divided into two rectangles tileable by this set).

Gray number - it is unknown whether rectangle is prime or composite.

Question mark (?) - solution count is unknown.

Click on underlined numbers to view picture with one solution.

w \ h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
N>0
1
0
2
0
0
3
0
2
0
4
0
0
4
0
5
0
0
0
0
0
6
0
4
8
18
72
162
7
0
0
0
0
0
520
0
8
0
0
16
0
0
1514
0
0
9
0
8
0
88
384
4312
22656
204184
1193600
10
0
0
32
0
0
13242
0
0
9567192
0
11
0
0
0
0
0
39088
0
0
63112256
0
0
12
0
16
64
468
8544
118586
1795360
29986082
467966840
≥1
≥1
≥1
13
0
0
0
0
0
361712
0
0
3.24512857×10¹⁰
0
0
≥1
0
14
0
0
128
0
0
1103946
0
0
2.33784892×10¹¹
0
0
≥1
0
0
15
0
32
0
2672
76800
3403624
115363072
4.58156736×10¹⁰
1.64476126×10¹²
≥1
≥1
≥1
≥1
≥1
≥1
16
0
0
256
0
0
10513130
0
0
1.17486514×10¹³
0
0
≥1
0
0
≥1
0
17
0
0
0
0
0
32614696
0
0
8.30740936×10¹³
0
0
≥1
0
0
≥1
0
0
18
0
64
512
16072
1168512
101530170
7.87612060×10¹⁰
7.11447492×10¹²
5.91419142×10¹⁴
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
19
0
0
0
0
0
316770752
0
0
4.19170532×10¹⁵
0
0
≥1
0
0
≥1
0
0
≥1
0
20
0
0
1024
0
0
990771834
0
0
2.97940610×10¹⁶
0
0
≥1
0
0
≥1
0
0
≥1
0
0
21
0
128
0
100064
12785664
3.10428316×10¹⁰
5.27256809×10¹²
1.11031728×10¹⁵
2.11388889×10¹⁷
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
all
22
0
0
2048
0
0
9.74113357×10¹⁰
0
0
1.50150768×10¹⁸
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
23
0
0
0
0
0
3.06067190×10¹¹
0
0
1.06576776×10¹⁹
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
24
0
256
4096
636368
170678784
9.62638129×10¹¹
3.55228145×10¹⁴
1.73516969×10¹⁷
7.56823422×10¹⁹
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
all
25
0
0
0
0
0
3.03028237×10¹²
0
0
≥1.18446744×10²¹
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
26
0
0
8192
0
0
9.54563802×10¹²
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
27
0
512
0
4097984
2.01464832×10¹⁰
3.00866517×10¹³
2.38825760×10¹⁶
2.71264398×10¹⁹
≥1.84467440×10²⁰
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
all
28
0
0
16384
0
0
9.48737771×10¹³
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
29
0
0
0
0
0
2.99284072×10¹⁴
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
30
0
1024
32768
26579488
2.56332318×10¹¹
9.44400708×10¹⁴
1.60678147×10¹⁸
≥1.84467440×10²⁰
≥1.84467440×10²⁰
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
all
31
0
0
0
0
0
2.98084427×10¹⁵
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
32
0
0
65536
0
0
9.41048775×10¹⁵
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
33
0
2048
0
173093760
3.11423852×10¹²
2.97138080×10¹⁶
1.08076633×10²⁰
≥1.84467440×10²⁰
≥1.84467440×10²⁰
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
≥1
all
34
0
0
131072
0
0
9.38348575×10¹⁶
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
35
0
0
0
0
0
2.96359421×10¹⁷
0
0
≥1.84467440×10²⁰
0
0
≥1
0
0
≥1
0
0
≥1
0
0
3k
N>0
x
3k
2k
3k
3k
all
3k
3k
all
3k
3k
all
3k
3k
all
3k
3k
all
3k
3k

Smallest prime reptiles

Smallest prime reptile (3Lx2):

Reptile tilings' solutions count (including symmetric)

polyomino \ n²
L triomino
1
1
4
409
108388
104574902
≥15397007360

Smallest tori tilings

Smallest torus (2x3):

Smallest square torus (3x3):

Smallest odd torus (3x3):

Tori tilings' solutions count (including translations)

w \ h
1
2
3
4
5
6
7
8
9
1
0
2
0
0
3
0
24
12
4
0
0
108
0
5
0
0
60
0
0
6
0
192
564
2736
13620
69744
7
0
0
252
0
0
356580
0
8
0
0
3108
0
0
≥500000
0
0
9
0
1536
1020
77760
≥500000
≥500000
≥500000
≥500000
≥500000

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

  1. Prime rectangles first have been found by Michael Reid (http://www.cflmath.com/~reid/Polyomino/l3_rect.html).
  2. Smallest rectangle first have been found by Michael Reid.
  3. 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)

See Also

I triominoTetrominoes