META-FIBONACCI SEQUENCES, BINARY TREES, AND EXTREMAL COMPACT CODES

BRAD JACKSON AND FRANK RUSKEY

Abstract. We look at a family of meta-Fibonacci sequences which arise in studying the number of leaves at the largest level in certain infinite sequences of binary trees, restricted compositions of an integer, and binary compact codes. For this family of meta-Fibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations. Included in these families of sequences are several well-known sequences in the Online Encyclopedia of Integer Sequences (OEIS).

1. Introduction

In a remarkable paper Emily Norwood studied the number of “compact codes” [5]. A compact code can be thought of as the sorted sequence of level numbers of the leaves of an extended binary tree. She provided a recurrence relation and table of the number of trees classified according to their height and their number of leaves. We will prove that if the outline of this table is considered as an increasing sequence of integers, then one of the “meta-fibonacci” numbers arises, namely the one that satisfies the recurrence relation

a(n) = a(x(n) − a(n − 1)) + a(y(n) − a(n − 2)),

with x(n) = n − 1 and y(n) = n − 2. Sequences satisfying this recurrence, but with different linear functions for x(n) and y(n) have been investigated by several authors in recent years, but the general behavior of these sequences remains rather mysterious. Perhaps the most well-behaved sequences in the family occur when x(n) = n and y(n) = n − 1. For a given parameter s ≥ 0, we will show that the sequences with x(n) = y(n)+1 = n−s are almost as well-behaved. In particular, we will show that they occur in a natural combinatorial setting, that they satisfy a recurrence relation of the form a_{s}(n) = f(n) + a_{s}(n − g(n)), and that they have a fairly simple ordinary generating function.

The case of s = 1 was studied before by Tanny [7]. The case of s = 0 was considered before by Conolly [2]. Our attempt here is to simplify, unify, generalize, and combinatorialize their results.

Research supported in part by NSERC.

Figure 1. The tree F_{0}.

Figure 2. The tree F_{1}.

2. Meta-Fibonacci Sequences and Complete Binary Trees

Figure 1 shows part of an infinite ordered binary tree F. The forest of labelled trees in F consists of a succession of complete binary trees of sizes 1, 1, 3, 7, …, 2^{h} − 1, . . .. We refer to the subtree with 2^{h} − 1 nodes as subtree h. The nodes of these trees are labelled in preorder. Now adjoin to F an infinite path that connects the trees from left-to-right as shown in Figure 2. We will think of this path as being parameterized by a value s that gives the delay between the preorder counts of successive trees. Alternatively, we can think of the nodes along the path as being super-nodes, where each super-node contains s ordinary nodes. This infinite tree is denoted F_{s}, with our initial tree F = F_{0}. The trees F_{0}, F_{1}, F_{2} are shown in Figures 1, 2, 3, respectively.

Denote by T_{s}(n) the tree induced by the first n nodes of the infinite tree F_{s}. Define a_{s}(n) to be the number of nodes at the bottom level in T_{s}(n). Also define d_{s}(n) to be 1 if the n-th node is a leaf and to be 0 if the n-th node is an internal node. Finally, define p_{s}(n) to be the positions occupied by the 1’s in the d_{s} sequences. Table 1 gives the values of a_{s}(n), d_{s}(n), and p_{s}(n) for s = 0, 1, 2 and 1 ≤ n ≤ 20. The values of four of these table

Figure 3. The tree F_{2}.

\begin{matrix}n = & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ a_{0}(n) & 1 & 2 & 2 & 3 & 4 & 4 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 8 & 8 & 9 & 10 & 10 & 11 & 12 \\ a_{1}(n) & 1 & 1 & 2 & 2 & 2 & 3 & 4 & 4 & 4 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 8 & 8 & 8 & 9 \\ a_{2}(n) & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 4 & 4 & 4 & 4 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 8 \\ d_{0}(n) & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ d_{1}(n) & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ d_{2}(n) & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ p_{0}(n) & 1 & 2 & 4 & 5 & 8 & 9 & 11 & 12 & 16 & 17 & 19 & 20 & 23 & 24 & 26 & 27 & 32 & 33 & 35 & 36 \\ p_{1}(n) & 1 & 3 & 6 & 7 & 11 & 12 & 14 & 15 & 20 & 21 & 23 & 24 & 27 & 28 & 30 & 31 & 37 & 38 & 40 & 41 \\ p_{2}(n) & 1 & 4 & 8 & 9 & 14 & 15 & 17 & 18 & 24 & 25 & 27 & 28 & 31 & 32 & 34 & 35 & 42 & 43 & 45 & 46 \end{matrix}

Table 1. The values of a_{s}(n) and d_{s}(n) for s = 0, 1, 2 and 1 ≤ n ≤ 20.

entries appear in OEIS^{1}, namely a_{0}(n) = A046699, a_{1}(n) = A006949, d_{0}(n) = A079559, and p_{0}(n) = A101925 = A005187(n) + 1. For fixed s these numbers are related as follows.

(1) a_{s}(n) = ∑_{j=0}^{n} d_{s}(n) and p_{s}(n) = min{j : a_{s}(j) = n}.

The a_{s}(n) numbers satisfy the meta-Fibonacci recurrence relation stated in Theorem 1 below.

Theorem 2.1. If 0 ≤ n ≤ s + 1, then a_{s}(n) = 1. If n = s + 2 then a_{s}(n) = 2. If n > s + 2, then

a_{s}(n) = a_{s}(n − s − a_{s}(n − 1)) + a_{s}(n − s − 1 − a_{s}(n − 2)).

Proof. First observe that if all the leaves at the last level are removed from F_{s}, then the same structure remains, except that the leftmost super-node needs to be made into an ordinary node (by subtracting s − 1). We will refer to this process as chopping the last level.

We split the proof into two broad cases depending on whether n is a leaf or not; i.e., whether d_{s}(n) = 1 (Case 1) or d_{s}(n) = 0 (Case 2).

1OEIS = Neil Sloane’s online encyclopedia of integer sequences.

Case 1a: If d_{s}(n − 1) = d_{s}(n) = 1 then n and n − 1 are sibling leaves and a_{s}(n) is even. For example, node 28 in Figure 3. The trees T_{s}(n − 1) and T_{s}(n − 2) have the same number of nodes, a_{s}(n)/2, at the penultimate level as does T_{s}(n). Thus by chopping the last level from T_{s}(n−1) and T_{s}(n−2), we see that a_{s}(n−s−a_{s}(n−1)) = a_{s}(n)/2 = a_{s}(n−s−1−a_{s}(n−1)).

Case 1b: If d_{s}(n) = 1 and d_{s}(n − 1) = 0 then n is a left child of its parent n − 1 and a_{s}(n) is odd. For example, node 27 in Figure 3. The tree T_{s}(n − 1) has (a_{s}(n) + 1)/2 nodes at the penultimate level and the tree T_{s}(n − 2) has (a_{s}(n) − 1)/2 nodes at the penultimate level. Thus by chopping the last level from T_{s}(n−1) and T_{s}(n−2), we see that a_{s}(n−s−a_{s}(n−1)) = (a_{s}(n) + 1)/2 and a_{s}(n − s − 1 − a_{s}(n − 1)) = (a_{s}(n) − 1)/2.

Case 2a: If d_{s}(n) = 0 and d_{s}(n − 1) = 1, then a_{s}(n) is even. For example, node 26 or node 29 in Figure 3. The trees T_{s}(n − 1) and T_{s}(n − 2) have the same number of nodes, a_{s}(n)/2, at the penultimate level. Node n may have been at the penultimate level in T_{s}(n), but it is removed in T_{s}(n − 1) and T_{s}(n − 2). Thus by chopping the last level from T_{s}(n − 1) and T_{s}(n − 2), we see that a_{s}(n − s − a_{s}(n − 1)) = a_{s}(n)/2 = a_{s}(n − s − 1 − a_{s}(n − 1)).

Case 2b: If d_{s}(n) = 0 and d_{s}(n − 1) = 0, then a_{s}(n) is even. For example, node 22 or node 30 in Figure 3. The trees T_{s}(n − 1) and T_{s}(n − 2) have the same number of nodes, a_{s}(n)/2, at the penultimate level. Node n may have been at the penultimate level in T_{s}(n), but it is removed in T_{s}(n − 1) and T_{s}(n − 2). Thus by chopping the last level from T_{s}(n − 1) and T_{s}(n − 2), we see that a_{s}(n − s − a_{s}(n − 1)) = a_{s}(n)/2 = a_{s}(n − s − 1 − a_{s}(n − 1)). □

Define D_{s} to be the infinite string d_{s}(1)d_{s}(1)d_{s}(2) · · ·. Let D_{n} be the finite string defined by D_{0} = 1 and D_{n+1} = 0D_{n}D_{n}. Let E_{n} be the finite string defined by E_{0} = 1 and E_{n+1} = E_{n}E_{n}0.

Lemma 2.2.

(2) D_{0} = D_{0}D_{0}D_{1}D_{2}D_{3} ⋯ = E_{∞}

Proof. The first equality in (2) is implied immediately by the definition of F_{0}; i.e., in 0D_{n}D_{n} the 0 is from the root (which is listed first in preorder) and D_{n}D_{n} is from the left and right subtrees. By the definitions, E_{n}^{R} = D_{n}, where the superscript R denotes reversal of the string. Thus

D_{0}D_{0}D_{1} ⋯ D_{n} = E_{n} ⋯ E_{1}E_{0}E_{0}.

Since E_{n} is a prefix of E_{n+1} by definition, the expression E_{∞} is well-defined. Hence D_{0} = E_{∞}. □

The sequence E_{n} has been considered before by Allouche, Betrema, and Shallit [1] in a different context. It is interesting to note that the sequence d(1)d(2) ⋯ is the limit of the morphism 0 ↦ 0 and 1 ↦ 110 (also discussed in [1], pg. 237). The following corollary is equation (6; pg. 132) in [2].

Corollary 2.3. The numbers a_{0}(n) satisfy the following recurrence relation for 0 ≤ k < 2^{h}.

a_{0}(2^{h} − 1 + k) = 2^{h−1} + a_{0}(k).

Proof. Since D_{0} = E_{h}E_{h}0 ⋯ and |E_{h}| = 2^{h} − 1, the value of d_{0}(2^{h} − 1 + k) = d_{0}(k) for 1 ≤ k ≤ 2^{h} − 1. Since we defined d_{0}(0) = 0 it also holds when k = 0. The number of 1’s in E_{h} is #_{1}(E_{h}) = 2^{h−1}. Thus

a_{0}(2^{h} − 1 + k) = ∑_{j=0}^{2^{h}−1} d_{0}(j) + ∑_{j=0}^{k} d_{0}(2^{h} − 1 + j)

= #_{1}(E_{h}) + ∑_{j=0}^{k} d_{0}(j)
= 2^{h−1} + a_{0}(k).
□

Lemma 2.4.

a_{s}(n) = \begin{cases}a_{0}(n − sh) & if 2^{h} + (s − 1)h + 1 ≤ n ≤ 2^{h+1} + (s − 1)h − 1, \\ 2^{h−1} & if 2^{h} + (s − 1)h − s + 1 ≤ n ≤ 2^{h} + (s − 1)h. \end{cases}

Proof. The labels on the nodes in subtree h in F_{s} are exactly the values of n lying in the first range above. This is true since there are 1 + 1 + 3 + ⋯ + (2^{h−1} − 1) = 2^{h} − h nodes in the subtrees to the left of subtree h, and sh super-nodes. Thus the lowest label of a node in subtree h is 2^{h} − h + sh + 1 = 2^{h} + (s − 1)h + 1, and the highest label is 2^{h} + (s − 1)h + 2^{h} − 1. The difference between the labels on corresponding nodes in F_{s} and F_{0} is sh if the nodes are in subtree h; thus a_{s}(n) = a_{0}(n − sh).

In the second range the nodes are super-nodes lying between subtrees h − 1 and h and therefore having 2^{h−1} leaves in their left-subtree. □

Corollary 2.5.

a_{1}(n) = a_{0}(n − ⌊lg n⌋).

Proof. Taking s = 1 in Lemma 2.4 we obtain a_{1}(n) = a_{0}(n − h) in the range 2^{h} + 1 ≤ n ≤ 2^{h+1} − 1. In that range h = ⌊lg n⌋. We need only check what happens when n = 2^{h}. By the lemma a_{1}(2^{h}) = 2^{h−1}. However, in F_{0} the node 2^{h} − h is the rightmost node in subtree h and thus a_{0}(2^{h} − h) = 2^{h−1}. □

The case s = 1 of the theorem below is roughly equivalent to equations (2.2) and (2.3) in Tanny [7].

Theorem 2.6. If 1 ≤ k ≤ 2^{h−1} − 1, then

a_{s}(2^{h} + (s − 1)h + k + 1) = 2^{h−2} + a_{s}(2^{h−1} + (s − 1)h − s + k + 1).

If 1 ≤ k ≤ 2^{h−1} − 1, then

a_{s}(2^{h} + 2^{h−1} + (s − 1)h + k) = 2^{h−1} + a_{s}(2^{h−1} + (s − 1)h − s + k + 1).

If 2^{h} + (s − 1)h − s + 1 ≤ n ≤ 2^{h} + (s − 1)h + 1, then a_{s}(n) = 2^{h−1}.

Proof. Let the node n be in the subtree h or the super-node, call it y, that is the parent of subtree h. Let x be the root of that subtree and denote the left and right subtrees of x by T_{L} and T_{R}. We will prove the following recurrence relation.

(3) a_{s}(n) = \begin{cases}2^{h−1} + a_{s}(n − 2^{h} − s + 1) & if n ∈ T_{R}, \\ 2^{h−2} + a_{s}(n − 2^{h−1} − s) & if n ∈ T_{L}, \\ 2^{h−1} & if n = x or n ∈ y. \end{cases}

Let T be the subtree whose root is the right child of the left child of y. In the first two cases above we are mappping the subtree T_{L} or T_{R} to T, which has the same structure. In the case of T_{R} we skip over 2^{h−1} leaves and 2^{h} + s − 1 nodes. In the case of T_{L} we skip over 2^{h−2} leaves and 2^{h−1} + s nodes. Clearly, if n = x or n ∈ y, then a_{s}(n) = 2^{h−1}.

From the proof of the previous lemma we know that x = 2^{h} + (s − 1)h + 1 and thus that the root of T_{R} is 2^{h} + 2^{h−1} + (s − 1)h + 1 and the root of T_{L} is x + 1 = 2^{h} + (s − 1)h + 2. Thus we know the exact range of n in each of the subtrees and the theorem statement is another way of writing (3). □

Let r_{1}, r_{2}, r_{3}, r_{4}, … = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 … be the transition sequence of the binary reflected Gray code; this sequence is also known as the “ruler function” (A001511). If the alternating 0’s are removed from the sequence r_{1} − 1, r_{2} − 1, r_{3} − 1, r_{4} − 1, … = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 … then the ruler function is again obtained. This implies that the generating function of the ruler function is

(4) ∑_{k≥1} r_{k}z^{k} = ∑_{n≥0} \frac{z^{2^{n}}}{1 − z^{2^{n}}} .

Lemma 2.7.

D_{0} = 110^{r_{1}}110^{r_{2}}110^{r_{3}}110^{r_{4}} ⋯
= 10^{r_{1}−1}10^{r_{2}−1}10^{r_{3}−1}10^{r_{4}−1} ⋯

Proof. The ruler sequence is R_{∞} where R_{1} = 1 and R_{n+1} = R_{n}, n+1, R_{n}. Since |R_{n}| = 2^{n}−1, we have r_{2^{n}+i} = r_{i} for 1 ≤ i ≤ 2^{n} − 1 and r_{2^{n}} = n + 1. We will show that

E_{n+1} = 110^{r_{1}}110^{r_{2}} ⋯ 110^{r_{2^{n−1}}},

which will finish the proof of the first equality since D_{0} = E_{∞}. By induction

E_{n+2} = E_{n+1}E_{n+1}0
= 110^{r_{1}}110^{r_{2}} ⋯ 110^{r_{2^{n−1}}} 110^{r_{1}}110^{r_{2}} ⋯ 110^{r_{2^{n−1}}} 0
= 110^{r_{1}}110^{r_{2}} ⋯ 110^{r_{2^{n−1}}} 110^{r_{1+2^{n−1}}}110^{r_{2+2^{n−1}}} ⋯ 110^{r_{2^{n}−1}}110^{n+1},

as required. The second equality follows from the well-known property of the ruler sequence that R_{∞} = 1 + (0, r_{1}, 0, r_{2}, 0, r_{3}, 0, r_{4}, 0, …). □

We can extend some of the previous results about D_{0} to D_{s}. For proposition P the notation [[P]] means 1 if P is true and 0 if P is false.

Lemma 2.8. Let s_{j} = r_{j} + s[[j is a power of 2]].

D_{s} = D_{0}0^{s}D_{0}0^{s}D_{1}0^{s}D_{2}0^{s}D_{3}0^{s} ⋯
D_{s} = 10^{s_{1}−1}10^{s_{2}−1}10^{s_{3}−1}10^{s_{4}−1} ⋯

Proof. The proof is similar to those used in Lemmata 2.7 and 2.2 and is omitted. □

Since the p_{s}(n) numbers give the positions of the 1’s in D_{s} the following corollary is true.

Corollary 2.9. For all n ≥ 1,

p_{s}(n + 1) − p_{s}(n) = r_{n} + s[[n is a power of 2]].

2.1. Generating Functions. If S = s(1)s(2) ⋯ s(m) is a string then we use S(z) to denote the ordinary generating function S(z) = ∑ s(i)z^{i}. Let A_{s}(z) and D_{s}(z) denote the ordinary generating functions of the a_{s}(n) and d_{s}(n) sequences, respectively. Directly from the definitions we get the equation shown below:

A_{s}(z) = \frac{D_{s}(z)}{1 − z}.

Since A_{s}(z) is determined by D_{s}(z) and D_{s}(z) is easier to treat, we first concentrate our attention on D_{s}(z).

Lemma 2.10.

D_{n}(z) = z^{n}(1 + z)(1 + z^{3}) ⋯ (1 + z^{2^{n}−1}) = z^{n} ∏_{j=1}^{n}(1 + z^{2^{j}−1}).

E_{n}(z) = z(1 + z)(1 + z^{3}) ⋯ (1 + z^{2^{n}−1}) = z ∏_{j=1}^{n}(1 + z^{2^{j}−1}).

Proof. From the recurrence relation D_{0} = 1 and D_{n+1} = 0D_{n}D_{n} we obtain D_{0}(z) = z and

D_{n+1}(z) = zD_{n}(z) + z^{|0D_{n}|}D_{n}(z) = z(1 + z^{2^{n+1}−1})D_{n}(z).

Similarly E_{0}(z) = z and E_{n+1}(z) = (1 + z^{2^{n+1}−1})E_{n}(z). The result now follows by induction. □ Corollary 2.11.

D_{0}(z) = z(1 + z)(1 + z^{3})(1 + z^{7}) ⋯ = z ∏_{n≥1}(1 + z^{2^{n}−1}).

Proof. Follows at once from the the preceding lemma and the equation D_{0} = E_{∞} from Lemma 2.2. □

Theorem 2.12. The generating function D_{s}(z) is equal to

(5) z(1 + z^{s+2^{0}}(1 + z^{s+2^{1}}[1 + z^{2^{1}−1}](1 + z^{s+2^{2}}[1 + z^{2^{2}−1}](1 + z^{s+2^{3}}[1 + z^{2^{3}−1}](1 + ⋯

Proof. We need to translate the string D_{0}0^{s}D_{0}0^{s}D_{1}0^{s}D_{2}0^{s}D_{3}0^{s} ⋯ from Lemma 2.8 into its generating function. Since

(6) |D_{0}0^{s}D_{0}0^{s}D_{1}0^{s} ⋯ D_{n−1}0^{s}| = s + 1 + ∑_{j=0}^{n−1}(2^{j+1} − 1 + s) = 2^{n+1} + (s − 1)(n + 1),

we can write

(7) D_{s}(z) = z (1 + ∑_{n≥0} z^{2^{n+1}+(n+1)(s−1)}D_{n}(z)) .

Let x_{k} = z(1 + z^{2^{k}−1}), so that D_{n}(z) = x_{1}x_{2} ⋯ x_{n}. We can rewrite (5) as

z(1 + z^{s+2^{0}}(1 + z^{s+2^{1}−1}x_{1}(1 + z^{s+2^{2}−1}x_{2}(1 + z^{s+2^{3}−1}x_{3}(1 + ⋯

The coefficient of x_{1}x_{2} ⋯ x_{n} is z raised to the power 1 + 2^{n+1} + (s − 1)(n + 1) by the sum given in (6). □

Theorem 2.13. If s ≥ 1, then

(8) A_{s}(z) = \frac{1 − z^{s}}{1 − z} (z + z ∑_{n≥1} ∏_{k=1}^{n} z^{s−1}(z + z^{2^{k}}))

Proof. Call the expression on the right R_{s}(z) and let y = z^{s−1}. Multiply R_{s}(z) by 1 − z, expand, and collect terms by increasing powers of y to obtain

(1 − z)R_{s}(z) = (1 − zy) (z + z ∑_{n≥1} ∏_{k=1}^{n−1} y(z + z^{2^{k}}))

= z + z ∑_{n≥1} y^{n} ∏_{k=1}^{n}(z + z^{2^{k}}) − z^{2}y − z^{2}y ∑_{n≥1} ∏_{k=1}^{n} y^{n}(z + z^{2^{k}})

= z + z ∑_{n≥1} y^{n} (∏_{k=1}^{n}(z + z^{2^{k}}) − zy ∏_{k=0}^{n}(z + z^{2^{k}}))

= z + z ∑_{n≥1} y^{n} ((z + z^{2^{n}}) ∏_{k=1}^{n−1}(z + z^{2^{k}}) − z ∏_{k=0}^{n−1}(z + z^{2^{k}}))

= z + z ∑_{n≥1} y^{n}z^{2^{n}} ∏_{k=1}^{n−1}(z + z^{2^{k}})

Note that this last expression is equal to D_{s}(z) by (7). □

Jon Perry [6] has observed experimentally that a_{1}(n) counts the number of compositions of n such that, for some k,

x_{0} + x_{1} + x_{2} + ⋯ + x_{k} = n where x_{i} ∈ {1, 2^{i}}

He uses the notation 1 + [1, 2] + [1, 4] + [1, 8] + ⋯ to denote the set of such compositions and notes that many other combinatorial objects are in one-to-one correspondence with similar composition rules [6]. We call these rules specifications.

Corollary 2.14. For s ≥ 1, the number of compositions of n with specification

[1, 2, …, s] + [s, 2 + s − 1] + [s, 4 + s − 1] + [s, 8 + s − 1] + ⋯

is a_{s}(n).

Proof. This is clear from the generating function for A_{s}(z) given in Theorem 2.13 once z(1 − z^{s})/(1 − z) is written as z + z^{2} + ⋯ + z^{s}. □

As an example, for s = 2 and n = 8, the specification is [1, 2] + [2, 3] + [2, 5] + [2, 9] + ⋯ and the a_{2}(8) = 3 compositions are

8 = 1 + 2 + 5 = 1 + 3 + 2 + 2 = 2 + 2 + 2 + 2.

To finish this section we also develop a generating function for the p_{s}(n) sequences.

Lemma 2.15. For all s ≥ 0,

∑_{n≥0} p_{s}(n)z^{n} = \frac{1}{1 − z} (1 + z ∑_{k≥0} z^{2^{k}} (s + \frac{1}{1 − z^{2^{k}}} )) .

Proof. Let P_{s}(z) denote the ordinary generating function of the numbers p_{s}(n). Then

∑_{n≥1}(p_{s}(n + 1) − p_{s}(n))z^{n} = \frac{1}{z} ((1 − z)P_{s}(z) − 1) .

By Corollary 2.9 this expression is equal to

∑_{n≥1} (r_{n} + s[[n is a power of 2]]) z^{n} = ∑_{k≥0} (sz^{2^{k}} + \frac{z^{2^{k}}}{1 − z^{2^{k}}} ) ,

where the equality follows from (4). Solving for P_{s}(z) finishes the proof. □

3. Binary Compact Codes

A binary compact code can be represented by an extended binary tree. We use the term extended binary tree in the sense of Knuth [4]: every node has either no children (a leaf) or two children (an internal node). Since no other types of codes are considered here, we shorten “binary compact code” to “code”. A code of order n can be represented by a tree with n leaves in which the level numbers ℓ_{1} ≥ ℓ_{2} ≥ ⋯ ≥ ℓ_{n} of the leaves are non-increasing. We will identify a compact binary code by the sequence of level numbers (ℓ_{1}, ℓ_{2}, …, ℓ_{n}). For example, the codes for n = 5 are (3, 3, 3, 3, 1), (3, 3, 2, 2, 2), and (4, 4, 3, 2, 1). Every code of order n corresponds to a unique partition of 1 into the n powers of 1/2 given by 1 = 2^{−ℓ_{1}} + 2^{−ℓ_{2}} + ⋯ + 2^{−ℓ_{n}}. Thus (3, 3, 3, 3, 1) corresponds to the partition 1 = 1/8 + 1/8 + 1/8 + 1/8 + 1/2.

The height h of a tree is the length of the longest path from the root to any leaf. For a given height h and integer n, we consider here the problem of finding the maximum number of leaves at the largest level h among all trees with n leaves, which we denote by M(n, h). Clearly M(n, h) = 0 if h < ⌈lg n⌉. A tree T with n vertices and height h that has M(n, h) leaf pairs at the largest level is said to be an optimal tree. We will show that our first two meta-Fibonacci sequences can be realized by certain families of optimal trees. This will be done via a “greedy” algorithm for constructing a sequence of optimal tree/codes for successive values of n and a fixed value h. We denote these trees T_{n,h} for natural numbers n and h and call them greedy trees. Here is the greedy algorithm for constructing T_{n,h}.

• If n = h + 1, then there is only one tree/code, namely h, h, h − 1, …, 2, 1.

• Given T_{n,h} the code T_{n,h} is obtained by replacing the leftmost level ℓ_{i} for which ℓ_{i} < h by the two levels ℓ_{i} + 1, ℓ_{i} + 1.

We will also consider the trees T_{n} = T_{n,⌈lg n⌉}. They may be constructed greedily as follows.

• If n = 0, then the tree is a leaf.

• If n = 2^{h}, then T_{n} is a complete binary tree (all leaves are at level h). Tree T_{n+1} is the tree of height h + 1 whose left subtree is T_{n} and whose right subtree is a single leaf.

• If n is not a power of 2, then expand the leftmost leaf which is not at the largest level, as described above.

It is also interesting to consider the inverse process of obtaining T_{n} from T_{n+1}. The inverse rule is very simple: Replace the rightmost equal pair ℓ_{j} = ℓ_{j+1} by ℓ_{j} − 1.

We could also have defined a code by the number of internal nodes at each level in the corresponding tree. Given a code of height h, let [τ_{0}, τ_{1}, …, τ_{h−1}] be the sequence in which τ_{i} is the number of internal nodes at level h. For our example codes given earlier, the corresponding level counts are [1, 1, 2], [1, 2, 1], [1, 1, 1, 1]. These counts clearly must satisfy

τ_{i} ≤ 2τ_{i−1}, for 1 ≤ i ≤ h − 1 and
τ_{0} + τ_{1} + ⋯ + τ_{h−1} = n − 1.

Subject to these two constraints M(n, h) is the largest value that τ_{h−1} can attain.

Let k be the largest level for which τ_{k} < 2τ_{k−1}. The greedy algorithm simply replaces τ_{k} by 1 + τ_{k}.

Lemma 3.1. Let τ_{0}, τ_{1}, ..., τ_{h−1} be the number of vertices at each level for the tree T_{n,h} and suppose that t_{0}, t_{1}, ..., t_{h−1} are the vertex numbers by level for any other tree T with n leaves and height h. For any 0 ≤ j ≤ h − 1,

τ_{j} + ⋯ + τ_{h−1} ≥ t_{j} + ⋯ + t_{h−1}.

Proof. For any h, the result is true for n = h+1 since there is only one tree with h+1 leaves and height h. Similarly it is true for n = 2^{h}.

Assume the result is true for all trees with n (for some n < 2^{h}) leaves and height h. Let τ′_{1}, τ′_{2}, …, τ′_{h−1} be the vertex numbers by level for T_{n+1,h}. Note that for some k > 0, we have τ′_{k} = 1 + τ_{k} and τ′_{j} = τ_{j} for all j ≠ k. By the greedy algorithm τ_{h−1} = 2τ_{h−2}, …, τ_{k+1} = 2τ_{k}, but τ_{k} < 2τ_{k−1}. Let T′ be any tree with n + 1 leaves and height h and suppose that T is the tree with n leaves and height h formed by removing from T′ the rightmost pair of leaves at level h. Suppose that t_{0}, t_{1}, …, t_{h−1} are the vertex numbers by level for T. By induction, we assume that t_{j} + ⋯ + t_{h−2} + t_{h−1} ≤ τ_{j} + ⋯ + τ_{h−2} + τ_{h−1} for all 0 ≤ j ≤ h − 1. Let t′_{0}, t′_{1}, …, t′_{h−1} be the vertex numbers by level for for T′. Note that t′_{h−1} = 1+t_{h−1} and t′_{j} = t_{j} for all j < h − 1. For all i ≤ k, we see that t′_{i} + ⋯ + t′_{h−1} ≤ τ′_{i} + ⋯ + τ′_{h−1}.

Suppose t′_{i} + ⋯ + t′_{h−1} > τ′_{i} + ⋯ + τ′_{h−1} for some i > k. Let m ≥ i be the smallest index such that t′_{m} > τ′_{m} = τ_{m}. Since m > k we have τ_{m} = 2τ_{m−1} = 2τ′_{m−1}. Since m was chosen to be smallest τ′_{m−1} ≥ t′_{m−1}. Putting these inequalities together we have t′_{m} > 2t′_{m−1} which is a contradiction. Thus t′_{i} + ⋯ + t′_{h−1} ≤ τ′_{i} + ⋯ + τ′_{h−1} for all i and the result is true by induction. □

Theorem 3.2. The greedy algorithm produces optimal trees.

Proof. Let t_{h−1} be the number of internal nodes in some code with n leaves and height h. The previous lemma tells us that τ_{h−1} ≥ t_{h−1}, where τ_{h−1} is the number of internal nodes at level h − 1 in T_{n,h}. □

Corollary 3.3. The largest number of 1’s in a partition of 2^{h} into powers of 2 consisting of n parts is M(n, h).

Proof. Multiply the partition of 1 described above by 2^{h} to obtain a partition of 2^{h}. □

Define a(n) to be the maximum number of leaf pairs at the largest level, taken over all binary trees with n leaves. In other words, a(n) = max M(n, h) : 1 ≤ h ≤ n − 1.

Corollary 3.4. For any n, we have a(n) = M(n, ⌈lg n⌉) = a_{1}(n − 1).

Proof. For any k > h = ⌈lg n⌉ construct a optimal tree of height k with n leaves using the greedy algorithm. The tree T_{n,k} has a subtree attached to an interior vertex at level k − h which is ismorphic to T_{n−k+h,h}. Clearly M(n − k + h, h) ≤ M(n, h) and thus a(n) = M(n, ⌈lg n⌉). The tree T_{1}(n) from Section 2 which defines the sequence a_{1}(n) has n+1 leaves (since it has n interior vertices) and is equal to the greedy tree for M(n + 1, ⌈lg(n + 1)⌉). Only the order in which the vertices are added is different since we add the vertices from the bottom in constructing T_{1}(n). □

Similarly define b(n) by the equation b(n) = M(n + h, h) for h + 1 ≤ n + h ≤ 2^{h}.

Corollary 3.5. The sequence b is well-defined and b(n) = a_{0}(n).

Proof. For a given n, let h be the smallest height such that n+h ≤ 2^{h}. For any larger height k > h construct a optimal tree of height k with n + k leaves using the greedy algorithm. The tree T_{n+k,k} has a subtree attached to an interior vertex at level k − h which is equal to T_{n+h,h}. Thus M(n + k, k) = M(n + h, h). If h is the height of the nth subtree T_{n} which defines the sequence a_{0}, we see inductively that T_{n} has n + h − 1 internal nodes and thus n + h leaves. As before we see that T_{n} is equal to the greedy tree for M(n + h, h). Thus T_{n} has b(n) leaf pairs at the largest level h, and we see that b(n) = a_{0}(n). □

Thus we have shown that the first 2 meta-Fibonacci sequences in our family of sequences have concrete realizations as the solutions of optimization problems involving binary compact codes/trees.

4. Acknowledgements

We wish to thank Don Knuth, Jon Perry, Jeff Shallit, and Herb Wilf for helpful comments related to this research.

References

[1] J.-P. Allouche, J. Betrema, and J.O. Shallit, Sur des Points Fixes de Morphismes d’un Monoïde Libre, Informatique théorique et Applications, 23 (1989) 235–249.

[2] B.W. Conolly, Meta-Fibonacci Sequences, Chapter XII in S. Vajda, Fibonacci & Lucas Numbers, and the Golden Section, Ellis Horwood Limited, 1989.

[3] M. Khosravifard, M. Esmaeili, H. Saidi, and T.A. Gulliver, A Tree Based Algorithm for Generating All Possible Binary Compact Codes with N Codewords, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E86-A (2003) 2510–2516.

[4] D.E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, [5] Emily Norwood, The Number of Different Possible Compact Codes, IEEE Transactions on Information

Theory, vol. IT-13, no. 4, pp. 613–616, 1967.

[6] Jon Perry, Symmetric Ferrar Diagrams, website, http://www.users.globalnet.co.uk/

   ~perry/maths/symmetricferrars/symmetricferrars.htm, March 2005.

[7] S.M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Mathematics, 105 (1992) 227– 239.

Dept. of Mathematics, San Jose State University, USA

Dept. of Computer Science, University of Victoria, CANADA

URL: http://www.cs.uvic.ca/~ruskey