algorithmscomputer sciencelinear programming
Define a subtree to be any connected subgraph of a tree.
Prove that the number of subtrees of a complete binary tree is not polynomial
in the number of nodes.
Give an example of a class of trees $\{T_n\}$ where the number of subtrees is a
polynomial in the number of nodes.
Thoughts:
This function seems to give us the number of special trees, given the root.
$$F(n) = 1 + 2 f(\text{left subtree}) + 2 f(\text{right subtree}) + f(\text{left subtree}) f(\text{right subtree})$$
As I understand, you are looking for formula for maximal number of nodes. Let $n$ be number of levels under children of the root. Assume $n\geq 1$ (for smaller it's trivial).
On the left node has $L$ children, and each of that $L$ children has $L$ children as long as it's not a leaf ($L \cdot L$ in second tier). So on the left you have $\frac{L^{n+1}-1}{L-1}$ nodes. It's easy to calculate using informations about sum of geometric sequence.
$$1 + \sum_{i=1}^{n}L^i=1 + L \cdot\frac{1-L^n}{1-L} = \frac{L^{n+1}-1}{L-1}$$
Similarly you have $\frac{R^{n+1}-1}{R-1}$ nodes on the right. And after you include root, you receive formula.
$$1 + \frac{R^{n+1}-1}{R-1} + \frac{L^{n+1}-1}{L-1}$$
Firstly, (c) should be in the $h=2$ row and you are missing a few trees in the $h=3$ row; there should be 21 of them. For the number of full binary trees of a certain height see OEIS A001699.
Now to find $N(h)$. Counting by subtrees is hard and there is hardly any literature on the matter. It's hard because the left and right principal subtrees are not independent. The natural recursion involves taking the union of their subtree-sets. Before you read further, you should check out the related thread. I will relate to a few things from its accepted answer.
A binary tree $\tau$ can be compacted into a unique directed acyclic graph where each node represents a distinct subtree in $\tau$. Now you can represent these DAGs in a canonical form, allowing you to define their "shape". In this sense, the "height" of the DAG corresponds to the height of the tree. For example,
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad$ 
is a possible shape that contains 11 nodes and has a height of 6. Thus it represents a tree of height 6 with 11 subtrees. To find $N(h)$, we need to make the DAG as wide as possible. A node in layer $\ell$ of the DAG represents a tree of height $\ell$, so layer $\ell$ can contain at most $T(\ell)$ nodes. Also, by the canonical definition of the DAGs, the width of the layers can only grow {1,2,4,8,...} from the top down. These two bounds are tight (by the algorithm in the other thread), and can be used to compute $N(h)$. For example, the first few values $(h, N(h), \text{shape})$ are
0 1 [1]
1 2 [1, 1]
2 3 [1, 1, 1]
3 5 [1, 1, 2, 1]
4 8 [1, 1, 3, 2, 1]
5 12 [1, 1, 3, 4, 2, 1]
6 20 [1, 1, 3, 8, 4, 2, 1]
7 36 [1, 1, 3, 16, 8, 4, 2, 1]
8 57 [1, 1, 3, 21, 16, 8, 4, 2, 1]
9 89 [1, 1, 3, 21, 32, 16, 8, 4, 2, 1]
10 153 [1, 1, 3, 21, 64, 32, 16, 8, 4, 2, 1]
The first 200 values of $N(h)$ are listed here.
Best Answer
You don’t need to worry about the exact number of subtrees of a complete binary tree. (I use the term complete binary tree to mean one in which every non-leaf has two daughters, and all levels are filled; it’s sufficient to look at those even if you use the definition that doesn’t require the last level to be filled.) If $T_n$ is the complete binary tree of height $n$ (or depth $n$, if that’s your terminology), then $T_n$ has $2^{n+1}-1$ vertices. Let $T_n^L$ and $T_n^R$ be the left and right subtrees of $T_n$. Each is a copy of $T_{n-1}$ and therefore has $2^n-1$ vertices. Let $T$ be a subtree of $T_n^L$ and $v$ a vertex of $T_n^R$; there is a unique path in $T_n$ from the root of $T$ to $v$, and adding that path to $T$ produces a subtree $S(T,v)$ of $T_n$. If $T,T'$ are subtrees of $T_n^L$, and $v,v'$ are vertices of $T_n^R$, then $S(T,v)=S(T',v')$ iff $T=T'$ and $v=v'$. Use this to show that if $T_n$ has $t_n$ subtrees, then
$$\lim_{n\to\infty}\frac{t_{n+1}}{t_n}=\infty$$
and conclude that $t_n$ cannot be a polynomial in $n$ (why?).
For the second question, note that every chain is a tree.