O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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: 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 ...

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

Start Free Trial

No credit card required