For n ‰¥ 0, we want to count the number of ordered rooted trees on n + 1 vertices. The five trees in Fig. 12.52(a) cover the case for n = 3.

(a) Performing a postorder traversal of each tree in Fig. 12.52(a), we traverse each edge twice - once going down and once coming back up. When we traverse an edge going down, we shall write "1" and when we traverse one coming back up, we shall write "-1." Hence the postorder traversal for the first tree in Fig. 12.52(a) generates the list 1, 1, 1, -1, -1, -1. The list 1, 1, -1, -1, 1, -1 arises for the second tree in part (a) of the figure. Find the corresponding lists for the other three trees in Fig. 12.52(a).
(b) Determine the ordered rooted trees on five vertices that generate the lists: (i) 1, -1, 1, 1, -1, 1, -1, -1; (ii) 1, 1, -1,-1, 1, 1,-1,-1; and (iii) 1,-1, 1,-1, 1, 1, -1, -1. How many such trees are there on five vertices?
(c) For n ‰¥ 0, how many ordered rooted trees are there for n + 1 vertices?

Transcribed Image Text:

(a)