Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 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 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 at 23:03
1  
@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 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 at 8:20
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.