Number of ways to packing $2 \times 1$ dominos into a $3 \times 6$ grid

Question

I tried counting the different ways but couldn't figure out a consistent method, and would appreciate any insights.

Answer 1

It looks like there's a nice recursive formula for this, but supposing you hadn't heard of such a formula and didn't think of a way to find one, here's how you might count the ways in an only slightly more tedious fashion.

Numbering the columns from $1$ to $6$, we can consider four cases:

1. No dominos overlap columns $2$ and $3$ or columns $4$ and $5.$
2. Dominos overlap columns $2$ and $3$ but not columns $4$ and $5.$
3. Dominos overlap columns $4$ and $5$ but not columns $2$ and $3.$
4. Dominos overlap columns $2$ and $3$ and also overlap columns $4$ and $5.$

A parity argument (the number of squares covered by any number of dominos is even) shows that you cannot just have one domino overlapping columns $2$ and $3$, and you cannot have three overlapping dominos. It has to be two dominos or none.

You can also demonstrate that when two dominos overlap one of those pairs of columns, it has to be in the top two rows or the bottom two rows. Top and bottom rows quickly leads to a contradiction.

Another parity argument shows that in case 4, it has to be the same two rows overlapping both pairs of columns. Top two rows on one side and bottom two rows on the other doesn't work.

So for case 1, we have the grid divided in three $3\times 2$ blocks, with three ways to put the dominos in each block.

For case 2, we have two ways to overlap columns $2$ and $3.$ The rest of the dominos in the left-hand $3\times 4$ block then can be placed in only one way. But the right-hand $3\times 2$ block can be filled three ways independently of the left-hand block.

Case 3 is filled in the same number of ways as case 2.

Once you decide "top two rows" or "bottom" for case 4, the rest of the dominos can be placed in only one way.

Adding up the four cases I get $41,$ the same as the proposed recursive formula.