Section 4.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
263
a. Write a recurrence relation for P(n), the number of ways to parenthesize a product of n factors, n ≥ 1.
Assume that P(1) = 1. (Hint: Note that for n > 2, the last multiplication to be performed can occur in
any of n − 1 positions.)
b. Prove that
P(n) = C(n − 1)
where C(0), C(1), … is the sequence of Catalan numbers (see Exercise 38 of Section 3.1).
76. A simple closed convex polygon consists of n points in the plane joined in pairs by n line segments; each
point is the endpoint of exactly 2 line segments, and any line connecting 2 nonadjacent points lies wholly
within the polygon.
a. Show that an (n + 2)-sided simple closed convex polygon can be triangulated (divided into triangular
regions) using n − 1 lines. (The figures show two different triangulations of a 6-sided polygon,
where n = 4).
(Hint: Use a pair of straight lines to shave off 2 corners; consider the cases where n is even and the cases
where n is odd.)
b. Write a recurrence relation for T(n), the number of different triangulations of an (n + 2)-sided polygon.
Assume that T(0) = 1. (Hint: Fix one edge of the polygon as the base of a triangle whose tip rotates
around the polygon, as shown. Use the sides of the triangle to divide the polygon into 2 polygonal sections with (k + 1) sides and (n − k + 2) sides.)
k = 1
k = 2
k = 3
k = 4
Trivial
2-sided
polygon
Trivial
2-sided
polygon
c. Prove that T(n) = C(n), where C(0), C(1), … is the sequence of Catalan numbers (see Exercise 38 of
Section 3.1).
S e c t i o n 4 . 3 PrinCiPle of inCluSion and exCluSion;
Pigeonhole PrinCiPle
In this section we discuss two more counting principles that can be used to solve
combinatorics problems.