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 31

Rooted Ordered Binary Trees, Pattern Avoidance, and Data Structures

In this chapter we have the opportunity to examine some additional examples where the Catalan numbers arise. This time, however, we shall verify that the structures are counted by these numbers by using the nonlinear recurrence relation developed in Chapter 29.

Example 31.1: Consider the trees shown in Fig. 31.1, where the vertices labeled with r are the roots. These trees are called binary because each vertex has at most two edges descending from it. Furthermore, these trees are ordered in the sense that a left branch descending from a vertex is considered to be different from a right branch descending from that vertex. In Fig. 31.2(a) we see the one rooted ordered binary tree for when we have n = 1 vertex—namely, just the root. Part (b) of Fig. 31.2 provides the two trees of this type for n = 2 vertices. If we let tn count the number of rooted ordered binary trees on n vertices, then at this point we have t1 = 1 and t2 = 2. The results in Fig. 31.3 on p. 240 show us that t3 = 5.

To count the number tn of rooted ordered binary trees on n ≥ 0 vertices, we shall assume ...

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