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".