3 Maze in general and Trees too!!! Given an maze of sidelength n where one starts at (0, 0) and goes to (n, n).

(a) How many shortest paths are there that go from (0, 0) to (n, n)?

(b) Consider shortest paths that meet the conditions which only use to points (x,y) where y x. That is, the path cannot cross line y = x.

i. Give an expression using part (a) and (b), that counts the number of paths. (Hint: consider what happens after a shortest that crosses y = x at (i, i), that is, the remaining path starting from (i, i + 1) and then continuing to (n, n). If in the remainder of the path, one exchanges the y-direction moves with x-direction moves and vice versa, where does one end up?

ii. A different tack is to derive a recursive formula. We call these paths n-legal paths for a maze of sidelength n, and let Fn be the number of n-legal paths. Consider a path, and let i < n be the largest value where the path contains (i, i), argue the number of paths is then Fi Fni1. (Hint: if i = 0, what are your first and last moves, and where is the remainder of the path allowed to go.)

iii. Give a recursive formula for the number of spanning trees of a complete graph Kn for n 3, where each non-root node has degree 3 or 1, and at most 1 node has degree 2? Two trees are different if and only if either left-subtree is different or right-subtree is different.

Need Help on just Part B Please