Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?

Question

Is there a non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?

It is a nice exercise with rational generating functions (or equivalently, linear recurrence relations) to show that for a random domino tiling of a $2\times n$ rectangle, with $n$ large, we can expect about $\frac{1}{\sqrt{5}}\approx 44.7\%$ of the tiles to be vertical. In the spirit of Non-enumerative proof that there are many derangements?, I wonder if there is an easy way to see, without computing this fraction, that this average must be some constant < 50%.

EDIT: Maybe to sharpen the request, is there any heuristic which works here and also carries over to the case of a $k\times n$ rectangle (with say $k$ fixed and $n$ large).

Answer 1

Here is at least a heuristic argument for why we should expect fewer vertical dominoes than horizontal dominoes. As we increase the length of the strip (to the right, say), let us think about how the rightmost four squares are covered. There are three cases: (1) two horizontal dominoes; (2) two vertical dominoes; (3) the last two squares are covered by a vertical domino and the preceding two squares are covered by horizontal dominoes (that "stick out" to the left and cover two additional squares).

Imagine I'm trying to build one copy of every tiling of the $2\times n$ strip and I'm trying to gauge whether I'll need to buy more horizontal dominoes from Harry or more vertical dominoes from Victoria. For every tiling of a $2\times (n-2)$ strip I'll need two horizontal dominoes for case (1) and two vertical dominoes for case (2); this is a tie. But for case (3), I need two horizontal dominoes and only one vertical domino for each tiling of a $2\times (n-3)$ strip. So I'm going to need to buy more dominoes from Harry than from Victoria.

Answer 2

Here is a proof without computing the fraction.

For each $n \in \mathbb{N}$, let $t_n$ be the number of tilings of the $2 \times n$ rectangle by dominos, and let $v_n$ and $h_n$ be the total number of vertical and horizonal tiles that appear in these tilings.

We have the following recurrence relations $$t_n=t_{n-1}+t_{n-2} \\ h_n=h_{n-1}+h_{n-2}+2t_{n-2} \\v_n=v_{n-1}+v_{n-2}+t_{n-1}$$

with initial conditions $t_1=1, t_2=2, h_1=0, h_2=2, v_1=1$, and $v_2=2$. It is easy to verify by hand that $v_5=h_5$ and $v_6 < h_6$. Therefore, $v_n < h_n$ for all $n \geq 6$ provided that $2t_{n-2} \geq t_{n-1}$ for all $n \geq 6$. However, $2t_{n-2} \geq t_{n-1}$ holds since $(t_n)_{n=1}^\infty$ is the Fibonacci sequence. Moreover, since $t_n / t_{n-1}$ tends to the golden ratio $\phi$ (which is strictly less than $2$), this shows that some fraction strictly less than $\frac{1}{2}$ of the tiles are vertical.

Answer 3

Essentially also a reformulation:

Tilings of $n\times 2$ with vertical and horizontal dominos are in bijection with Zeckendorf expansions of integers in $[0,F_{n+1}-1]$ (perhaps up to a small shift of $n$), expanded to the correct length by adding leading zeroes: From left to right write $01$ for two parallel horizontal tiles and write $0$ for a vertical tile. The Zeckendorf expansion of a random integer in $[0,F_{n+1}-1]$ involves $F_n$ with asymptotic probability $1/\omega^2$ (for $\omega=(1+\sqrt{5})/2$ the golden number). The inequality $2/\omega^2>1/\omega$ implies now the result (and, more precisely, the probability for a vertical tile is thus indeed $\omega/(2+\omega)=1/\sqrt{5}$).

Answer 4

Could some argument along these lines be made? (I admit that this argument is itself seriously lacking.)

Let $p$ be the probability that a random tile among all domino tilings of a $2\times n$ rectangle is vertical. The question is why $p\approx 1/\sqrt{5}$.

Label the tiles from left-to-right, breaking ties from bottom-to-top (for sake of concreteness). If the orientation of two consecutive tiles was independent (it's not), then the probability that two consecutive tiles were both vertical would be $p^2$. There are $5$ different ways that the tiles $i$ and $i+1$ can be arranged:

1. $i$ is vertical, $i+1$ is vertical,
2. $i$ is vertical, $i+1$ is horizontal,
3. $i$ is horizontal, $i+1$ is vertical,
4. $i$ is horizontal, $i+1$ is horizontal, and $i+1$ is above $i$,
5. $i$ is horizontal, $i+1$ is horizontal, and $i+1$ is to the right of $i$.

If all $5$ of those possibilities were equally likely, then two consecutive tiles would be vertical with probability $1/5$. They are not equally likely, so we do not have equality because of boundary effects, but as $n\to\infty$, they become increasingly closer to equally likely, so $p^2\to 1/5$.