We want to count step-by-step paths between points in the plane with integer coor- dinates. Only two kinds of step are allowed: a right-step which increments the x coordinate, and an up-step which increments the y coordinate
(a) How many paths are there from (0, 0) to (20, 30)?
(b) How many paths are there from (0,0) to (20, 30) that go through the point (10, 10)?
(c) How many paths are there from (0, 0) to (20, 30) that do not go through either of the points (10, 10) and (15, 20)?
Hint: Let P be the set of paths from (0, 0) to (20, 30), N₁ be the paths in P that go through (10, 10) and N₂ be the paths in P that go through (15, 20).