Home | 18.013A | Chapter 0 | Section 0.2 |
||
|
Prove that the Fibonacci numbers count the number of different ways of inserting n dominoes into a 2 by n grid, so that each domino covers two adjacent boxes.
Solution:
Consider the following array
The first domino on the left can be vertical in which case the remaining board to be covered is one shorter
xxxxx | |||||
xxxxx |
or it can be horizontal, in which case the only way to fill the other left square is by another horizontal domino, and the remaining board is two shorter
xxxxx |
xxxxx |
||||
yyyyy |
yyyyy |
If f(n) is the number of ways of covering the 2 by n board, then we get
f(n) = f(n-1) + f(n-2), the first term counts the number of ways of finishing the job after a first vertical and the second after a first horizontal.
Exercise 0.2A Try to find a similar formula for a 3 by n board.
Notice that it can't be done at all if n is odd;
(Hint: let g(2n) be the number of ways of covering the 3 by 2n board by dominoes and let h(2n-1) be the number of ways of covering the 3 by 2n-1 board with one corner square removed. You can figure out relations among g and h as above.)
|