JACODESMATH / ISSN 2148-838X

J. Algebra Comb. Discrete Appl.
1(1) • 19-27

Received: 18 May 2014; Accepted: 24 June 2014
DOI 10.13069/jacodesmath.09554

Journal of Algebra Combinatorics Discrete Structures and Applications

Horizontal runs in domino tilings

Research Article

Kamilla Oliver1∗, Helmut Prodinger2∗∗

1. 91502 Erlangen, Germany

2. Department of Mathematics, University of Stellenbosch 7602, Stellenbosch, South Africa

Abstract: We discuss tilings of a grid (of size n×2) with dominoes of size 2×1. Parameters that might be called
“longest run” are investigated, in terms of generating functions and also asymptotically. Extensions
are also mentioned.

2010 MSC: 05A15, 68R05

Keywords: Tiling, Generating function, Asymptotic, Bootstrapping, Mellin transform, Fibonacci numbers

1. Introduction

Donald Knuth [3] included tilings of an n × 2-rectangle using 2 × 1-sized tiles (“dominoes”) as an
introductory example of the use of generating functions. If Tn is the number of these tilings, then
Tn = Tn−1 + Tn−2, since we have two choices to start: one vertical domino, leaving an (n − 1) × 2-
rectangle, or two horizontal dominos, leaving an (n − 2) × 2-rectangle. Since T0 = 1 and T1 = 1, this
leads to Tn = Fn+1 (a Fibonacci number).

Here is one particular tiling of a 20 × 2-rectangle:

Denoting T the family (=set) of all tiled n× 2-rectangles, for n ≥ 0, then we can write a symbolic
equation:

T = + T + T

∗ E-mail: olikamilla@gmail.com,
This author did most of her research while visiting the University of Stellenbosch in September 2013. She thanks
the department of mathematics for its hospitality.
∗∗ E-mail: hproding@sun.ac.za,
This author was supported by an incentive grant of the NRF of South Africa.

19



Horizontal runs in domino tilings

With the generating function

T(z) :=
∑
n≥0

Tnz
n,

the symbolic equation translates directly into

T(z) = 1 + zT(z) + z2T(z) =
1

1 −z −z2
.

This equation is simple enough that, with partial fraction decomposition, one finds an explicit form

Tn =
1
√

5

[(
1 +
√

5

2

)n+1
−
(

1 −
√

5

2

)n+1]
.

The number

α :=
1 +
√

5

2

is called the golden ratio; it is one of the most important constants in mathematics. In terms of asympotics
it is dominating:

Tn ∼
1
√

5

(
1 +
√

5

2

)n+1
.

If one cannot resort to an explicit expression as above, one looks at the dominating singularity and writes

T(z) ∼
C

1 −αz
as z →

1

α
.

The constant C may be computed as

C = lim
z→ 1

α

1 −αz
1 −z −z2

=
α
√

5
.

In this paper, we are interested in the (consecutive) sequence of horizontal dominoes in a tiling. We
are looking for the longest substructure of the type in the figure.

We will indicate in Section 2 how the expected value of this parameter may be computed. Then, in
Section 3, we change our setting to tilings of n × 3 rectangles. Things become more involved, but it is
highly instructive to see how one has to deal with the difficulties. For more material of a similar type we
refer to [8].

2. The longest horizontal run in tilings of n×2-rectangles

As the first step of our analysis, we decompose a tiled rectangle according to (maximal) runs of
horizontal dominoes. We indicate this for the example from the introduction: We see here runs of 3, 1,
and 2 (stacked) horizontal dominoes. So our parameter is 3 for this example. Various runs of length 0 are

20



K. Oliver, H. Prodinger

not indicated. Based on this (unique!) decomposition, we introduce T <h, the family of tiled dominoes
where the (maximal) run parameter is < h, we find

T <h =
<h( <h)∗

.

For completeness, we mention that the ‘∗’ operator (Kleene’s star in language theory) produces sequences.
If A is a set, then A∗ = A0 ∪A1 ∪A2 ∪ ·· · , i.e., all sequences that can be formed from elements of A.
This operation is also useful when one deals with generating functions. If f(z) is the generating function
associated to A, so that the coefficient of zn (written as [zn]f(z)) counts the number of elements of size
n in A, then 1

1−f(z) is the generating function associated to A
∗. For general background we would like

to mention the book [2].

Here,

<h
=

h−1⋃
i=0

i
.

The lefthand side describes repetitions of with at most h− 1 elements; the righthand side splits the
repetitions into the various possibilities from i = 0, 1, . . . ,h − 1 . In terms of generating functions, the
last expression translates into

1 + z2 + z4 + · · · + z2(h−1) =
1 −z2h

1 −z2
.

Consequently, we get

T<h(z) =
1 −z2h

1 −z2
1

1 − z(1−z
2h)

1−z2
=

1 −z2h

1 −z −z2 + z2h+1
.

One can see from this that, as h → ∞, which means no more restrictions on the run lengths, we find
again the generating function

T(z) =
1

1 −z −z2
.

Further,

T≥h(z) := T(z) −T<h(z) =
1

1 −z −z2
−

1 −z2h

1 −z −z2 + z2h+1

=
1 −z2

1 −z −z2
z2h

1 −z −z2 + z2h+1
.

There is a dominant root ρh of 1 −z −z2 + z2h+1, which is close to 1/α. So we set ρh := 1/α + εh and
continue

1 −
1

α
−εh −

1

α2
−

2εh
α

+ α−2h−1 ∼ 0,

or

εh ∼
√

5α−2h−1.

21



Horizontal runs in domino tilings

We write

1 −z −z2 + z2h+1 ∼
(

1 −
z

ρh

)
C,

and find

C = lim
z→ρh

1 −z −z2 + z2h+1

1 − z
ρh

∼
√

5

α
.

Now we can read off coefficients:

[zn]T≥h(z) ∼
αn+1
√

5
− [zn]

α
√

5

1

1 −z/ρh

=
αn+1
√

5
−

α
√

5
ρ−nh

∼
αn+1
√

5
−

α
√

5

( 1
α

+
√

5α−2h−1
)−n

=
αn+1
√

5
−
αn+1
√

5

(
1 +
√

5α−2h
)−n

∼
αn+1
√

5
−
αn+1
√

5

(
1 −
√

5α−2h
)n

∼
αn+1
√

5
−
αn+1
√

5
e−
√
5n/α2h.

Normalization leads to

[zn]T≥h(z)

Tn
∼ 1 −e−

√
5n/α2h.

In order to compute the average value of our parameter, one has to sum this:∑
h≥1

(
1 −e−

√
5n/α2h

)
.

It is very well understood how to get asymptotics for

f(x) :=
∑
h≥1

(
1 −e−x/α

2h
)

as x →∞, see [1]. One computes the Mellin transform

f∗(s) =
∑
h≥1

α2hs · Γ(s) = −
α2s

1 −α2s
Γ(s),

valid in 〈−1, 0〉 (the fundamental strip). Then one employs the inversion formula

f(x) = −
1

2πi

∫ −1
2
+i∞

−1
2
−i∞

α2s

1 −α2s
Γ(s)x−sds,

shifts the line of integration to the right and takes the residues (with a negative sign) into account. The
contribution from the pole at s = 0 is

1

2
logα x +

γ

2 log α
−

1

2
.

22



K. Oliver, H. Prodinger

There is also a contribution coming from the simple poles at s = kπi
log α

:

−
1

2 log α

∑
k 6=0

Γ
( kπi

log α

)
e−kπi·logα x.

This is a periodic function of small amplitude. Such functions occur frequently when one analyses run
statistics, see [8]. Altogether we found for the average of our parameter the asymptotic formula

1

2
logα n +

1

4
logα 5 +

γ

2 log α
−

1

2
−δ(
√

5n),

with

δ(x) := −
1

2 log α

∑
k 6=0

Γ
( kπi

log α

)
e−kπix.

Let us emphasize that the paper [8] has many similar results, and concrete error terms and estimates
are worked out. Here, for the benefit of the reader, we suppress technical details and just stick to the
main ideas.

3. Tilings of n×3-rectangles

Let us start with an example of a 20 × 3-rectangle:

It decomposes in a natural way as follows:

Figure 1. Decomposition into blocks

The individual (maximal) blocks are of 3 types, as indicated in the figure:

Figure 2. First type

23



Horizontal runs in domino tilings

Figure 3. Second type

Figure 4. Third type

Again, we will look at

Figure 5. Maximal sequence of horizontal dominoes present (2 layers)

Let the three types with a sequence of exactly i horizontal (stacked) dominoes be denoted by F i,
G i, H i, then the family of dominoes with our run parameter < h can be described by

T <h =

(h−1⋃
i=0

F i
)[(h−1⋃

i=0

G i ∪
h−1⋃
i=0

H i
)(h−1⋃

i=0

F i
)]∗

.

In terms of generating functions (the variable z marks the length of the domino), we have the following:

h−1⋃
i=0

F i −→ 1 + z2 + · · · + z2(h−1) =
1 −z2h

1 −z2
,

h−1⋃
i=0

G i −→ z2 + · · · + z2h =
z2(1 −z2h)

1 −z2

and
h−1⋃
i=0

H i −→ z2 + · · · + z2h =
z2(1 −z2h)

1 −z2
.

Consequently

T<h(z) =
1 −z2h

1 −z2
1

1 − 2
z2(1 −z2h)

1 −z2
1 −z2h

1 −z2

=
(1 −z2)(1 −z2h)

1 − 4z2 + z4 + 4z2h+2 − 2z4h+2
.

24



K. Oliver, H. Prodinger

In the limit h →∞ (no restrictions), we find

T(z) =
1 −z2

1 − 4z2 + z4
,

which was already derived in [3] using a different method. These functions only depend on z2, which is
clear, since a tiled n× 3-rectangle is only possible for even n. Thus we set w := z2 and work with

R<h(w) =
(1 −w)(1 −wh)

1 − 4w + w2 + 4wh+1 − 2w2h+1

and

R(w) =
1 −w

1 − 4w + w2
.

There is a dominant root at w = 1/ρ with ρ = 2 +
√

3, and

R(w) ∼
3 −
√

3

6

1

1 −ρz
,

and so

[wn]R(w) ∼
3 −
√

3

6
ρn.

There is a dominant root ωh = 1ρ + εh of

1 − 4w + w2 + 4wh+1 − 2w2h+1.

One application of bootstrapping results in

εh =
2

√
3ρh+1

.

From a historical point of view, it is interesting to point out that this procedure appeared for the first
time in [6].

A computation that is analogous to the one in the previous section yields

[wn]T≥h(z) ∼
3 −
√

3

6
ρn −

3 −
√

3

6
ω−n

∼
3 −
√

3

6
ρn −

3 −
√

3

6

(1
ρ

+ εh

)−n
=

3 −
√

3

6
ρn −

3 −
√

3

6
ρn
(

1 +
2
√

3ρh

)−n
∼

3 −
√

3

6
ρn −

3 −
√

3

6
ρn
(

1 −
2
√

3ρh

)n
.

Normalization leads to
[wn]T≥h(z)

[wn]T(z)
∼ 1 −e−

2n√
3ρh .

To compute the average, we need to evaluate∑
h≥1

(
1 −e−x/ρ

h
)
,

with x = 2n/
√

3. The asymptotic evaluation is as before:

logρ n + logρ 2 −
1

2
logρ 3 +

γ

log ρ
−

1

2
−

1

log ρ

∑
k 6=0

Γ
(2kπi

log ρ

)
e−2πik·logρ(2n/

√
3 ).

25



Horizontal runs in domino tilings

4. The longest vertical run in tilings of n×2-rectangles

For completeness, we briefly discuss how one can attack the parameter “longest vertical run.”

We introduce T <h, the family of tiled dominoes where the (maximal) run parameter is < h, we find

T <h =
<h
(

<h
)∗
.

In terms of generating functions, this means

T<h(z) =
1 −zh

1 −z −z2 + zh+2
.

We set again ρh = 1/α + εh, and find

εh ∼
1
√

5

1

αh+2
.

Further,

[zn]T≥h(z)

Tn
∼ 1 −e

√
5n/αh+1.

The expected value is to be evaluated as ∑
h≥1

(
1 −e−x/α

k
)
,

with x =
√
5
α
n. The asymptotic evaluation is

logα n +
1

2
logα 5 +

γ

log α
−

3

2
−

1

α

∑
k 6=0

Γ
( 2kπi

log α

)
e−2πik·logα(n

√
5/α);

n refers to the length of the tiled rectangle.

The case of an n×3-rectangle and runs of vertical tiles can also be done, but is a bit more elaborate.
It leads to a similar type of result.

5. Conclusion

We have demonstrated how to deal with runlength parameters: First, symbolic equations lead to
explicit forms of the associated generating functions. Then, one identifies the dominant singularity and
finds an approximate expression for the coefficients. The average value that one wants to compute is then
asymptotically described by a series. To work out asymptotics for this sum, the Mellin transform [1, 2]
is used. This series of operations works also in other contexts. A few references for further reading
are [4, 5, 7].

References

[1] P. Flajolet, X. Gourdon, P. Dumas, Mellin transforms and asymptotics: Harmonic sums, Theoretical
Computer Science 144, 3-58, 1995.

26



K. Oliver, H. Prodinger

[2] P. Flajolet, R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009.
[3] R. Graham, D. E. Knuth, O. Pathasnik, Concrete Mathematics, second edition, Addison Wesley,

Reading, 1994.
[4] C. Heuberger, H. Prodinger, Carry propagation in signed digit representations, European J. Combin,

24(3), 293-320, 2003.
[5] A. Knopfmacher, H. Prodinger. On Carlitz compositions, European J. Combin, 19(5), 579-589, 1998.
[6] D. E. Knuth, The average time for carry propagation, Nederl. Akad. Wetensch. Indag. Math., 40(2),

238-242, 1978.
[7] G. Louchard, H. Prodinger, Asymptotics of the moments of extreme-value related distribution func-

tions, Algorithmica, 46, 431-467, 2006.
[8] H. Prodinger, S. Wagner, Bootstrapping and double-exponential limit laws, submitted, 2012.

27


	Introduction
	The longest horizontal run in tilings of n2-rectangles
	Tilings of n3-rectangles
	The longest vertical run in tilings of n2-rectangles
	Conclusion
	References