Skip to main content
4 of 4
edited tags
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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

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

Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171