Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Inspired by this questionthis 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.

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.

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.

added 382 characters in body
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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.

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.

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.

Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Inequality among domino tilings of large triomino shapes

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.