recurrence relation related problems

Question

I'm having some difficulties of finding the recurrence relations of;

1. number of divisions of internal region of n sided polygon

2. number of paths from one point to another point in an NxN grid

Can anyone guide me in approaching in a way to a solution?

EDIT: I guess the solution of both problems is the catalan number

Well I need recurrence relation for them and mostly a basic idea of finding it

Answer 1

1. If you have a polygon with n vertices, you know that 2 consecutive vertices make a triangle with the center of the polygon. No need for recursion. There are n such regions.

2. This looks pretty complicated. If you say your grid is NxM then at the first step either you go down (new grid : N-1xM) or you go right (new grid : NxM-1) so $C(N, M) = C(N-1, M) + C(N, M-1)$ + limit conditions when N or M is equal to 1. If you have a closed formula it should be easy to check it with this formula else I didn't look more into it yet