Section 4.4 Permutations and Combinations
293
96. Prove Vandermonde’s identity:
C(n + m, r) = ∙
r
k=0
C(n, k)C(m, r − k)
(Hint: use a combinatorial argument, picking r elements from the union of two disjoint sets of size n and
m, respectively.)
97. The recurrence relation for the sequence of Catalan numbers is
C(0) = 1
C(1) = 1
C(n) = ∙
n
k=1
C(k − 1)C(n − k) n ≥ 2
Although we will not prove it, a closed-form solution to this recurrence relation is
C(n) =
1
n + 1
C(2n, n)
(Note that C(n) denotes a value in the Catalan sequence and C(2n, n) denotes the number of combinations
of n objects from 2n objects.) Compute C(2), C(3), and C(4) using this formula and compare the results
with the recurrence relation results (see Exercise 38 of Section 3.1).
98. a. A turtle begins at the upper left corner of an n × n grid and makes his way to the lower right corner.
Along the way, he can move only right or down. The accompanying figure shows two possible paths in
a 4 × 4 grid. How many possible paths can the turtle take?
(Hint: Each path can be described by a sequence of R’s (right moves) and D’s (down moves). Find the
number of ways to distribute the R’s in such a sequence.)
b. Relate the answer to part (a) to the sequence of Catalan numbers (see Exercise 97).
99. Arrange the following permutations of the numbers {1, … , 6} in lexicographical order:
163542, 345621, 643125, 634521, 163452, 356421
100. Arrange the following permutations of the numbers {1, … , 5} in reverse lexicographical order:
32541, 35142, 53124, 42531, 32154, 42315
293
96. Prove Vandermonde’s identity:
C(n + m, r) = ∙
r
k=0
C(n, k)C(m, r − k)
(Hint: use a combinatorial argument, picking r elements from the union of two disjoint sets of size n and
m, respectively.)
97. The recurrence relation for the sequence of Catalan numbers is
C(0) = 1
C(1) = 1
C(n) = ∙
n
k=1
C(k − 1)C(n − k) n ≥ 2
Although we will not prove it, a closed-form solution to this recurrence relation is
C(n) =
1
n + 1
C(2n, n)
(Note that C(n) denotes a value in the Catalan sequence and C(2n, n) denotes the number of combinations
of n objects from 2n objects.) Compute C(2), C(3), and C(4) using this formula and compare the results
with the recurrence relation results (see Exercise 38 of Section 3.1).
98. a. A turtle begins at the upper left corner of an n × n grid and makes his way to the lower right corner.
Along the way, he can move only right or down. The accompanying figure shows two possible paths in
a 4 × 4 grid. How many possible paths can the turtle take?
(Hint: Each path can be described by a sequence of R’s (right moves) and D’s (down moves). Find the
number of ways to distribute the R’s in such a sequence.)
b. Relate the answer to part (a) to the sequence of Catalan numbers (see Exercise 97).
99. Arrange the following permutations of the numbers {1, … , 6} in lexicographical order:
163542, 345621, 643125, 634521, 163452, 356421
100. Arrange the following permutations of the numbers {1, … , 5} in reverse lexicographical order:
32541, 35142, 53124, 42531, 32154, 42315