An up-right path between two lattice points and is a path from to that takes steps of length 1 unit either up or to the right. How many up-right paths from to , when drawn in the plane with the line , enclose exactly one bounded region below that line?
Solution
We will make use of a sort of bijection which is typically used to prove the closed form for the Catalan numbers. We will count these paths with complementary counting. Since both the starting and ending points are above the line , any path which traverses below this line (and hence includes a point on the line ) will enclose at least one region. In any such path, we can reflect the portion of the path after the first visit to the line over that line to get a path from to . This process is reversible for any path to , so the number of paths enclosing at least one region is . More difficult is to count the paths that enclose at least two regions. For any such path, consider the first and final times it intersects the line . Since at least two regions are enclosed, there must be some point on the intermediate portion of the path on the line . Then we can reflect only this portion of the path over the line to get a new path containing a point on the line . We can then do a similar reflection starting from the first such point to get a path from to . This process is reversible, so the number of paths which enclose at least two regions is . Then the desired answer is just .