Aforward path from (0,0) to (n, n) is good if it never goes strictly above the diagonal line x = y. any other forward path is bad. from class, the number of good forward paths is the nth catalan number.

in this problem, you will get a new derivation for the formula for catalan numbers without using generating functions.
we denote paths as sequences (v1, v2n) where each vi is either the vector (1,0) or (0,1).

(a) given a bad path ( v2n) from (0,0) to (n, n), let r be the smallest index such that vi + vr is above the line x = y, i. e., the second coordinate is strictly bigger than the first coordinate.
create a new path (w1, w2n) by w ; jvi if 1 < i show that w is a forward path from (0,0) to (n â 1, n + 1).

(b) in (a) we defined a function {bad forward paths from (0,0) to (n, n)} + {forward paths from (0,0) to (n â 1, n + 1)}. show that this function is a bijection.