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 (P) - strongly prime rectangle (which cannot be divided into two or more number of rectangles tileable by this set).

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

Red number (C) - 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 \ h123456789N>0
10
200
3022P0
40044C0
500000
6044C88C1818C7272C162162C
700000520520C0
8001616C0015141514C00
9088C08888C384384P43124312C2265622656C204184204184C11936001193600C
10003232C001324213242C0095671929567192C3k
11000003908839088C006311225663112256C3k
1201616C6464C468468C85448544C118586118586C17953601795360C2998608229986082C467966840467966840Call
1300000361712361712C003.24512857×10¹⁰3245128576C3k
1400128128C0011039461103946C002.33784892×10¹¹23378489272C3k
1503232C026722672C7680076800C34036243403624C115363072115363072C4.58156736×10¹⁰4581567368C1.64476126×10¹²164476126080Call
1600256256C001051313010513130C001.17486514×10¹³1174865141560C3k
17000003261469632614696C008.30740936×10¹³8307409362688C3k
1806464C512512C1607216072C11685121168512C101530170101530170C7.87612060×10¹⁰7876120608C7.11447492×10¹²711447492552C5.91419142×10¹⁴59141914295736Call
1900000316770752316770752C004.19170532×10¹⁵419170532284992C3k
200010241024C00990771834990771834C002.97940610×10¹⁶2979406105076728C3k
210128128C0100064100064C1278566412785664C3.10428316×10¹⁰3104283168C5.27256809×10¹²527256809600C1.11031728×10¹⁵111031728433824C2.11388889×10¹⁷21138888919470784Call
220020482048C009.74113357×10¹⁰9741133578C001.50150768×10¹⁸150150768205273752C3k
23000003.06067190×10¹¹30606719000C001.06576776×10¹⁹1065767764719498688C3k
240256256C40964096C636368636368C170678784170678784C9.62638129×10¹¹96263812906C3.55228145×10¹⁴35522814546496C1.73516969×10¹⁷17351696917388772C7.56823422×10¹⁹7568234227478522808Call
25000003.03028237×10¹²303028237848C00≥1.18446744×10²¹≥118446744073709551615C3k
260081928192C009.54563802×10¹²954563802106C00≥1.84467440×10²⁰≥18446744073709551615C3k
270512512C040979844097984C2.01464832×10¹⁰2014648320C3.00866517×10¹³3008665176560C2.38825760×10¹⁶2388257605782016C2.71264398×10¹⁹2712643984776742592C≥1.84467440×10²⁰≥18446744073709551615Call
28001638416384C009.48737771×10¹³9487377712634C00≥1.84467440×10²⁰≥18446744073709551615C3k
29000002.99284072×10¹⁴29928407213328C00≥1.84467440×10²⁰≥18446744073709551615C3k
30010241024C3276832768C2657948826579488C2.56332318×10¹¹25633231872C9.44400708×10¹⁴94440070803210C1.60678147×10¹⁸160678147466414272C≥1.84467440×10²⁰≥18446744073709551615C≥1.84467440×10²⁰≥18446744073709551615Call
31000002.98084427×10¹⁵298084427619272C00≥1.84467440×10²⁰≥18446744073709551615C3k
32006553665536C009.41048775×10¹⁵941048775198442C00≥1.84467440×10²⁰≥18446744073709551615C3k
33020482048C0173093760173093760C3.11423852×10¹²311423852544C2.97138080×10¹⁶2971380802436232C1.08076633×10²⁰10807663334085120512C≥1.84467440×10²⁰≥18446744073709551615C≥1.84467440×10²⁰≥18446744073709551615Call
3400131072131072C009.38348575×10¹⁶9383485753144122C00≥1.84467440×10²⁰≥18446744073709551615C3k
35000002.96359421×10¹⁷29635942157481248C00≥1.84467440×10²⁰≥18446744073709551615C3k
N>0x3k2k3k3kall3k3kall

Smallest prime reptiles

Smallest prime reptile (3Lx2):

Reptile tilings' solutions count (including symmetric)

polyomino \ n²
L triomino11P4P409C108388P104574902C≥15397007360P

Smallest tori tilings

Smallest torus (2x3):

Smallest square torus (3x3):

Smallest odd torus (3x3):

Tori tilings' solutions count (including translations)

w \ h123456789
100
20000
30024241212
4000010810800
5000060600000
6001921925645642736273613620136206974469744
70000252252000035658035658000
80000310831080000≥500000≥5000000000
90015361536102010207776077760≥500000≥500000≥500000≥500000≥500000≥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