I didn't use a recurrence. When dividing into three areas, one of the the lines must span the entire grid creating two areas. Then one more line is used to split one of the just created areas into three areas. I just figured out how many ways there are to place the first line, then how many ways there are to place the second. There are two main scenarios you need to deal with:
1) Two horizontal or vertical lines
2) One horizontal and one vertical line
I didn't use a recurrence. When dividing into three areas, one of the the lines must span the entire grid creating two areas. Then one more line is used to split one of the just created areas into three areas. I just figured out how many ways there are to place the first line, then how many ways there are to place the second. There are two main scenarios you need to deal with:
1) Two horizontal or vertical lines
2) One horizontal and one vertical line
Hope that helps
on /blog/107