Chapter 12, Problem 1RE

To determine

The number, if we make a tree that displays all monotonically increasing subsequences of $4,7,3,9,5,1,8$.

Explanation of Solution

We have seen in the text that to find all possible sub-sequences of a given sequence, we represent the problem in the form of a tree. We pull a tree from the root. The nodes of this root are the terms of the sequence given in the given order. Now, we have to draw the nodes of these nodes as well.

Therefore, we consider the first note. Since we need to find monotonically increasing followings for the nodes of the first node, we add the next terms in the same order that appear in the original sequence. We do this for all nodes and then their nodes, until we are exhausted (because the conditions will certainly do for us). The end result is the following tree.

Now, to calculate the total number of the latter, we simply calculate the total number of possible paths from root to leaf. These are the total nodes in a given tree (including trees). Since each node is viewed from the root through a unique path and for a write relative to a given path, we list only the nodes seen in order.

Hence, there are 22 such subsequences in all.