8
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Nov 3, 2015 at 18:34
  • $\begingroup$ @GerhardPaseman: Yes, one can reduce it to some sort of staircase shapes in the middle - but finding an inclusion here is tricky... $\endgroup$
    – Per Alexandersson
    Commented Nov 3, 2015 at 19:27
  • 1
    $\begingroup$ What are the counts for the first few $n$? $\endgroup$
    – Douglas Zare
    Commented Nov 3, 2015 at 23:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Nov 4, 2015 at 2:33
  • 1
    $\begingroup$ The sequence $L_n$ for $n \ge 1$ begins [12, 128832, 1524023326720, 19791909372130292011008, 281712534342378705290655154554535936]. $I_n$ begins [13, 145601, 1765722581057, 23333526083922816720025, 336575314603876110364700686838155709]. $\endgroup$
    – Peter Taylor
    Commented Sep 29, 2021 at 15:39

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .