Prove number of nodes in heap

Question

Consider a variation of the normal heap which we will call the x-heap

The x-heap of height $h$ has the following properties:

• It will have $2^h$ nodes

• A height of $0$ corresponds to the single root node

• The format of the tree is a root with exactly one child, which in turn is the root of a complete binary tree

We define a collection of x-heaps to be sequence $X_0, X_1,\dots,X_k$ with the following properties:

• $height(X_{i-1})\leq height(X_i)$, where $0\leq i \leq k$

• There exist at least $i + 1$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$

• There exist at most $i + 2$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$

We cannot have a collection with all of the same type of x-heap (can't have collection with all single nodes)

Prove that if $X_0,X_1,\dots,X_k$ is a collection, then the total number of nodes is between $2^k$ and $2^{k+1}$

---

I am not sure where to start here. I feel I must use the last two bullet points, but not sure how.

Moreover, the trees in a collection can have height $1, 3, 4, 8$ as an example. It is not limited to increasing by $1$.

Answer 1

Interesting proposition.

Moreover, the trees in a collection can have height 1,3,4,8 as an example. It is not limited to increasing by 1.

How could 1,3,4,8 be an example? If you set $i=0$ in "there exist at least $i + 1$ x-heaps of $height \leq i$, where $0\leq i \leq k$", you know there exist at least 1 X-heap of height less than or equal to 0. That means $X_0$ must be 0. In fact, the height will be increased by 0 or 1 every time.

Reformulation

Since an x-heap is completely determined by its height, let us introduce almost-natural sequences, which comes from a collection of x-heaps in the question.

An almost-natural sequence is a non-decreasing sequence of integers $0=h_0, h_1,\dots,h_k$, where $k\ge0$, such that, for all $0\le i\le h_k$,

• at least $i + 1$ of them are not greater than $i$
• at most $i + 2$ of them are not greater than $i$.

Characterization of almost-natural sequences. An almost-natural sequence must be one of the following.

• $0, 1, \cdots, k-1, k$, i.e., the first $k+1$ natural numbers.
• $0, 1, \cdots, m-1, m, m, m+1, \cdots, k-2, k-1$, i.e., the first $k$ natural numbers with one of them, $m$ repeated once, where $0\le m\le k-1$.

Corollary. $2^k\le\sum_{i=0}^k2^{h_k}\le2^{k+1}-1$ for an almost-natural sequence $h_0,h_1,\dots,h_k$.

Exercises

Here are a few related exercises.

Exercise 1. Prove the characterization of almost-natural sequences.

Here is a hint. Does a given almost-natural sequence contain a repeated number? If yes, prove that number appears exactly twice and no other number is repeated.

Exercise 2. Prove the corollary.

Exercise 3. Let a d-natural sequence be a non-decreasing sequence of $k+1$ integers $0=h_0, h_1,\dots,h_k$ such that at least $i+1$ and at most $i+1+d$ of them are not greater than $i$ for all $0\le i\le h_k$. Determine the lower bound and upper bound of $\sum_{i=0}^k{h_k}$ and $\sum_{i=0}^k2^{h_k}\,.$