Please be thorough:

9. Consider an n n grid (indexed 0, . . . n-1). Say we want to draw a path from the lower left 10 points grid point (0,0) to the upper right grid point, (n -1, 1) by travelling only east or north cell-by-cell (no back-tracking is allowed, so we cannot travel west or south). We are interested in how many different paths are there in terms of n. For example, for n 4, the number of paths from (0,0) to (3, 3) is 20 (see Figure 1) (a) At a particular grid point (i,j), how many ways are there of reaching this point in terms of adjacent grid points? (b) How many paths are there from (0,0) to (n -1,n 1) for n -5? Page 2 0.3 4 (2,3) 10 (3,3) 20 (0,2) 1 (1,2) 3 (2,2)6 (3,2) 10 (0,0) 11,0) (2,0) 1(3,0) 1 Figure 1: Grid Example for n-4 (c) How many paths are there from (0,0) to (n-1, n-1) for n 10? (d) Give a general formula in terms of n for the number of paths