8

Inspired by this question, which asks for what shape maximizes the number of domino tilings, I want to ask the following seemingly simpler question, which I have been thinking about for a while:

Consider the straight triomino, consisting of three squares in a row, each with side $2n$. This is the $I_n$-triomino.

Then consider the $L_n$-triomino, consisting of three squares with side $2n$, but now in an L-shape.

Clearly, $I_n$ and $L_n$ have the same area, $12n^2$, and both can be tiled by dominos, tiles of shape $1 \times 2$.

Is it clear there are at least as many domino tilings of $I_n$ as there are of $L_n$?

Intuitively, the bent shape is more "constrained" in some sense, and one could imagine generalizations of this problem with more such corners.

Of course, one beautiful way to prove the inequality is to give an injection of tilings of the L-shape to tilings of the I-shape, but it is not completely clear how to do this.

Edit: My computer program gives that $L_1 = 12$ and $I_1 = 13$, and $L_2 = 128832$ and $I_2 = 145601$. I do not dare to runt it for next $n$, but there is a closed formula for the $I_n$, see page 166 in these slides. This source describe a quicker way to count tiles, so perhaps it is possible to do here.

Community
  • 1
Per Alexandersson
  • 15,598
  • It isn't clear to me, but this is how I would start. Consider the middle square and look at incomplete tilings of that square where isolated squares along two edges remain uncovered. Can you biject between the cases where the two edges are adjacent versus when they are opposite? I imagine stair steps connecting uncovered squares with their covered counterparts, and shifting the dominoes to shift the uncovered squares from one edge to another. Gerhard "You're Probably Thinking This Too" Paseman, 2015.11.03 – Gerhard Paseman Nov 03 '15 at 18:34
  • @GerhardPaseman: Yes, one can reduce it to some sort of staircase shapes in the middle - but finding an inclusion here is tricky... – Per Alexandersson Nov 03 '15 at 19:27
  • 1
    What are the counts for the first few $n$? – Douglas Zare Nov 03 '15 at 23:50
  • 1
    Both regions can be expressed as a union of two congruent trapezoids with base angles of $90^\circ$ and $45^\circ$. For each subset of $n$ out of $2n$ squares on the jagged edge, there is some number of domino tilings of that trapezoid with those $n$ included. For $L_n$, you sum over the subsets of the count times the count of the complementary subset. For $I_n$, you sum over the subsets of the count times the count of the complement reversed. Perhaps it would be helpful to determine the counts for the trapezoids. – Douglas Zare Nov 04 '15 at 02:33
  • @DouglasZare: Yep, that's true - I went down that road, that's probably the way to reduce the problem. However, even with this reduction, it is far from straightforward. The tilings of the region near where these trapezioids glue together can't be made into an injection in a straightforward manner... – Per Alexandersson Nov 04 '15 at 03:07
  • 1
    The sequence $L_n$ for $n \ge 1$ begins [12, 128832, 1524023326720, 19791909372130292011008, 281712534342378705290655154554535936]. $I_n$ begins [13, 145601, 1765722581057, 23333526083922816720025, 336575314603876110364700686838155709]. – Peter Taylor Sep 29 '21 at 15:39

0 Answers0