How many ways are there to tile a rectangle with polyominoes? презентация

Enumerative combinatorics
Game problems
Partition and tiling problems
Monte Carlo method
Buffon’s needle
Galton board
Tiling of a plane
Graphs and polyominoes on a lattice

Random walks on a lattice
If some atoms fit into two squares with adjacent sides, a “spring” appears between them.
Percentage of draws
Number of springs

Example:
n1=2, n2=4, n3=2, n4=3
Generalize the results for:
three-dimensional space: d=3
lattice with holes
surface of a “g” kind containing the lattice
General case: different connection types
Aim:
finding the statistical weight for macrostates n1, n2, n3, n4
n1: a spring between an outer node of primitive 1 and an inner node of primitive 2
n2: a spring between an inner node of primitive 1 and an outer node of primitive 2
n3: a spring between an inner node of primitive 1 and an inner node of primitive 2
n4: a spring between an outer node of primitive 1 and an outer node of primitive 2

Statistical weight problem for a system of graphs embedded in square lattice
1
2
…
N
1
2
…
M
M x N nodes
M x N squares
N\M
2
1
…
1
2
…
(n1,n2,n3)=(6,2,4)

Applications in chemistry.
Thermodynamic Considerations for Polymer Solubility
where
W is the number of possible arrangements within the lattice,
k is the Boltzmann constant.
ΔS = k ln W
polymer solute
low molecular weight solute
Two-dimensional lattice model of solubility

Polyomino representation

1
2
12
13
14
123
124
1234
1235
1236
12345
12356
123456
1245
1246
125
134
1256
126
23
25
235
2356
6
5
1
4
2
3
0
1
6
5
1
4
2
3
0
2
6
5
4
3
0
12
6
5
4
0
123
5
3
0
1246
6
4
3
0
125
1
4
0
2356
0
123456
Enumerating polyomino configurations

From graphs to polyominoes
A polyomino is a plane geometric figure formed by joining equal squares.
A graph covering of a lattice is equivalent to a tiling of an area with polyominoes.
Suppose a (kxh)*(nxh) field, r monominoes and b L-minoes are given.
Enclose every polyomino into a hxh field and consider it as a whole.
The size of the initial field changes to kxn.

.
Polyomino adjacency cases
hxh field
Calculating the number of possible adjacencies (P) c is a number of pairs
a number of ways to place squares
not belonging to any pair

Direct method of counting partitions
Suppose a MxN stripe and a set of polyominoes are given.
Construct all the possible partitions of the stripe, where a monomino, that is 1x1 a square, is denoted by z, graphically.
Tiling of a 2x14 stripe with L-minoes and dominoes
Introduced methods

L-minoes and dominoes on a 2xn stripe
=
=

Calculation of infinite sums

Obtaining the generating function

Generating functions for some other partitions
1xn stripe
Domino
Triomino
Domino + Triomino
2xn stripe
Domino
Triomino
L-mino + Triomino
L-mino
3xn stripe
Domino
Triomino
n
n
n

Indirect method of counting partitions
#
#
#

. . .
n-1
n
. . .
n-2
n
j
. . .
n-j
j
. . .
n-j
n
n
. . .
n
2
2
1,
1
[ n=0 ]
[n=0]
1
Derivation of the generating function

Partitions of the 3xn field
11 partitions
9 results
2
2
2
,
,
multiplication

n=2
n=2
n=2
n=2
,
,
,
,
,
,
,
,
,
Partition of the 3x4 field
2
2

2
2

Kasteleyn’s formula for the number of perfect matchings in a planar graph G
Pfaffian method
Pfaffian orientation
Let A denote the signed adjacency matrix of G. This means that
• Aij = 0 if no edge joins vi to vj .
• Aij = 1 if the edge joining vi to vj is oriented from vi to vj .
• Aij = −1 if the edge joining vi to vj is oriented from vj to vi .
A perfect matching of G is a collection of edges e1, ..., en of G such that every vertex belongs to exactly one ej .
Let P(G) denote the number of distinct perfect matchings of G. Then
The matrix A is called skew-symmetric if Aij = −Aji for all i, j. A is skew-symmetric.
Let A be a 2n × 2n skew-symmetric matrix. The Pfaffian of A is defined as the sum taken over all permutations of the set {1, ..., 2n}.
Given Muir’s Identity, Kastelyn’s Theorem can be reformulated as follows.
Let G be a graph equipped with any Pfaffian orientation. Let A be the corresponding signed adjacency matrix. Then
Muir’s Identity
1
1 Kastelyn’s Formula for Perfect Matchings. Rich Schwartz
Ways to tile a MxN field with dominoes

4 binary operations:
3 unary operations:
– without forming a spring
– with forming a horizontal spring
– with forming a vertical spring
– with forming both horizontal and vertical springs
– mirroring
– rotation
– translation
Coloured digraphs method
χ
γ↑
γ
R
T
M

Properties of unary and binary operations

Relation between coloured graphs and partitions
T
γ↑
γ
R
χ
T
χ
γ
γ
χ
χ
T
T
χ
γ
χ
χ
γ
R
χ
γ↑
M

Tiling a rectangular m×n field
χ
R
χ
R
χ
n-1
n-1
n-1
m-1
χ
R
χ
R
χ
n-1
n-1
n-1
m-2
χ
n
T
χ
n-1
m-1
χ
n
T
The number of all possible partitions of a MxN field into arbitrary tiles is
2MN-M-N

Partitions of a MxN field into arbitrary tiles
M
N
M-1
N-1

Aims & perspectives
Algebraization of the tiling problem
Finding a method applicable to the whole class of similar problems
Cluster characterization (coloured digraphs method)
Forming clusters from different primitive sets
Distinguishing between clusters
Deriving the structural complexity of a cluster
Conclusion

Connection with modern art
Robert Delaunay.
City. 1910
Georges Braque.
Mandora.1909-10
Pablo Picasso.
Harlequin with Violin. 1918

Evolution of primitive geometric shapes
Searching for rhythmical structures – investigating adjacent/non-adjacent squares on a lattice
Paul Klee. Personal diaries, 1921-1931.
Investigating colour schemes

Musical combinatorics
Two full octaves of the 12-tone equal-tempered scale, in three different musical representations: Notes on the musical staff, letter names and keys on the piano keyboard.
The 12 musical notes repeat in a cyclic fashion, and therefore can be represented as 12 positions on a circle.
Michael Keith. From Polychords to Polya. Adventures in Musical Combinatorics. 1991. Vinculum Press, Princenton.

George Frideric Handel, Hallelujah Chorus, from Messiah (1741)
Ludwig van Beethoven, Piano Sonata Op. 79 (1808)
Claude Debussy, L’Apres-Midi d’un Faune (1892)
George Crumb, Makrocosmos Vol. 1 (1972)
Chords
Michael Keith. From Polychords to Polya. Adventures in Musical Combinatorics. 1991. Vinculum Press, Princenton.
is the number of n-note chords in a scale of L notes having exactly a adjacencies
Graphs of a(t) for excerpts from several compositions

Lattice model in music
1/4
The lattice you have seen at the beginning represents a fragment from Debussy’s “Mazurka”.
Here, the t-axis shows the note value. Red squares stand for the treble clef notes, blue squares – for the bass clef notes.
Here, we do not distinguish octaves.

Enumerative combinatorics
Game problems
Partition and tiling problems
Monte Carlo method
Buffon’s needle
Galton board
Tiling of a plane
Graphs and polyominoes on a lattice