Question

Exercise 1. It is easier to count the paths which are not Dyck paths. That is, count all the paths that MUST cross the line y -r. We will do this bijectively by showing that the "bad paths" are in bijection with paths from (-1, 1) to (n, n). The key to constructing this bijection is noting that each "bad path" has an earliest point where it crosses y-x. What type of path do you get if you reflect the bold portion of the path over the line y = x+1 in the diagram below? Try to express the observation in formal mathematical terms to establish the bijection. Then, count how many paths there are from (-1,1) to (n, n) to figure out how many "bad paths" there are.

Answer 1

Total number of paths from (0, 0) to (n, n) is the total number of permutations of n horizontal and n vertical steps, ie, (2n)!/n! n! = (2n n) Now we calculate the number of non - paths ie, paths which will cross the line y = x. Claim: The set of non - Dyck paths are in bijection with the set of paths from (-1, 1) to (n, n) Proof: - Notice the image of the point (0, 0) w.r.t the line y = x + 1 is (-1, 1) and any non - Dyck path has an unique earliest point, where it crosses the line y = x, say (p, q) where 0 lessthanorequalto p, w lessthanorequalto n - 1, and thus making contact with the line y = x + 1 at (p q + 1), for the first time. Also every path from (-1, 1) to (n, n) must cross the line y = x + 1, for the first time.