## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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:   , and the n + (n − 1) = 2n − 1 edges: It is called the fan on n vertices.

Figure 16.1 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required