Fibonacci and Catalan Numbers: An Introduction

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(= F₁), 2(= F₃), 5(= F₅), 13(= F₇), . . ., or 1(= F₂), 3(= F₄), 8(= F₆), 21(= F₈), . . . .

Example 16.1: Our first example deals with the undirected graph G_n 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 G₂ is shown in Fig. 16.2(a). In Fig. 16.2(b) there are three subgraphs of G₂. Note that each of these subgraphs contains all three vertices of G₂, contains no loops or cycles, and is connected. These are the three spanning trees of G₂.

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 G₃. Note how these three spanning trees can be obtained from the three spanning trees in Fig. 16.2 (b) by adding ...