19
$\begingroup$

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).

$\endgroup$
9
  • $\begingroup$ Is it true that each given cell is at least as likely to be covered by a horizontal tile as it is to be covered by a vertical one? $\endgroup$ Sep 9 at 1:41
  • 2
    $\begingroup$ @PeterTaylor but this does not seem to be an injective map. Say, for $n=3$ both tilings (2*2)(vertical) and (vertical)(2*2) which cover the midpoint of the lower row by a horizontal domino are mapped to the all-vertical tiling. $\endgroup$ Sep 9 at 7:54
  • 2
    $\begingroup$ By the way, full disclosure: the reason I am asking this is because I like to present this to students as an example of the power of generating functions; but I was worried that maybe there is some cheap trick that lets you see it ahead of time. $\endgroup$ Sep 9 at 13:20
  • 2
    $\begingroup$ There's certainly a non-generating-function approach: by basic combinatorics the proportion is $$1 - 2 \frac{\sum_k k\binom{n - k}{k}}{\sum_k n\binom{n - k}{k}}$$ where the $k$ in the sums counts the pairs of horizontal tiles; then Wilf-Zeilberger can evaluate the sums. $\endgroup$ Sep 9 at 14:00
  • 1
    $\begingroup$ @Stef Yes, that follows from my answer below. There are more vertical tiles for $n \in \{1,3\}$; there are an equal number of vertical and horizontal tiles for $n \in \{2,4,5\}$; and there are more horizonal tiles for all $n \geq 6$. $\endgroup$
    – Tony Huynh
    Sep 11 at 11:09
14
$\begingroup$

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.

$\endgroup$
3
  • 8
    $\begingroup$ Maybe I should have chosen the names HORace and VERonica. $\endgroup$ Sep 9 at 14:10
  • $\begingroup$ I like this argument a lot! $\endgroup$ Sep 9 at 14:18
  • 1
    $\begingroup$ Without any further calculations, I think what this argument rigorously shows (by induction on $n$, if we pick a sufficiently large $n_0$ as the base case) is that if the limiting fraction $f$ of vertical tiles exists then $f\le 1/2$. But I think one has to work a bit harder (maybe not much harder?) to prove that $f$ exists and is strictly less than $1/2$. $\endgroup$ Sep 9 at 22:35
7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This is nice, but it is ultimately pretty similar to the full linear recurrence, compute the asymptotic growth rate approach. $\endgroup$ Sep 9 at 13:04
  • 1
    $\begingroup$ I agree. I basically did the minimal amount of work to show that the ratio (if it exists) is strictly less than $\frac{1}{2}$, but the answer is not too illuminating. Would be nice if there were a more conceptual answer. $\endgroup$
    – Tony Huynh
    Sep 9 at 13:41
5
$\begingroup$

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}$).

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ If 1-5 were equally likely (ignoring boundary effects, say, approximately for large n), wouldn't 4/10 of the dominos be vertical? $\endgroup$ Sep 9 at 12:55
  • $\begingroup$ It's the "The probability that two consecutive tiles are both vertical is of course $p^2$" claim that seems dubious to me: that's asserting an independence between tiles which isn't obvious, at any rate. $\endgroup$ Sep 9 at 13:24
  • $\begingroup$ Oh yes, the independence is not at all true. I'll rephrase that part. $\endgroup$ Sep 9 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.