TAOCP 7.2.2 Exercise 61
Let $P_n$ be the number of integer sequences $x_1 \ldots x_n$ such that $x_1 = 1$ and $1 \le x_{k+1} \le 2x_k \qquad \text{for } 1 \le k < n.$ For a rooted binary tree, the profile at level $k$ is the...
Exercise 61. [HM26] Let $P_n$ be the number of integer sequences $x_1 \ldots x_n$ such that $x_1 = 1$ and $1 \le x_{k+1} \le 2x_k$ for $1 \le k < n$. (The first few values are 1, 2, 6, 20, 76, 2280, ...; this sequence was introduced by A. Cayley in Philosophical Magazine (4) 13 (1857), 245–248, who showed that $P_n$ enumerates the partitions of $2^n - 1$ into powers of 2.)
a) Show that $P_n$ is the number of different profiles that are possible for a binary tree of height $n$.
b) Find an efficient way to compute $P_n$ for large $n$. Hint: Consider the more general sequence $P_n^{(m)}$, defined similarly but with $x_1 = m$.
c) Use the estimation of exercise 57 (Theorem E') to show that $P_n \ge \left\lfloor\frac{2^n}{3}/(n-1)\right\rfloor$.
Verified: no
Solve time: 4m28s
Setup
Let $P_n$ be the number of integer sequences $x_1 \ldots x_n$ such that $x_1 = 1$ and
$1 \le x_{k+1} \le 2x_k \qquad \text{for } 1 \le k < n.$
For a rooted binary tree, the profile at level $k$ is the number of nodes at that level; write it as $p_k$. A binary tree of height $n$ has levels $1,\ldots,n$ with $p_1=1$ and $p_k \ge 1$ for all $k \le n$. Each node has at most two children, so
$p_{k+1} \le 2p_k \qquad \text{for } 1 \le k < n.$
For the generalized quantity $P_n^{(m)}$, sequences satisfy $x_1 = m$ with the same recurrence constraints.
The tasks are to identify $P_n$ with binary-tree profiles, to compute $P_n$ efficiently, and to establish the lower bound
$P_n \ge \left\lfloor \frac{2^n}{3} \middle/ (n-1) \right\rfloor.$
Solution
(a) Correspondence with binary-tree profiles
Let $(x_1,\ldots,x_n)$ satisfy $x_1=1$ and $1 \le x_{k+1} \le 2x_k$. Construct a rooted binary tree level by level as follows. At level $1$ place a single root, so the profile satisfies $p_1=1=x_1$.
Assume level $k$ has been constructed with $p_k=x_k$. Each node at level $k$ has at most two children, so the total number of nodes that can be created at level $k+1$ is at most $2x_k$. Choose any integer $p_{k+1}$ satisfying $1 \le p_{k+1} \le 2x_k$ and distribute children among the nodes at level $k$ so that exactly $p_{k+1}$ nodes appear at level $k+1$; this is possible because each node contributes at most two children and the bound $2x_k$ is sharp.
Thus every admissible sequence determines a profile $(p_1,\ldots,p_n)$ satisfying $p_1=1$ and $1 \le p_{k+1} \le 2p_k$. Conversely, given any binary tree of height $n$, its profile satisfies these inequalities, since each level is nonempty and each node has at most two children.
Therefore the mapping $x_k = p_k$ is a bijection between admissible sequences and binary-tree profiles of height $n$. This completes the proof of part (a). ∎
(b) Efficient computation of $P_n$
Define
$P_n^{(m)} = #{x_1 \ldots x_n : x_1=m,\ 1 \le x_{k+1} \le 2x_k}.$
Conditioning on the second term yields, for $n \ge 2$,
$P_n^{(m)} = \sum_{t=1}^{2m} P_{n-1}^{(t)}.$
This follows because any valid sequence beginning with $x_1=m$ chooses $x_2=t$ with $1 \le t \le 2m$, and the remainder is any valid sequence counted by $P_{n-1}^{(t)}$.
Let
$S_{n-1}(m) = \sum_{t=1}^{m} P_{n-1}^{(t)}.$
Then
$P_n^{(m)} = S_{n-1}(2m), \qquad S_{n-1}(m) = S_{n-1}(m-1) + P_{n-1}^{(m)}.$
Hence both arrays $P_n^{(m)}$ and their prefix sums can be computed simultaneously in increasing order of $m$. For fixed $n$, the largest possible value of $x_k$ is $2^{k-1}$, since repeated doubling is the maximal growth permitted by $x_{k+1} \le 2x_k$. Therefore it suffices to compute $P_n^{(m)}$ for $1 \le m \le 2^{n-1}$.
The computation proceeds level by level: initialize $P_1^{(1)}=1$ and $P_1^{(m)}=0$ for $m>1$. For each $n$, compute all $P_n^{(m)}$ from the previous level using the summation formula and prefix sums. Each level requires a linear sweep over the admissible range $1 \le m \le 2^{n-1}$, so the total arithmetic cost is proportional to
$\sum_{k=1}^{n} 2^{k-1} = 2^n - 1.$
This yields an evaluation of $P_n$ in time proportional to $2^n$ and space proportional to $2^{n-1}$.
(c) Lower bound
For each sequence $x_1 \ldots x_n$, at step $k$ the constraint $1 \le x_{k+1} \le 2x_k$ implies that both choices
$x_{k+1} = 1 \quad \text{and} \quad x_{k+1} = 2x_k$
are always admissible, since $x_k \ge 1$ implies $1 \le 2x_k$.
Define a mapping from binary strings $\varepsilon_2 \ldots \varepsilon_n \in {0,1}^{n-1}$ to sequences by
$x_1 = 1,$
\begin{cases} 1, & \varepsilon_{k+1} = 0,\ 2x_k, & \varepsilon_{k+1} = 1. \end{cases}$$ At each step this rule preserves $1 \le x_{k+1} \le 2x_k$, so every binary string produces a valid sequence. Distinct binary strings produce distinct sequences because the first index $k$ where they differ forces different values of $x_{k+1}$. Hence there are at least $2^{n-1}$ valid sequences: $$P_n \ge 2^{n-1}.$$ Since for all $n \ge 2$, $$2^{n-1} \ge \frac{2^n}{3(n-1)},$$ because this inequality is equivalent to $3(n-1) \ge 2$, which holds for $n \ge 2$, it follows that $$P_n \ge \frac{2^n}{3(n-1)}.$$ Taking the floor preserves the inequality, hence $$P_n \ge \left\lfloor \frac{2^n}{3} \middle/ (n-1) \right\rfloor.$$ This completes the proof. ∎ ## Verification The bijection in part (a) uses only the constraints $p_1=1$ and $p_{k+1} \le 2p_k$, matching exactly the defining inequalities for the sequences, so no additional structure is introduced. The recurrence in part (b) partitions sequences by the value of $x_2$, which ranges over all integers $1$ through $2m$, and the remaining suffix depends only on that choice, so the decomposition is disjoint and exhaustive. The lower bound in part (c) depends only on the existence of two valid choices at every step. Since $x_k \ge 1$ implies $1 \le 2x_k$, both transitions are always feasible, and no further constraints eliminate them. ## Notes The recurrence in part (b) can be viewed as a restricted partition convolution on a dynamically growing state space bounded by $2^{k-1}$. The binary construction in part (c) corresponds to selecting an extremal subset of the backtracking tree consisting only of leftmost and maximal branches, which already yields exponential growth in $n$.