You have a board n x 2 and n dominoes. In how many ways can you cover the board?

The dominos are pieces 2 x 1.

We want to count all the possible tilings of the board.

The dominos are all identical so swapping any two of them

doesnt count as a different solution.You have a board n x 2 and n dominoes. In how many ways can you cover the board?
Let F(n) be the number of ways you can tile an nx2 board with n dominoes.



Note:

F(1) = 1

F(2) = 2



and for n%26gt;2...

Case one:

First domino is laid flush with the end. Then we're left with a (n-1)x2 board that hasn't been covered with the n-1 other dominoes. Thus for this case, there are F(n-1) tilings.



Case two:

First domino is laid "lengthwise" either on the top or the bottom. In order to completely cover the board, the second domino must be laid lengthwise on the bottom or top (whichever the first didn't take). Then we're left with a (n-2)x2 board to tile with n-2 dominoes, which by definition is done F(n-2) ways.



These are the only two cases, so we get the recursive definition

F(n) = F(n-1) + F(n-2)

which is the same definition for the fibonacci sequence.



Combine this with the note above showing F(1) is the second fibonacci number and F(2) is the third fibonacci number, we can conclude the following:

F(n) = f_(n+1) where f_(i) gives the ith fibonacci number.



[[[[[[

[For clarification, f_1 = 1, f_2 = 1, and so on.

since the "natural numbers" start at different places for different people, the actual formula above may be slightly different in different solutions.

If instead we were to have f_0 = 1, f_1 = 1, and f_2 = 2, the conclusion would simply be F(n) = f_n...

]]]]]]]You have a board n x 2 and n dominoes. In how many ways can you cover the board?
basically this is recursive and follows the natural fabonacci sequence !You have a board n x 2 and n dominoes. In how many ways can you cover the board?
2^2n