Friday, January 27, 2012

How many different perfect covers are there for a 4 x 4 chessboard using dominoes?

Are there any particular formulas in Combinatorics that we can apply?How many different perfect covers are there for a 4 x 4 chessboard using dominoes?
To solve it by hand, just proceed systematically.
First put a horizontal (H) domino in the corner.
Follow it with first another H next to it ... and continue from there.
Then backtrack at each stage and place a vertical (V).

There are only 8 different ways to start,
always placing the next one in the next available space from the top left:

HHHHH
HHHHV
HHHV
HHVH
HHVV
HVVHH
HVVHV
HVVV

From each of those, the number of ways to complete the cover is very limited (3 or fewer).

When you are done with that, you'll have half of them.
The other half are diagonal mirrors of those, with the upper left domino vertical.

For lots of information on this topic see:

https://secure.wikimedia.org/wikipedia/e鈥?/a>
(Domino Tiling in Wikipedia)

or
https://oeis.org/A004003 in the OEIS

2x2: 2 ways
4x4: 36 ways ... at which point it takes off like a rocket
6x6: 6738
8x8: 12,988,816
and on from there to enormous numbers.

The formula, involving cosines of all things, can be found on the Wikipedia page.
  • cracker barrel locations
  • No comments:

    Post a Comment