More applications of the Catalan numbers. (a) A monotonic path (also mentioned in Problem 23.6)…
More applications of the Catalan numbers.
(a) A monotonic path (also mentioned in Problem 23.6) on an n × n grid is a path that starts at the bottom left corner, ends at the top right corner, and includes only upward and rightward moves. Show that the number of such paths that do not cross the diagonal (the one extending from bottom left to top right) is Cn.
(b) Show that the number of ways of drawing nonintersecting diagonals in a convex n-gon so as to divide it into triangles is Cn−2, the (n − 2)nd Catalan number. For example (Figure 25.12), this can be done five ways in a pentagon, and C5−2 = 5.
Consider a grid that is 7 units wide and 9 units tall Figure 23.5). A monotonic path is one that begins at point (0, 0) (the bottom left corner) and traverses to (7, 9) (the top right corner), using only upward and rightward moves.
(a) How many different paths are possible?
(b) How many such paths go through the point (3, 2)?