image

COMBINATORIAL MODELS I

Nothing ever becomes real till it is experienced; even a

proverb is no proverb to you till your life has illustrated it.

–John Keats

In Chapters 4 and 5, we studied several interesting applications of the Fibonacci and Lucas family to combinatorics, including the theory of partitioning. In this chapter, we will present additional applications to combinatorics.

In Section 4.2, we briefly studied compositions of positive integers n with summands 1 and 2. We found that the number of distinct compositions c014-math-001 of n is c014-math-002; see Table 14.1.

Table 14.1

n Compositions c014-math-003
1 1 1
2 1 + 1, 2 2
3 1 + 1 + 1, 1 + 2, 2 + 1 3
4 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2 5
5 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1, 8
2 + 1 + 1 + 1, 1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1
c014-math-004

14.1 A FIBONACCI TILING MODEL

Theorem 4.1 has a spectacular combinatorial interpretation. To see this, suppose we would like to tile a board (an array of n unit squares) ...

Get Fibonacci and Lucas Numbers with Applications, Volume 1, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.