# How many subsets of NxM rectangle are tileable by dominos?

There are a lot of articles, formulas and algorithms for the number of domino tilings for some region, but I couldn't find anything about number of tileable regions. Is there any exact formula or at least some not very complicated algorithm? (I can generate all subsets and check for each of them if it is tileable or not, but it seems to be too complicated...)

Note: Just to be accurate, by "subset" I mean here "subset of set of 1x1 squares those union forms a NxM rectangle" and not "geometrical subset of NxM rectangle".

-
Interesting problem! Have you tried setting up some recursive formula? I'm not sure, but I think something useful can be found doing so. – barto Jan 22 '14 at 21:55
is not every rectangle that has at least one even (non-odd) side tilable? so any i by 2j is tilable, the only untilable rectangles are 2i+1 by 2j+1 – Willemien Jan 22 '14 at 22:23
@Willemien The question is about subsets, and not the entire rectangle. So yes, the subset needs to have (connected components of) even size. However, that is not a sufficient condition, as in the case of the T-tetromino. Perhaps having an equal number of black and white square is sufficient? – Calvin Lin Jan 22 '14 at 23:03
@CalvinLin, there are easy counterexamples to your speculation on the sufficiency of an equal number of black and white squares: For example, put a B above the first W in BWBW and a W below the second B. – Barry Cipra Jan 23 '14 at 3:18
you mean that the subsets don't have to be rectangles ? ( but they should be connected?) maybe any subset that can be divided in non odd(as described before) rectangles (but that is saying almost the same as saying when it can be tiled with domino's) – Willemien Jan 23 '14 at 8:20