Solutions to the Combinatorics Problems

1: Find the number of words of length n on the alphabet {0, 1} with exactly m blocks of the form 01.
Solution: There are n 1 locations between the digits in such a word. Let us call a location at which the
digits switch (either from 0 to 1 or from 1 to 0) a switch-location. For a word of the required form which
starts and ends with a 1, there must be 2m switch-locations (with every second switch-location giving a 01-
block) so there are
_
n1
2m
_
such words. For a word of the required form which starts with a 1 and ends
with a 0, there must be 2m + 1 switch-locations, so there are
_
n1
2m+1
_
such words. A word that starts with
0 and ends with 1 must have 2m 1 switch-locations, so there are
_
n1
2m1
_
such words, and a word that
starts and ends with 0 must have 2m swith-locations, so there are
_
n1
2m
_
such words. Altogether there are
_
n1
2m
_
+
_
n1
2m+1
_
+
_
n1
2m1
_
+
_
n1
2m
_
=
_
n
2m+1
_
+
_
n
2m
_
=
_
n+1
2m+1
_
such words.
Alternatively, a nice trick is to note that if we append a 1 to the beginning and a 0 to the end of a word
of the required form, then the new word will be of length n + 2 and will still have m 01-blocks; there will be
n + 1 locations between the digits in the word, and 2m + 1 of these locations will be switch-locations, so there
are
_
n+1
2m+1
_
such words.
2: Find the number of words of length n on the alphabet {0, 1, 2, 3} with an even number of zeros.
Solution: Let a
n
be the number of words of length n with an even number of 0s, and let b
n
be the number of
words of length n with an odd number of 0s. Note that any word of length n + 1 with an even number of 0s
can be obtained either by appending a 1, 2 or 3 to the end of a word of length n with an even number of 0s, or
by appending a 0 to the end of a sequence of length n with an odd number of 0s, and so we have the recurrence
relation a
n+1
= 3a
n
+ b
n
. Similarly, we have and b
n+1
= a
n
+ 3b
n
. The rst few values of a
n
and b
n
are listed
below.
n 1 2 3 4
a
n
3 10 36 136
b
n
1 6 28 120
We can combine the recurrence formulas for {a
n
} and {b
n
} to get a single recurrence formula for {a
n
} as follows.
a
n+2
= 3a
n+1
+b
n+1
= 3a
n+1
+(a
n
+3b
n
) = 3a
n+1
8a
n
+(9a
n
+3b
n
) = 3a
n+1
8a
n
+3a
n+1
= 6a
n+1
8a
n
To solve this, we solve its characteristic equation
2
6 +8 = 0 to get = 2, 4, so the formula for a
n
is of the
form a
n
= A 2
n
+ B 4
n
. Put in n = 1 and n = 2 to get 2A + 4B = 3 and 4A + 16B = 10. Solve these to get
A = B =
1
2
, and so we have a
n
=
1
2
_
2
n
+ 4
n
_
.
3: Find the number of words of length n on the alphabet {0, 1, 2} such that neighbours dier by at most 1.
Solution: Let a
n
be the number of such words that end with 0, let b
n
be the number of such words that end
with 1, let c
n
be the number of such words that end with 2, and let x
n
be the total number of such words, so
x
n
= a
n
+ b
n
+ c
n
. By interchanging 0s and 2s we obtain a bijection between the set of words of the required
form that end with 0 with the set of such words that end with 2, and so we have a
n
= c
n
and x
n
= 2a
n
+ b
n
.
Note that a
1
= b
1
= 1, and we have the recursion a
n+1
= a
n
+ b
n
and b
n+1
= a
n
+ b
n
+ c
n
= 2a
n
= x
n
. The
rst few values are listed below.
n 1 2 3 4 5
a
n
1 2 5 12 29
b
n
1 3 7 17 41
x
n
3 7 17 41 99
We can combine these paired recurrence formulas for {a
n
} and {b
n
} to get a single one for {b
n
} as follows.
b
n+2
= 2a
n+1
+ b
n+1
= 2(a
n
+ b
n
) + b
n+1
= (2a
n
+ b
n
) + b
n
+ b
n+1
= b
n+1
+ b
n
+ b
n+1
= 2b
n+1
+ b
n
.
To solve this, we solve its characteristic equation
2
21 = 0 to get = 1

2, so the formula for b

2)
n
+B(1

2)
n
(). Extend the sequence {b
n
} to include b
0
= 1 (so the recurrence relation is
still satised), then put n = 0 and n = 1 into equation () to get A+B = 1 (1) and A(1+

2)+B(1

2) = 1 (2).
Solve equations (1) and (2) to get A = B =
1
2
, and so b
n
=
1
2
_
(1 +

2)
n
+ (1

2)
n
_
. Thus the number of
words of the required form is x
n
= b
n+1
=
1
2
_
(1 +

2)
n+1
+ (1

2)
n+1
_
.
4: Find the number of words on the alphabet {0, 1, 2} with no neighbouring zeros.
Solution: This is similar to problem 3. The answer is
1
6
_
(3 + 2

3)(1 +

3)
n
+ (3 2

3)(1

3)
n
_
.
5: Find the number of subsets of {1, 2, , n} which do not contain two successive numbers.
Solution: Given a subset A {1, 2, , n} we associate the word e
1
e
2
e
3
on {0, 1} given by e
k
=
_
1 if k A
0 if k / A
.
Note that A contains two successive numbers if and only if the word has a block of the form 11. Thus the required
number of subsets is equal to the number of words of length n on {0, 1} with no 11-blocks. Let a
n
be the number
of such words that end with 0, let b
n
be the number of such words that end with 1, and let x
n
be the total
number of such words so x
n
= a
n
+ b
n
. Then a
1
= b
1
= 1 and we have the recurrence formulas a
n+1
= a
n
+ b
n
and b
n+1
= a
n
, so x
n
= a
n+1
. We combine these to get a
n+2
= a
n+1
+ b
n+1
= a
n+1
+ a
n
, so we see that
a
n
= f
n+1
and so x
n
= f
n+2
, where f
n
denotes the n
th
Fibonacci number. Solving the recursion formula for
the Fibonacci numbers gives f
n
=
1

5
__
1+

5
2
_
n

_
1

5
2
_
n
_
, so x
n
=
1

5
_
_
1+

5
2
_
n+2

_
1

5
2
_
n+2
_
.
6: Find the number of ways to choose two disjoint nonempty subsets from the set {1, 2, , n}.
Solution: To a given ordered pair (A, B) of disjoint subsets A, B {1, 2, , n}, we associate the word e
1
e
2
e
n
on {0, 1, 2} given by
e
k
=
_

_
0 if k / A B
1 if k A
2 if k B
.
We have A = if and only if the associated word is a word on {0, 1}, and B = if and only if the associated
word is a word on {0, 2}. Of the 3
n
words of length n, there are 2
n
which are words on {0, 1} and 2
n
which are
words on {0, 2}, and only 1 which is a word on {0}. Thus the number of ordered pairs of disjoint subsets of
{1, 2, , n} is equal to 3
n
2 2
n
+1, and so the number of unordered pairs of disjoint subsets is
1
2
(3
n
+1) 2
n
.
7: Find the number of surjective maps from the set {1, 2, 3, 4, 5, 6} to the set {1, 2, 3, 4}.
Solution: Note rst that there are n
k
maps from any set of k elements to any set of n elements, (since there are
n choices for the image of each of the k elements), but some of these maps are not surjective. Let A be a set
with k elements and let B = {b
1
, b
2
, , b
n
} be a set with n elements. For each i = 1, , n, let B
i
= B \ {b
i
}.
Note that a map from A to B is not surjective when its image lies in one of the subsets B
i
. Let S
i
be the set
of maps from A to B
i
. Note that for i < j, S
i
S
j
is the set of maps from A to B
i
B
j
= B \ {i, j}, and for
i < j < k, S
i
S
j
S
k
is the set of maps from A to B \ {i, j, k}, and so on. By the remark made in our rst
sentence, we have |S
i
| = (n 1)
k
, |S
i
S
j
| = (n 2)
k
, |S
i
S
j
S
k
| = (n 3)
k
and so on. By the Principle of
Inclusion and Exclusion, the total number of non-surjective maps from A to B is
|S
1
S
n
| =

i
|S
i
|

i<j
|S
i
S
j
| +

i<j<k
|S
i
S
j
S
k
|
=
_
n
1
_
(n 1)
k

_
n
2
_
(n 2)
k
+
_
n
3
_
(n 3)
k

_
n
n1
_
(1)
k
Thus the number of surjective maps from A to B is
n
k

_
n
1
_
(n 1)
k
+
_
n
2
_
(n 2)
k

_
n
3
_
(n 3)
k
+
_
n
n1
_
(1)
k
In particular, when k = 6 and n = 4, there are 4
6
4 3
6
+ 6 2
6
4 1
6
= 4096 2916 + 384 4 = 1560.
8: Find the number of permutations of order 6 in the group of all permutations of {1, 2, , 8}.
Solution: Given distinct elements a
1
, a
2
, , a
l
{1, 2, , n}, we write (a
1
, a
2
, , a
l
) for the permutation of
{1, 2, , n} dened by (a
1
) = a
2
, (a
2
) = a
3
, , (a
l1
) = a
l
and (a
l
) = a
1
and (k) = k if k = a
i
for any
i. Such a permutation is called a cycle of length l. Two cycles (a
1
, , a
k
) and (b
1
, , b
l
) are called disjoint
when a
i
= b
j
for any i, j. The following facts are well known and not dicult to prove.
1. Every permutation of {1, 2, , n} is a product of disjoint cycles, and the product is unique up to the
order of the cycles and the cyclic ordering of the elements in each cycle.
2. The order of a product of disjoint cycles is the least common multiples of their lengths.
We illustrate how to count the number of permutations of {1, 2, , n} which are equal to a product of disjoint
cycles of specied lengths, by nding the number of permutations of {1, 2, , 26} of the form
(abcdef)(ghij)(klmn)(opq)(rst)(uvw) .
There are
_
26
6
_
ways to choose the 6 unordered elements a, b, c, d, e, f. We can take a to be the smallest of
these, then there are 5! ways to choose the remaining 5 ordered elements b, c, d, e, f. Next there are
_
20
8
_
ways
to choose the next 8 unordered elements g, h, i, j, k, l, m, n. We take g to be the smallest of these 8, then there
are 7 6 5 ways to choose the ordered elements h, i, j, then we take k to be the smallest of the 4 elements
k, l, m, n, and then there are 3 2 1 ways to choose the ordered elements l, m, n. Finally, there are
_
12
9
_
ways to
choose the unordered elements o, p, q, r, s, t, u, v, w, we take o to be the smallest, there are 8 7 choices for p, q,
we take r to be the smallest of the 6 elements r, s, t, u, v, w, there are 5 4 choices for s, t, then we take u to be
the smallest of u, v, w and there are 2 1 choices for v, w. Thus the total number of permutations of the above
form is equal to
_
26
6
_
5 4 3 2 1
_
20
8
_
7 6 5 3 2 1
_
12
9
_
8 7 5 4 2 1 .
Using this counting method, we now count the total number of permutations of {1, 2, , 8} of order 6. We
make a table showing all possible forms for such permutations, and the number of permutations of each form.
form no. of elements
(abc)(de)
_
8
3
_
2
_
5
2
_
= 1120
(abc)(de)(fg)
_
8
3
_
2
_
5
4
_
3 = 1680
(abc)(def)(gh)
_
8
6
_
5 4 2 = 1120
(abcdef)
_
8
6
_
5! = 3360
(abcdef)(gh)
_
8
6
_
5! = 3360
Thus the total number is 1120 + 1680 + 1120 + 3360 + 3360 = 10640.
9: (a) Into how many regions do n great circles divide the surface of a sphere, given that no three of the great
circles intersect at a point?
Solution: Each of the
_
n
2
_
pairs of great circles intersect in two points, so the total number of points (or vertices)
is V = 2
_
n
2
_
= n(n 1). Each of the n great circles meets each of the other (n 1) great circles at two points,
so there are 2(n 1) points along each great circle, so each great circle is divided into 2(n 1) arcs (or edges),
and the total number of edges is E = 2n(n1) = 2V . The Euler characteristic of the sphere is = 2 so we have
V E +F = 2 where F is the required number of regions (or faces). Thus F = EV +2 = V +2 = n
2
n+2.
(b) Into how many regions do n spheres divide space, given that any two of the spheres intersect along a circle,
no three intersect along a circle, and no four intersect at a point?
Solution: Let a
n
denote the required number of regions. Note that a
1
= 2 and a
2
= 4. When we add an (n+1)
st
sphere, it intersects the other n spheres along n circles, each pair of which intersect at two points and no 3 of
which intersect at a point. By the proof of part (a) (with every occurrence of the word great removed) these
n circles divide the (n +1)
st
sphere into n
2
n +2 regions. Each of the regions corresponds to a subdivision of
a region in space into two parts, so we obtain the following recursion formula:
a
n
= a
n
+ (n
2
n + 2) .
Thus we have
a
n
= 2 + 2 + 4 + + ((n 1)
2
(n 1) + 2) =
n1

k=0
k
2
k + 2 .
Evaluate this sum to get a
n
=
n(n
2
3n + 8)
3
.
10: Find the number of paths in the set
_
(x, y) Z
2

0 y x
_
which move always to the right or upwards from
the point (0, 0) to the point (n, n).
Solution: First we solve the easier problem of nding the number of paths in Z
2
which move always to the right
and upwards from the point (a, b) to the point (a + k, b + l). Such a path consists of k + l steps with k of the
steps to the right and l of the steps upwards, so it corresponds in a natural way to a word of length k + l on
{r, u} with k rs and l us (with each r indicating a step to the right and each u indicating a step upwards).
There are
_
k+l
k
_
such words, and hence the same number of such paths.
Now we return to the given problem. From the previous paragraph we know that there are
_
2n
n
_
paths
from (0, 0) to (n, n) (moving upwards and to the right). Let us call such a path good if it remains below or
touches the line y = x, and let us call such a path bad if it crosses the line y = x, that is if it touches the line
y = x + 1. We must count the number of good paths.
There is a lovely trick which helps us to count the number of bad paths. Given a bad path from (0, 0) to
(n, n) we associate a path from (1, 1) to (n, n) as follows: nd the rst point p where the bad path touches the
line y = x + 1 and reect the initial portion of the bad path (the portion from (0, 0) to p) in the line y = x + 1
to obtain a path from (1, 1) to (n, n). Notice that we can recover the given bad path from the resulting path
by performing the same operation, and so this gives a bijective correspondence between the set of bad paths
from (0, 0) to (n, n) and the set of all paths from (1, 1) to (n, n). By the result of the rst paragraph there are
_
2n
n+1
_
such paths. Thus the total number of good paths from (0, 0) to (n, n) is
_
2n
n
_

_
2n
n+1
_
=
1
n+1
_
2n
n
_
.
11: 2n distinct points lie on a circle. In how many ways can the points be paired so that when all pairs are joined
by line segments, then resulting n line segments are disjoint.
Solution: Let c
n
denote the number of ways that 2n points on a circle can be paired so that the various line
segments joining the pairs do not cross. Let a
1
be one of the 2n points, and let a
2
, a
3
, , a
2n
be the rest of the
points in order around the circle (say clockwise). Note that a
1
cannot be paired with a
k
for k odd, since if it were
then we would have an odd number of points a
2
, a
3
, , a
k1
between a
1
and a
k
, one of which would have to be
paired with a point on the other side of the line segment a
1
a
k
. Thus a
1
can only be paired with a
2
, a
4
, , a
2n
.
When a
1
is paired with a
2k
, the 2(k 1) points a
2
, a
3
, , a
2k1
points must be paired amongst themselves and
there are c
k1
ways to do this, and the 2(n k) points a
k+1
, a
k+2
, a
2n
must be paired amongst themselves
and there are c
nk
ways to do this. Thus, setting c
0
= 1, we have the following recurrence relation for {c
n
}:
c
n
= c
0
c
n1
+ c
1
c
n2
+ c
2
c
n3
+ + c + n 1c
0
.
The rst few values are as follows
n 0 1 2 3 4
c
n
1 1 2 5 14
To solve this recurrence relation, let f(x) = c
0
+ c
1
x + c
2
x
2
+ . Then
f(x)
2
= (c
0
c
0
) + (c
0
c
1
+ c
1
c
0
) x + (c
0
c
2
+ c
1
c
1
+ c
2
c
0
) x
2
+ = c
1
+ c
2
x + c
3
x
2
+
and so we have xf(x)
2
= f(x) 1. By the quadratic formula, we have f(x) =
1

1 4x
2x
. In order to
have lim
x0
f(x) = c
0
, we must use the negative sign, so f(x) =
1

1 4x
2x
. Using the binomial expansion
(1 x)
1/2
= 1

n=1
2
n
(2n2)!
_
2
n
(n1)!
_
2
we obtain
f(x) =
1
2x
_
1

1 4x
_
=
1
2x

n=1
2
n
_
2n 2
n 1
_
x
n
=

n=1
1
n
_
2n 2
n 1
_
x
n1
=

n=0
1
n + 1
_
2n
n
_
x
n
.
Thus we obtain c
n
=
1
n+1
_
2n
n
_
. These numbers c
n
are called the Catalan numbers.
It seems a most remarkable coincidence that this problem has the same answer as the previous problem.
There is a wonderful way to see why this relationship holds. Given a pairing of the 2n points a
1
, a
2
, , a
2n
on the circle, connect them by nonintersecting line segments then form a word e
1
e
2
e
2n
on {r, u} as follows.
Begin at a
1
and set e
1
= r, then move clockwise around the circle visiting the vertices a
2
, a
3
, . When we
arrive at the vertex a
k
, which is an end point of some line segment, set e
k
= r if it is the rst time that we have
visited this line segment, and set e
k
= u if it is the second time we have visited the line segment. Convince
yourself that this word corresponds to a good path from (0, 0) to (n, n) and that the correspondence is bijective.
12: In how many ways can you triangulate a convex n-gon?
Solution: Let t
n
denote the number of such triangulations. Note that t
3
= 1. Label the vertices of a given
convex n-gon by a
1
, a
2
, , a
n
in order around the edge (say clockwise). Consider the edge a
1
a
2
. It must be
an edge of a triangle in any triangulation. If a
1
a
2
a
3
is a triangle in some triangulation, then the (n 1)-gon
a
1
a
3
a
4
a
n
will be triangulated (by that same triangulation); if a
1
a
2
a
n
is a triangle in some triangulation then
the (n 1)-gon a
2
a
3
a
n
will also be triangulated; and if a
1
a
2
a
k
is a triangle in some triangulation where
3 < k < n, then both the (k 1)-gon a
2
a
3
a
k
and also the (nk +2)-gon a
k
a
k+1
a
n
will be triangulated.
Thus, setting t
2
= 1, we obtain the following recurrence formula for {t
n
}:
t
n
= t
2
t
n1
+ t
3
t
n2
+ t
4
t
n3
+ + t
n1
t
2
.
This is the same recursion formula satised by the Catalan numbers, but with the indices shifted by 2, so we
have t
n
= c
n2
=
1
n1
_
2n4
n2
_
.