How many upright paths from 0 0 to 6 6 never cross the line

How many upright paths from (0, 0) to (6, 6) never cross the line y = x? (\"Upright path\" is defined in problem 3a.)

Solution

All of the legal paths (ones which do not cross over y=xy=x) must begin with a move right and end with a move up. Further, any time the number of upward moves exceeds the number of downward moves, the path becomes illegal. So it would seem, the answer is the total number of paths from (0,0) to (n,n) - (Total illegal paths). The number of paths from (0,0) to (n,n) is (2nCn)=12C6-total illegal paths.