Chapter 16

Alternate Fibonacci Numbers

In this chapter, we shall provide a variety of examples that are counted by alternate Fibonacci numbers—that is, subsequences of the Fibonacci numbers, such as 1(= F1), 2(= F3), 5(= F5), 13(= F7), . . ., or 1(= F2), 3(= F4), 8(= F6), 21(= F8), . . . .

Example 16.1: Our first example deals with the undirected graph Gn shown in Fig. 16.1. This graph has the n + 1 vertices: img img img, and the n + (n − 1) = 2n − 1 edges:

equation

It is called the fan on n vertices.

For n = 2, the undirected graph G2 is shown in Fig. 16.2(a). In Fig. 16.2(b) there are three subgraphs of G2. Note that each of these subgraphs contains all three vertices of G2, contains no loops or cycles, and is connected. These are the three spanning trees of G2.

The fan for n = 3 is shown in Fig. 16.3(a) on p. 128. In Fig. 16.3(b) we have three of the eight spanning trees for G3. Note how these three spanning trees can be obtained from the three spanning trees in Fig. 16.2 (b) by adding ...

Get Fibonacci and Catalan Numbers: An Introduction now with the O’Reilly learning platform.

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