Fibonacci numbers

The Fibonacci numbers Fn are defined recursively by the relation Fn = Fn–1 + Fn–2, where F1 = F2 = 1. The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

They describe, among other things, the number of ways to tile a 2 × (n–1) checkerboard with 2 × 1 dominoes.

There's only one way to tile a 2 × 1 board:
|

Two ways to tile a 2 × 2 board (see also SVG version):
=, ||

Three ways to tile a 2 × 3 board (SVG version):
|||, |=, =|

Five ways to tile a 2 × 4 board (SVG version):
||||, ||=, |=|, =||, ==

Eight ways to tile a 2 × 5 board (SVG version):
|||||, |||=, ||=|, |=||, =|||, |==, =|=, ==|

Thirteen ways to tile a 2 × 6 board (SVG version):
Thirteen 2-by-6 boards

Twenty-one ways to tile a 2 × 7 board (SVG version):
Twenty-one 2-by-7 boards

See also Graham, Knuth, and Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994.

For a practical, commercial use of Fibonacci numbers to encode binary data in a self-clocking code, visit Kronos, Incorporated.

Originally designed and rendered using Mathematica 3.0 and GifOMatic for NeXT.
Copyright © 1997–2006 Robert M. Dickau.

(With belated thanks to Steven Fairgrieve for some minor corrections.)

[ home ] || [ 060523 ]

www.prairienet.org/~pops/fibboard.html