F[n] = number of ways to tile a 4-by-n grid G[n] = number of ways to tile a 4-by-n grid with top-right and bottom-right squares uncovered H[n] = number of ways to tile a 4-by-n grid with bottom-right 2 squares uncovered = number of ways to tile a 4-by-n grid with top-right 2 squares uncovered if n >= 2, the right end of any tiling can be two vertical dominoes (F[n-1] ways) horz, horz vert (H[n-1] ways) horz, vert, horz (G[n-1] ways) vert, horz, horz (H[n-1] ways) 4 horizontal dominoes (F[n-2] ways) F[n] = F[n-1] + G[n-1] + 2*H[n-1] + F[n-2]; For G: the right end can be a vertical domino (F[n-1] ways) or two horizontal dominoes => top & bottom are horz = G[n-2] G[n] = F[n-1] + G[n-2]; For H: the right end can be a vertical domino (F[n-1] ways) or two horizontal dominoes (H[n-1] ways) H[n] = F[n-1] + H[n-1]; F[0] = 1, F[1] = 1, G[0] = 0, G[1] = 1, H[0] = 0, H[1] = 1
Hope it helps !! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.