Question

Dorothy is trying to walk from Munchkin land to Oz. Assume that Munchkin land is located at the point (0, 0) in the usual coordinate plane, and Oz is located at the point (n, n) in the first quadrant of the plane, where n is a positive integer. Since Dorothy is in a hurry she intends to only take East-bound steps that take you from (x, y) to (x+1, y) and North-bound steps that take you from (x, y) to (x, y+1). Dorothy has learned that the Wicked Witch is waiting for her somewhere above the line y = x in the First quadrant. If Dorothy never goes above the line y = x, how many different paths can she take from Munchkin Land to Oz? Come up with a recurrence relation for these paths and explain them. This will allow you to say that the paths have the same enumeration as what we saw in the section. (explain the enumeration please)