Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Became Hot Network Question
added 180 characters in body
Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

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

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

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

moved question to text and added missing "in average"
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

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

Non-enumerative proof that 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%.

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

Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171
Loading