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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
