The Combinatorics of Certain k-ary Meta-Fibonacci Sequences

Frank Ruskey and Chris Deugau University of Victoria Victoria, BC V8W 3P6 Canada

                   ruskey@cs.uvic.ca
                   chrisde@gmail.com

Abstract

This paper is concerned with a family of k-ary meta-Fibonacci sequences described by the recurrence relation

a(n) = ∑_{i=1}^{k} a(n−i − (s−1) − a(n−i)),

where s may be any integer, positive or negative. If s ≥ 0, then the initial conditions are a(n) = 1 for 1 ≤ n ≤ s+1 and a(n) = n−s for s+1 < n ≤ s+k. If s ≤ 0, then the initial conditions are a(n) = n for 1 ≤ n ≤ k(−s + 1). We show that these sequences arise as the solutions of two natural counting problems: The number of leaves at the largest level in certain infinite k-ary trees, and (for s ≥ 0) certain restricted compositions of an integer. For this family of generalized meta-Fibonacci sequences and two families of related sequences we derive combinatorial bijections, ordinary generating functions, recurrence relations, and asymptotics (a(n) ∼ n(k − 1)/k). We also show that these sequences are related to a “self-describing” sequence of Cloitre and Sloane.

1 Introduction

A meta-Fibonacci recurrence relation is one of the form

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

where x(n) and y(n) are linear functions of n, typically of the form n − s. They are a particular type of nested recurrence relation, which are recurrence relations in which the right-hand side has a substring of the form a(a()). These recurrence relations have been investigated by several authors in recent years, but their general behavior remains rather mysterious (e.g., Guy [12](Problem E31), Pinn [18]). The most famous of these sequences is most likely that of Hofstadter [14], in which x(n) = y(n) = n. The Hofstadter sequence exhibits a markedly chaotic behavior for some choices of the initial values, and virtually nothing has been proven about it when Hofstadter’s original initial conditions are used, including the question of whether is defined for all values of n. Perhaps the most wellbehaved sequences in the family occur when x(n) = n and y(n) = n − 1 with the initial conditions a(1) = a(2) = 1. For a given parameter s ≥ 0, Jackson and Ruskey [15] showed that the sequences with x(n) = y(n) + 1 = n − s for s ≥ 0 are almost as well-behaved, so long as they have the appropriate initial conditions. The case of s = 1 was studied before by Tanny [21]. The case of s = 0 was considered before by Conolly [9].

Prior to the paper [15], no combinatorial interpretation was known for these sequences (i.e., they were not known to be the solution to some natural counting problem), nor were their generating functions known. The combinatorial interpretation given in [15] was based on binary trees. This paper, among several other things, extends the results of [15] to k-ary trees and to negative values of s.

We will refer to the sequences (a(1), a(2), …) that are solutions to the recurrence relation

a(n) = ∑_{i=1}^{k} a( n−i − (s−1) − a(n−i) )  (1)

as k-ary meta-Fibonacci sequences. This is a natural name for them because, as we shall see, they are related to k-ary trees and to k-ary numbers. The integer s is called the shift parameter; the reason that we use s−1 instead of s will become clear in the following section. These sequences were studied recently by Callaghan, Chew, and Tanny [5], building on the earlier work of Higham and Tanny [13]. It is known that k-ary meta-Fibonacci sequences are quite sensitive to their initial conditions. For example, consider Figures 1 and 2. These both show sequences generated by (1) for s = 0, but with different initial conditions. In Figure 1, a(1) = a(2) = a(3) = 1; in Figure 2, a(1) = 1, a(2) = 2, and a(3) = 1. Other initial conditions can give yet other behaviors. Our sequence, with s = 0 and k = 3, is the same as the sequence T_{0,3}(n + 2) of [5] for n ≥ 1 (e.g., Figure 1.5, p. 797). The paper [5] was mainly concerned with the recurrence relation (1) when the initial conditions are all 1’s. Because of the very different behavior of the two sequences, we are unable to use any of the results of [5], nor do the results overlap in any significant way.

The initial conditions used in this paper for a(n) when s ≥ 0 are

a(n) = 1 for 1 ≤ n ≤ s + 1 and a(n) = n − s for s + 1 < n ≤ s + k.  (2)

When s ≤ 0, the initial conditions are

a(n) = n for 1 ≤ n ≤ k(−s + 1).  (3)

We will show that, with the initial conditions (2) and (3), these sequences also occur in natural combinatorial settings, that they have a fairly elegant ordinary generating function, and determine their asymptotics. In particular, for any fixed s and k ≥ 2, we give three Figure 1: For 1 ≤ n ≤ 3400, the graph of a(n) − 2n/3, where a(n) = a(n−a(n−1))+a(n−1−a(n−2))+a(n−2−a(n−3)), with a(1) = a(2) = a(3) = 1. The lighter curve shows a(n) at even values of n, the darker curve shows a(n) at odd values of n.

Figure 2: For 1 ≤ n ≤ 3400, the graph of a(n) − 2n/3, where a(n) = a(n−a(n−1))+a(n−1−a(n−2))+a(n−2−a(n−3)), with a(1) = 1, a(2) = 2, and a(3) = 3.

new ways of interpreting the sequences; our interpretations are based on certain subtrees of unusually labeled infinite k-ary trees, on certain restricted compositions of an integer, and on certain self-referential sequences. From the first combinatorial interpretation, we can easily see that a(n) is monotone, that its consecutive terms increase by 0 or 1, and that therefore, the sequence hits every positive integer.

In general, it is difficult to obtain asymptotics of meta-Fibonacci sequences. The asymptotic suggested by Figure 1, was proven in [5] (Corollary 4.16 and Corollary 5.14), namely T (n) ∼ (k − 1)n/k. In Theorem 28 we show that the sequences with our initial conditions also are asymptotic to (k − 1)n/k.

Since our meta-Fibonacci sequences have the property that successive values are the same or increase by one, it is natural to investigate the sequence of positions where the values increase. We will show that those positions are intimately tied with such classic topics as the ruler function and certain morphisms.

Informally, we say that an integer sequence is self-referential if it is defined by a recurrence relation with cases that depend on the inclusion or not of previous values in the sequence. Examples may be found in Cloitre, Sloane, Vandermast [7] and Hofstadter [14]. Recently, Cloitre and Sloane [8] observed experimentally that the self-referential sequence (OEIS^{1} \underline{A045412}) defined by

1The OEIS is Neil Sloane’s online encyclopedia of integer sequences [19].

b(n) = \begin{cases}3, & if n = 1; \\ 1 + b(n − 1), & if n ∈ \{b(1), …, b(n − 1)\}; \\ 3 + b(n − 1), & if n ∉ \{b(1), …, b(n − 1)\}; \end{cases}  (4)

is related to a meta-Fibonacci recurrence relation, and asked for a proof. In Section 7, we will provide a proof, based on our tree interpretation of meta-Fibonacci sequences, for a generalized version of (4) where 3 is replaced by k + 1.

1.1 Organization

This paper is organized as follows. The first section is the introduction. Section 2 presents the basic correspondence between k-ary meta-Fibonacci sequences and the number of leaves at the lowest level in a certain infinite family of k-ary trees. In Section 3 we develop recursive descriptions of the differences, either 0 or 1, of successive numbers in k-ary meta-Fibonacci sequences. These recursive descriptions are used to derive generating functions for k-ary meta-Fibonacci sequences. In Section 4 we introduce another k-ary tree correspondence, this one based on postorder traversals. In Section 5 we analyze the positions of the 1’s in the sequences from Section 3, and generating functions are derived for these sequences. In Section 6 these generating functions are used to prove a correspondence with certain integer compositions (and partitions). A direct combinatorial proof is also provided. In Section 7 we prove the Cloitre-Sloane observation. In Section 8 we prove that the sequences also satisfy some non-nested recurrence relations. Finally, in Section 9 we conclude with some open problems.

A preliminary version of some portions of this paper appeared in Deugau and Ruskey [10].

2 Meta-Fibonacci Sequences and Complete k-ary Trees

Figure 3 shows part of an infinite ordered ternary tree F_{0,3}. For all k ≥ 2, a k-ary version of this tree, F_{0,k}, is defined in the natural way, with every non-leaf having k children. Hereafter, we call a node that is not a leaf, an internal node. In this tree all leaves are at the same level, level 0. The level of any internal node is defined to be one greater than the level of its children.

The forest of labeled trees in F_{0,k} consists of a succession of complete k-ary trees of sizes

1, \underbrace{1, 1, …, 1}_{k−1}, \underbrace{1+k, …, 1+k}_{k−1}, …, \underbrace{1+k+ ⋯ +k^{h}, …, 1+k+ ⋯ +k^{h}}_{k−1}, …  (5)

The nodes of these subtrees are labeled in preorder. In F_{0,k} there is a one-way infinite path of unlabeled nodes (drawn with rectangles in Figure 3), which we refer to as the delay path. The nodes along the delay path are called super-nodes and we think of them as being indexed starting at zero. The rightmost (k − 1) subtrees of supernode h are referred to as Figure 3: The tree F_{0,3}.

Figure 4: The tree F_{1,3}.

Figure 5: The tree F_{2,3}.

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

Table 1: The values of a_{s,k}(n), d_{s,k}(n), and p_{s,k}(n) for k = 2, 3, s = −1, 0, 1, 2, and 1 ≤ n ≤ 19.

subforest h, where the natural number h is the common height of the trees in the subforest. For instance, the first super-node is the parent of subforest 1, the second super-node is the parent of subforest 2, and so on. We will now generalize to F_{s,k} first for s > 0 and then for s < 0.

For s ≥ 0, the unlabeled structure of the tree is the same as for F_{0,k}; it is mainly the labeling of the supernodes that changes. The trees F_{1,3} and F_{2,3} are shown in Figures 4 and 5. Except along the delay path, each subtree is again labeled in preorder. The delay path is parameterized by a value s that gives the delay between the preorder counts of successive trees, where the delay is applied after the leftmost subtree of a given size, and only along the delay path. Alternatively, we can think of each super-node as containing s ordinary nodes; this is illustrated in the figures. Note that, conceptually, the nodes of the delay path occur in between the underbraces in (5), with the leftmost super-node occurring to the left of the first brace.

We now generalize the trees for s ≤ 0 and k ≥ 2. The idea here is that only certain nodes get labels, and, as before, those that get labels are labeled in preorder. Every leaf is labeled. For all levels ℓ > 0, the leftmost −s + 1 nodes at level ℓ are unlabeled, and all other nodes Figure 6: The tree F_{−1,2}.

Figure 7: The tree F_{−2,2}.

Figure 8: The tree F_{−1,3}. are labeled. We sometimes say that an unlabeled node is empty. The trees F_{−1,2}, F_{−2,2}, and F_{−1,3}, are shown in Figures 6, 7, and 8, respectively.

Denote by T_{s,k}(n) the tree induced from F_{s,k} by the nodes with labels 1, 2, …, n. The actual number of nodes in T_{s,k}(n) could be more or less than n depending on the values of s and n. When we use the term “n-th node” or “node n”, we mean the node whose label includes n. Define a_{s,k}(n) to be the number of nodes at the bottom level (i.e., level 0) in T_{s,k}(n). Also define d_{s,k}(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,k}(n) to be the positions occupied by the 1’s in the d_{s,k}(n) sequence. Since T_{s,k}(0) is an empty tree, it has no nodes at the bottom level. Therefore, it makes sense to define a_{s,k}(0) = d_{s,k}(0) = p_{s,k}(0) = 0. Table 1 gives the values of a_{s,k}(n), d_{s,k}(n), and p_{s,k}(n) for k = 2, 3, s = −1, 0, 1, 2 and 1 ≤ n ≤ 19. The values of all of these table entries for s ≥ 0, as well as values for k = 4, are in the OEIS (as sequences \underline{A006949}, \underline{A046699}, \underline{A079559}, \underline{A101925}, and \underline{A120501}–\underline{A120532}). For fixed s these numbers are related as follows,

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

In the sequel we will often drop the s, k subscripts or only the k subscript, since our discussion will be for fixed values of these parameters, and it will make the notation less cumbersome; for example, we do so in the next lemma.

Lemma 1. Let 1 ≤ i ≤ k. The quantity

a(n−i − (s−1) − a(n−i))

is the number of leaves in T_{s,k}(n) that are the i-th child of their parent, if

• s ≥ 0 and n > s + k, or

• s ≤ 0 and n > k(−s + 1).

Proof. Let f(i) denote the number of leaves that are the i-th child of their parent in T_{s,k}(n), and define \overline{a}(n) = a(n − (s−1) − a(n)). We will show that f(i) = \overline{a}(n − i) for 1 ≤ i ≤ k.

First, observe that if all the leaves at the last level are removed from the infinite tree F_{s,k}, then the same unlabeled infinite tree structure remains. We now define a process, called chopping, that takes T_{s,k}(n) and returns the tree chop(T_{s,k}(n)) obtained by removing all the a(n) leaves at the last level, and then relabeling so that chop(T_{s,k}(n)) = T_{s,k}(n′) for some n′. If s > 0 and n > s + k, the leftmost super-node is made into an ordinary node by subtracting by s − 1 from the number of labels in the tree; if s ≤ 0 and n > k(−s + 1), the bottom −(s − 1) empty nodes are made into labeled leaves, again by subtracting s − 1 from the number of nodes in the tree. Recall that T_{s,k}(n) contains n labels, although the number of nodes that it contains will be different unless s = 1. By our discussion above, in chop(T_{s,k}(n)) = T_{s,k}(n′)

• the number of labels is n′ = n − (s − 1) − a(n), and

• the number of nodes is n − a(n).

It therefore follows that at the penultimate level in T_{s,k}(n)

• the number of labels is \overline{a}(n) + (s − 1), and

• the number of nodes is \overline{a}(n) = a(n − (s−1) − a(n)).

The latter statement is used below.

We now break the proof into two cases, depending on whether the n-th node is a leaf or not. If the n-th node is not a leaf, then

f(1) = f(2) = ⋯ = f(k) = \overline{a}(n − 1),

because every leaf has all k siblings and the number of parents of those leaves is \overline{a}(n − 1), the number of penultimate nodes in T_{s,k}(n − 1). We must use \overline{a}(n − 1) and not \overline{a}(n) because n could be a penultimate node, but then it has no children in T_{s,k}(n); however, every other penultimate node has k leaves. On the other hand,

\overline{a}(n − 1) = \overline{a}(n − 2) = ⋯ = \overline{a}(n − k)

because none of the nodes n − 1, n − 2, …, n − k can be penultimate nodes (note that every penultimate node is followed by k leaves). Thus f(i) = \overline{a}(n − i) for 1 ≤ i ≤ k in this case.

In the other case, node n is a leaf. Assume that n is the r-th child of its parent. Then

f(1) = ⋯ = f(r) and f(r+1) = ⋯ = f(k),

where f(r) = 1+f(r+1). Since n is the last leaf, its parent is the last penultimate node; thus f(r) = \overline{a}(n) = \overline{a}(n − 1). Note that \overline{a}(n − 1) = ⋯ = \overline{a}(n − r) because nodes n, …, n − r + 1 are all leaves, and so their removal does not change the number of penultimate nodes. Also, \overline{a}(n − r − 1) = ⋯ = \overline{a}(n − k), because node n − r is at the penultimate level and nodes n − r − 1, …, n − k + 1 are not. Since, \overline{a}(n − r) = 1 + \overline{a}(n − r − 1), we have shown that f(i) = \overline{a}(n − i) for 1 ≤ i ≤ k, which finishes the proof.

Theorem 2. If (s ≥ 0 and n > s+k) or (s ≤ 0 and n > k(−s + 1)), then

a(n) = ∑_{i=1}^{k} a(n − i − (s−1) − a(n−i)).  (7)

If s ≥ 0, then the base cases are a(n) = 1 for 1 ≤ n ≤ s + 1, and a(n) = n − s for s + 1 < n ≤ s + k. If s ≤ 0, then the base cases are a(n) = n for 1 ≤ n ≤ k(−s + 1).

Proof. The base cases are easy to check. Equation (7) follows immediately from Lemma 1, since every leaf is the i-th child of its parent for some unique i, where 1 ≤ i ≤ k.

3 Binary strings, morphisms, and D_{s,k}

Define D_{s,k} to be the infinite string d_{s,k}(1)d_{s,k}(2)d_{s,k}(3) · · ·. In this section we will uncover the recursive structure of this sequence.

Let D_{n,k} be the finite string defined by D_{0,k} = 1 and D_{n+1,k} = 0(D_{n,k})^{k}, the string with 0 at the start, followed by k repetitions of D_{n,k}. Let E_{n,k} be the finite string defined by E_{0,k} = 1 and E_{n+1,k} = (E_{n,k})^{k}0, the string starting with k repetitions of E_{n,k} followed by 0. As before, we will often drop the subscripts s and/or k when no confusion can arise.

Lemma 3. For all n ≥ 0, we have 0^{n}E_{n} = D_{n} 0^{n}.

Proof. Our proof is by induction on n. The statement is true if n = 0 since D_{0} = E_{0} = 1. Assuming that it is true for n, for n + 1 we have

0^{n+1}E_{n+1} = 0 0^{n}(E_{n})^{k}0 = 0 0^{n}E_{n}(E_{n})^{k−1}0 = 0 D_{n}0^{n}(E_{n})^{k−1}0 = ⋯
⋯ = 0 (D_{n})^{k} 0^{n} 0 = D_{n+1} 0^{n+1}.

Lemma 4. For n ≥ 0 and k ≥ 2,

D_{0}(D_{0})^{k−1}(D_{1})^{k−1} ⋯ (D_{n})^{k−1} = (E_{n})^{k−1}(E_{n−1})^{k−1} ⋯ (E_{1})^{k−1}(E_{0})^{k−1}E_{0}.  (8)

Proof. Our proof is by induction on n. If n = 0, then (D_{0})^{k} = (E_{0})^{k} = 1^{k}. For the general case we will first prove, also by induction on n, that

(D_{n})^{k−1} = 0^{n} (E_{n})^{k−2} (E_{n−1})^{k−1} ⋯ (E_{1})^{k−1} (E_{0})^{k−1}E_{0}  (9)

Equation (9) is true if n = 0. For n + 1 we have

(D_{n+1})^{k−1} = (D_{n+1})^{k−2} D_{n+1}
= (D_{n+1})^{k−2} 0 (D_{n})^{k}
= (D_{n+1})^{k−2} 0 D_{n} (D_{n})^{k−1}
= (D_{n+1})^{k−2} 0 D_{n} 0^{n} (E_{n})^{k−2} (E_{n−1})^{k−1} ⋯ (E_{1})^{k−1} (E_{0})^{k−1}E_{0}
= (D_{n+1})^{k−2} 0^{n+1}E_{n} (E_{n})^{k−2} (E_{n−1})^{k−1} ⋯ (E_{1})^{k−1} (E_{0})^{k−1}E_{0}
= 0^{n+1}(E_{n+1})^{k−2} (E_{n})^{k−1} (E_{n−1})^{k−1} ⋯ (E_{1})^{k−1} (E_{0})^{k−1}E_{0}.

In a somewhat similar fashion we may also prove by induction on n that

(E_{n})^{k−1} (E_{n−1})^{k−1} ⋯ (E_{1})^{k−1} (E_{0})^{k−1} E_{0} 0^{n+1} = E_{n+1}.  (10)

Now back to the proof of the lemma. Assuming that it is true for n, then for n + 1,

D_{0}(D_{0})^{k−1}(D_{1})^{k−1} ⋯ (D_{n})^{k−1}(D_{n+1})^{k−1}

= (E_{n})^{k−1}(E_{n−1})^{k−1} ⋯ (E_{1})^{k−1}(E_{0})^{k} (D_{n+1})^{k−1}
= (E_{n})^{k−1}(E_{n−1})^{k−1} ⋯ (E_{1})^{k−1}(E_{0})^{k} 0^{n+1} (E_{n+1})^{k−2}(E_{n})^{k−1} ⋯ (E_{1})^{k−1}(E_{0})^{k−1}E_{0}
= E_{n+1} (E_{n+1})^{k−2}(E_{n})^{k−1} ⋯ (E_{1})^{k−1}(E_{0})^{k−1}E_{0}
= (E_{n+1})^{k−1}(E_{n})^{k−1} ⋯ (E_{1})^{k−1}(E_{0})^{k−1}E_{0}.

The first equality follows from the inductive assumption; the second follows from (9); the third follows from (10).

The following Theorem gives explicit expressions for D_{s} in terms of D_{n}. In a sense, it provides string representations of the tree structures F_{s,k} introduced earlier.

Theorem 5. For all k ≥ 2 and s ≥ 0,

D_{s,k} = D_{0}0^{s}(D_{0})^{k−1}0^{s}(D_{1})^{k−1}0^{s}(D_{2})^{k−1} ⋯  (11)

If s = 0, then

D_{0,k} = D_{0}(D_{0})^{k−1}(D_{1})^{k−1}(D_{2})^{k−1}(D_{3})^{k−1} ⋯ = E_{∞}.  (12)

For all k ≥ 2 and s ≤ 0,

D_{s,k} = D_{0}^{−s+1}(D_{0})^{r}(D_{1})^{r}(D_{2})^{r}(D_{3})^{r} ⋯,  (13)

where r = (−s + 1)(k − 1).

Proof. Equation (11) comes from the definition of F_{s,k}. The 0^{s} factors represent the placement of the super-nodes.

The first equality in (12) is implied by (13). The second equality in (12) comes from Lemma 4. Since E_{n} is a prefix of E_{n+1}, the expression E_{∞} is well-defined. Hence D_{0,k} = E_{∞}.

Define a node in F_{s,k} to be a root if it is not empty but its parent is empty. At level 0 there are (−s + 1)k roots (i.e., the (−s + 1)k leaves have no parents). At level ℓ > 0 there are (−s + 1)k − (−s + 1) = (−s + 1)(k − 1) = r roots. Note that in a preorder traversal, we encounter all subtrees with roots at level ℓ before encountering any with roots at level ℓ + 1. Furthermore, each subtree with a root at level ℓ produces the sequence D_{ℓ}. Thus overall, we get the sequence on the righthand side of the equality (13).

3.1 Using morphisms to describe D_{s}

Let ε denote the empty string. A morphism is a function f : Σ → Σ^{∗}, where Σ is an alphabet and Σ^{∗} is the set of all strings over that alphabet. The function f is extended to a mapping over Σ^{∗} by application to each symbol of the string: if a_{1}a_{2} ⋯ a_{n} ∈ Σ^{∗}, then f(a_{1}a_{2} ⋯ a_{n}) = f(a_{1})f(a_{2}) ⋯ f(a_{n}). Also, f(ε) = ε.

It is worth observing that D_{n} is the n-th iterate of the morphism 0 ↦ 0 and 1 ↦ 01^{k}, with D_{0} = 1; let us call this morphism σ. Similarly, E_{n} is the n-th iterate of the morphism 0 ↦ 0 and 1 ↦ 1^{k}0, with E_{0} = 1; let us call this morphism τ. Various properties of this morphism, particularly in the case where k = 2, are explored in Allouche, Betrema, and Shallit [2]. Here’s the induction proof of the crucial property, E_{n} = τ^{n}(1), of τ.

E_{n+1} = (E_{n})^{k}0 = (τ^{n}(1))^{k}0 = τ^{n}(1^{k}0) = τ^{n}(τ(1)) = τ^{n+1}(1).

Note that E_{n+1} = τ(E_{n}).

For a binary string u, define

ξ_{s,k}(u) = \begin{cases}0^{s}1^{k−1}, ·σ(u) & if s ≥ 0; \\ 1^{(−s+1)(k−1)}, ·σ(u) & if s ≤ 0. \end{cases}  (14)

As usual, the k will be dropped from the subscript if no confusion can arise. Consider the calculation of ξ_{−2,2}^{4}(ε) shown below.

ξ_{−2}^{4}(ε) = ξ_{−2}^{3}(111 · σ(ε) ) = ξ_{−2}^{3}(111 )
= ξ_{−2}^{2}(111 · σ(111) ) = ξ_{−2}^{2}(111 011 011 011 )
= ξ_{−2}^{1}(111 011011011 0011011 0011011 0011011 )
= 111 011011011 001101100110110011011
000110110011011 000110110011011 000110110011011.

This is a prefix of D_{−2,2}, except for a missing 111 at the front. Below we show that this holds in general.

Theorem 6. For all k ≥ 2

D_{s,k} = \begin{cases}1, ·ξ_{s}^{∞}(ε) & if s ≥ 0; \\ 1^{−s+1} · ξ_{s}^{∞}(ε), & if s ≤ 0. \end{cases}  (15)

Proof. For this proof we employ the tree interpretation of D_{s} in a new way. Imagine that instead of chopping the last level, we are instead grafting on a new level of leaves by transforming each existing leaf into an internal node and k leaves. In general, this process is described by σ; a 1 is transformed into a 01^{k}. However, it does not describe what happens at the very leftmost part of the tree; we must be careful about supernodes (for s > 0) and empty nodes (for s ≤ 0).

If s > 0 and we are grafting a new level, then the leftmost leaf becomes a supernode with s labels and k children, all of whom are leaves. By the way supernodes are labeled, that initial 1 becomes 10^{s}1^{k−1}. Since the initial 1 is expanded in a special way, we do the overall expansion by prepending 0^{s}1^{k−1} before applying σ in (14), and then tacking on the initial 1 as a final step in (15).

If s ≤ 0 and we are grafting a new level, then the leftmost −s + 1 leaves become empty nodes, each with k children, all of whom are leaves. The remaining (−s + 1)k − (−s + 1) = (−s + 1)(k − 1) leaves that are children of empty nodes before the graft can be expanded in the normal manner on the next grafting. Thus (14) holds. Those initial −s + 1 leaves are accounted for in (15) by the 1^{−s+1}.

3.2 Generating functions for D_{s}

Generally, if S = s(1)s(2)s(3) ⋯ is a string then we use S(z) to denote the ordinary generating function S(z) = ∑_{i≥1} s(i)z^{i}. However, for the polynomials D_{n}(z) and E_{n}(z) we think of the sequence as being indexed starting at 0. Let A_{s}(z) and D_{s}(z) denote the ordinary generating functions of the a_{s,k}(n) and d_{s,k}(n) sequences, respectively. Directly from the definitions we get the equation shown below:

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

In the notation for the q-binomial coefficients [6], we have [_{1}^{h}]_{k} = 1 + k + ⋯ + k^{h−1} = (k^{h} − 1)/(k − 1). In this paper, the bottom term will always be one, so we will use the notation [h]_{k} to represent [_{1}^{h}]_{k}. When no confusion can arise the subscript k will be dropped. 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). If S is a string, then |S| denotes the number of characters in S.

Lemma 7. For n ≥ 0, we have |D_{n}| = |E_{n}| = [n + 1] = 1 + k + ⋯ + k^{n}.

Proof. From their definitions, it is obvious that |D_{n}| = |E_{n}|. We know that D_{0} = 1, so |D_{0}| = 1 = [0 + 1]. Since D_{n+1} = 0(D_{n})^{k}, inductively, |D_{n+1}| = 1 + |(D_{n})^{k}| = 1 + k[n + 1] = 1 + k(1 + k + ⋯ + k^{n}) = [n + 2].

Lemma 8.

D_{n}(z) = z^{n+1}(1+z^{[1]}+z^{2[1]}+ ⋯ +z^{(k−1)[1]}) ⋯ (1+z^{[n]}+ ⋯ +z^{(k−1)[n]})
= z^{n+1} ∏_{i=1}^{n} ∑_{j=0}^{k−1} z^{j[i]} = z^{n+1} ∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} ,

E_{n}(z) = z(1+z^{[1]}+z^{2[1]}+ ⋯ +z^{(k−1)[1]}) ⋯ (1+z^{[n]}+ ⋯ +z^{(k−1)[n]})
= z ∏_{i=1}^{n} ∑_{j=0}^{k−1} z^{j[i]} = z ∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} .

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

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

Similarly, E_{0}(z) = z and E_{n+1}(z) = (1 + z^{[n+1]} + z^{2[n+1]} + ⋯ + z^{(k−1)[n+1]})E_{n}(z). The results now follow by induction.

Observe that Lemma 8 implies that D_{n} is a shifted version of E_{n} (move trailing 0’s from front to back). This observation gives another proof of Lemma 3.

Corollary 9.

D_{0}(z) = z ∏_{i≥1} ∑_{j=0}^{k−1} z^{j[i]} = z ∏_{i≥1} \frac{1 − z^{k[i]}}{1 − z^{[i]}} .

Proof. Follows from Lemma 8 and the equation D_{0} = E_{∞} from Lemma 5. Theorem 10. The generating function D_{s,k}(z), for s ≥ 0, is equal to

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

(16)

Proof. We translate the string D_{0}0^{s}(D_{0})^{k−1}0^{s}(D_{1})^{k−1}0^{s}(D_{2})^{k−1}0^{s} ⋯ from Lemma 21 into its generating function. Since

|D_{0}0^{s}(D_{0})^{k−1}0^{s} ⋯ (D_{n−1})^{k−1}0^{s}| = s + 1 + ∑_{i=0}^{n−1}((k − 1)[i + 1] + s) = s + n(s − 1) + [n + 1],

we can write

D_{s}(z) = z + ∑_{n≥0} z^{s+n(s−1)+[n+1]}D_{n}(z)(1 + z^{|D_{n}|} + ⋯ + z^{(k−2)|D_{n}|})
= z + ∑_{n≥0} ∑_{i=1}^{k−1} z^{s+n(s−1)+i[n+1]}D_{n}(z)  (17)
= z + ∑_{n≥0} ∑_{i=1}^{k−1} z^{s+n(s−1)+i[n+1]+1}x_{1}x_{2} ⋯ x_{n},

where x_{i} = z(1 + z^{[i]} + ⋯ + z^{(k−1)[i]}) = z[k]. Recall that D_{n}(z) = zx_{1}x_{2} ⋯ x_{n} and expand the summation to obtain

D_{s}(z) = z + (z(z^{s+[1]}+ ⋯ +z^{s+(k−1)[1]})) + (zx_{1}(z^{2s−1+[2]}+ ⋯ +z^{2s−1+(k−1)[2]})) + ⋯
= z(1 + (z^{s+[1]}+ ⋯ +z^{s+(k−1)[1]}) + (x_{1}(z^{2s−1+[2]}+ ⋯ +z^{2s−1+(k−1)[2]})) + ⋯
= z(1 + z^{s+[1]}((1+ ⋯ +z^{(k−2)[1]}) + (x_{1}(z^{s−1+k[1]}+ ⋯ +z^{s−1+(k−2)[2]+k[1]})) + ⋯
= z(1 + z^{s+k^{0}}((1+ ⋯ +z^{(k−2)[1]}) + z^{s−1+k[1]}x_{1}((1+ ⋯ +z^{(k−2)[2]}) + ⋯
= z (1 + z^{s+k^{0}} (\frac{1 − z^{(k−1)[1]}}{1 − z^{[1]}} + z^{s+k^{1}} \frac{1 − z^{k[1]}}{1 − z^{[1]}} (\frac{1 − z^{(k−1)[2]}}{1 − z^{[2]}} + z^{s+k^{2}} \frac{1 − z^{k[2]}}{1 − z^{[2]}} ⋯

Theorem 11. For all s ≥ 0 and k ≥ 2,

A_{s,k}(z) = \begin{cases}\frac{z}{1 − z} ∏_{i≥1} \frac{1 − z^{k[i]}}{1 − z^{[i]}} , & if s = 0; \\ z \frac{1 − z^{s}}{1 − z} ∑_{n≥0} ∏_{i=1}^{n} z^{s} \frac{1 − z^{k[i]}}{1 − z^{[i]}} ; & if s > 0. \end{cases}

Proof. The case for s = 0 is simply obtained by dividing D_{0}(z) from Corollary 9 by (1 − z). For the case s > 0, call the right side of the equation R(z), and multiply it by (1 − z). We get

(1 − z)R(z) = z(1 − z^{s}) ∑_{n≥0} ∏_{i=1}^{n} z^{s} \frac{1 − z^{k[i]}}{1 − z^{[i]}}

= z + z ∑_{n≥1} z^{sn} ∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} − z^{s+1} ∑_{n≥0} ∏_{i=1}^{n} z^{s} \frac{1 − z^{k[i]}}{1 − z^{[i]}}

= z + z ∑_{n≥1} z^{sn} ∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} − z^{s+1} ∑_{n≥1} ∏_{i=1}^{n−1} z^{s} \frac{1 − z^{k[i]}}{1 − z^{[i]}}

= z + z ∑_{n≥1} z^{sn} (∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} − ∏_{i=1}^{n−1} \frac{1 − z^{k[i]}}{1 − z^{[i]}} )

= z + z ∑_{n≥1} z^{sn} (\frac{1 − z^{n[i]}}{1 − z^{[i]}} − 1) (∏_{i=1}^{n−1} \frac{1 − z^{k[i]}}{1 − z^{[i]}} )

= z + ∑_{n≥1} z^{sn+1} ∑_{j=1}^{k−1} z^{j[n]} ∏_{i=1}^{n−1} \frac{1 − z^{k[i]}}{1 − z^{[i]}}

= z + ∑_{n≥0} z^{sn+s+1} ∑_{j=1}^{k−1} z^{j[n+1]} ∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} ,

where the third equality comes from taking the n = 0 term out of the first summation, the fourth equality comes from substituting n − 1 for n, the seventh equality comes from collecting like terms, the eighth comes from factoring, the ninth comes from the fact that \frac{k^{h}−1}{k−1} = 1 + k + ⋯ + k^{h−1}, and the final equality comes from substituting n + 1 for n. The remaining equation after the last step is equal to D_{s}(z) by (17), and therefore we have the generating function for A_{s}(z) as determined above.

We have not managed to find a particularly nice form of D_{s}(z) for s < 0. However, it is possible to derive that, for s < 0,

D_{s}(z)/z = \frac{1 − z^{−s+1}}{1 − z} + z^{−s+1} ∑_{n≥0} z^{r([1]+[2]+···+[n])} \frac{1 − z^{r[n+1]}}{1 − z^{[n+1]}} ∏_{i=1}^{n} \frac{1 − z^{k[i]}}{1 − z^{[i]}} ,

by using (13), the expression for D_{n}(z) in Lemma 8, and the fact that |D_{n}| = [n + 1]. As before, r = (−s + 1)(k − 1). It would be nice to simplify this generating function.

4 Compositions (and partitions) of an integer

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

n_{0} + n_{1} + ⋯ + n_{m} = n where n_{i} ∈ {1, 2^{i}} for i = 0, 1, …, m.

He uses a notation similar to ⟨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 [17]. We call these rules specifications. Jackson and Ruskey [15] showed that if s > 0, then a_{s,2}(n) counted the number of compositions of n with specification

⟨1, 2, …, s⟩ + ⟨s, 2 + s − 1⟩ + ⟨s, 4 + s − 1⟩ + ⟨s, 8 + s − 1⟩ + · · · .

We extend this result to any k > 1 and to s = 0. So far, we have been unable to find a composition interpretation for s < 0.

Corollary 12. If s = 0, then the number of compositions of n with specification

ℤ^{+} + ⟨0, [1], …, (k − 1)[1]⟩ + ⟨0, [2], …, (k − 1)[2]⟩ + ⋯

is a_{0,k}(n). For s ≥ 1, the number of compositions of n with specification

⟨1, 2, …, s⟩ + ⟨s, s + [1], …, s + (k − 1)[1]⟩ + ⟨s, s + [2], …, s + (k − 1)[2]⟩ + ⋯

is a_{s,k}(n).

Proof. This is clear from the generating function of A_{s,k}(z) given in Theorem 11 by observing that z(1 − z^{s})/(1 − z) = (z + z^{2} + ⋯ + z^{s}). Substituting into our summation gives

(z+z^{2}+ ⋯ +z^{s})(1 + z^{s}(1+z^{[1]}+ ⋯ +z^{k[1]}) + z^{s}(1+ ⋯ +z^{k[1]})z^{s}(1+ ⋯ +z^{k[2]}) + ⋯

As an example, a_{2,3}(20) = 10, and the 10 corresponding compositions are given below:

1+2+2+15, 1+3+2+2+2+2+2+2+2+2, 1+3+6+2+2+2+2+2, 1+3+10+2+2+2, 1+4+15, 2+2+2+2+2+2+2+2+2+2, 2+2+6+2+2+2+2+2, 2+2+10+2+2+2, 2+4+6+2+2+2+2, 2+4+2+2+2+2+2+2+2.

Since a_{2,3}(n) counts both the number of bottom level nodes of the tree T_{2,3}(n) and these compositions, there should be a direct one-to-one correspondence between the bottom level nodes and the compositions. This is the subject of the subsection to follow.

4.1 A result of Allouche, Betrema, and Shallit

The generating function for D_{0}(z)/z given in Corollary 9 can be written as

∏_{i≥1} \frac{1 − z^{k[i]}}{1 − z^{[i]}} = ∏_{i≥1}(1 + z^{[i]} + z^{2[i]} + ⋯ + z^{(k−1)[i]}).

This is the generating function for the number of partitions of n of the form

n = ε_{1}[1] + ε_{2}[2] + ε_{3}[3] + ⋯,  (18)

where ε_{i} ∈ {0, 1, …, k − 1}. Since (k − 1)[1] + (k − 1)[2] + ⋯ + (k − 1)[m] < [m + 1], if there is a partition of the form (18), then it is unique (of course, we already know this since D_{s} is a 0-1 sequence). The values of n expressible as in (18) are exactly the numbers of the form p_{0}(m) − 1. This relation between partitions of the form (18) and the D_{0} sequence (as generated by the morphism ρ) was noted in [2] for general k and proven in the case k = 2 (see the “Remarque” on page 241). Suppose that n can be written as (18). Then

(k − 1)n = ∑_{i≥1} ε_{i}(k^{i} − 1)
= ∑_{i≥1} ε_{i}k^{i} − ∑_{i≥1} ε_{i}
= m − ν_{k}(m),

where m is the integer ∑_{k≥1} ε_{i}k^{i}; note that m is divisible by k. Conversely, given the k-ary representation of an integer m divisible by k, we can recover an n expressible as in (18).

4.2 A one-to-one correspondence

This correspondence was discovered in collaboration with Carla Savage.

In the tree T_{s,k}(n) a path from a leaf to the root can be considered as a k-ary number m = (b_{d} ⋯ b_{1}b_{0})_{k}, so that

m = ∑_{j=0}^{d} b_{j}k^{j},

where b_{j} ∈ {0, 1, …, k − 1} and d + 1 is the length of the path. At the j-th edge of the path the child is the b_{j}-th child of its parent — counting from 0 and from left-to-right. For example, the leftmost path corresponds to (0 ⋯ 00)_{k}, and the right-most path to the k-ary representation of n − 1.

Define the mapping ψ that takes this k-ary number and returns the composition

ψ(m) = ∑_{j=0}^{d}(s + b_{j}(1 + k + ⋯ + k^{j})) = ∑_{j=0}^{d}(s + b_{j}[j]).

If s = 0, then transforming ψ(m) into a composition of n is simple:

n = (n − ψ(m)) + ψ(m).

This composition has the required specification.

Otherwise, assume that s > 0. We can now transform ψ(m) into a composition of n as follows:

n = (1 + ((n − ψ(m)) mod s)) + ψ(m) + s ⌊\frac{n − ψ(m)}{s}⌋;  (19)

that is, take ψ(m), add ⌊(n−ψ(m))/s⌋ parts s, and an initial part (1+((n−ψ(m)) mod s)). Note that the resulting composition is of specification

⟨1, 2, …, s⟩ + ⟨s, s + [1], …, s + (k − 1)[1]⟩ + ⟨s, s + [2], …, s + (k − 1)[2]⟩ + · · · . (20)

Below we continue the example that follows Corollary 12.

\begin{matrix}m & (b_{2}b_{1}b_{0})_{3} & ψ(m) & n = 20 \\ 0 & 000 & 2 + 2 + 2 & 2+2+2+2+2+2+2+2+2+2 \\ 1 & 001 & 3 + 2 + 2 & 1+3+2+2+2+2+2+2+2+2 \\ 2 & 002 & 4 + 2 + 2 & 2+4+2+2+2+2+2+2+2 \\ 3 & 010 & 2 + 6 + 2 & 2+2+6+2+2+2+2+2 \\ 4 & 011 & 3 + 6 + 2 & 1+3+6+2+2+2+2+2 \\ 5 & 012 & 4 + 6 + 2 & 2+4+6+2+2+2+2 \\ 6 & 020 & 2 + 10 + 2 & 2+2+10+2+2+2 \\ 7 & 021 & 3 + 10 + 2 & 1+3+10+2+2+2 \\ 8 & 022 & 4 + 10 + 2 & 2+4+10+2+2+2 \\ 9 & 100 & 2 + 2 + 15 & 1+2+2+15 \end{matrix}

In order to prove that this is a one-to-one correspondence we need the following lemma.

Lemma 13. If m corresponds to a root-to-leaf path in T_{s,k}(n) then n > ψ(m).

Proof. Let n′ be the rightmost leaf in T_{s,k}(n); thus n′ ≤ n. We count the number of nodes in the subtrees to the left of this path and then add in the 1 + s + d nodes on the path. The subtrees to the left of the path are the subtrees that remain when the path is removed. The number of extra nodes in the supernodes along the leftmost path (not counting the root) is d(s − 1); taking these nodes into account, each supernode now counts 1. Let (b_{d} ⋯ b_{1}b_{0})_{k} be the k-ary representation of n′. The number of nodes in the trees with roots at level j is

(1 + k + ⋯ + k^{j})b_{j}.

Thus the number of nodes to the left of the path is

d(s − 1) + ∑_{j=0}^{d}(1 + k + ⋯ + k^{j})b_{j}.

Therefore,

n′ = 1 + s + d + d(s − 1) + ∑_{j=0}^{d}(1 + k + ⋯ + k^{j})b_{j} = 1 + ∑_{j=0}^{d} s + (1 + k + ⋯ + k^{j})b_{j}.

Thus 1 + ψ(m) = n′ ≤ n, which implies that n > ψ(m).

Lemma 13 shows that (19) is always well-defined; every leaf corresponds to some unique composition of the correct specification. To go from a composition to a leaf we reverse the process. Given a composition x_{−1} + x_{0} + ⋯ + x_{t} of specification (20) consider the subcomposition x_{0} + ⋯ + x_{d} where d + 1 is the height of T_{s,k}(n); that is, d is the largest integer such that

n ≤ (s − 1)d + (1 + k + ⋯ + k^{d}).

For i = 0, 1, …, d we have x_{i} ∈ {s, s + [i + 1], …, s + (k − 1)[i + 1]}. If x_{i} = s + j[i + 1], then set b_{i} = j. This gives a k-ary number (b_{d} ⋯ b_{1}b_{0})_{k}, which will correspond to a leaf in T_{s,k}(n) if n is large enough, which it will be, because of the way that d was chosen.

5 A Postorder Labeling

In Section 2, we described the labeling of the infinite ordered k-ary trees F_{s,k}, and the relationship between these trees and the sequences a_{s,k}(n), d_{s,k}(n), and p_{s,k}(n). In this section we will describe an alternate labeling of these trees, one based on postorder rather than preorder, and show how this alternate labeling gives rise to the meta-Fibonacci sequences described earlier. The main difference is that the value of s is shifted by 1, in a sense to be made precise later.

We will use the notation F′_{s,k} to represent our postorder labeling. The tree F′_{s,k} has exactly the same shape as F_{s,k}; that is, it is a k-ary tree with all leaves at the same level and the number of labels assigned to each node is the same in both types of trees. However, the way that the labels are assigned is different. As before, the labels are the non-negative integers.

For s ≤ 0, the change is very simple; each subtree is labeled in postorder, not preorder. For s ≥ 0, each subtree that is not along the delay path is labeled in postorder. Let

v be a super-node along the delay path. We first label the left-most subtree of v. After the left-most subtree of v is labeled, v is labeled an additional s − 1 times (as opposed to previously, when we would label the super-node s times), increasing the label by one each time. Now we label the k − 1 remaining k-trees with a postorder traversal. After labeling the subtrees, we then finish labeling v by giving it 1 more label (so we have now labeled the super-node s−1+1 = s times). Figures 9 and 10 show the start of F′_{1,3} and F′_{2,3} respectively.

Define a′_{s,k}(n) to be the number of nodes at the bottom level of the tree T′_{s,k}(n), where T′_{s,k}(n) is the forest induced by the first n labeled nodes of F′_{s,k}. For example, referring to Figure 9, we see that a′_{1,3}(n) is

1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 18, 18, …,

which is equal to the sequence a_{0,3}(n) (See Table 1). Similarly, observe that a′_{2,3}(n) = a_{1,3}(n). The remainder of this section is devoted to proving that a′_{s,k} = a_{s−1,k} in general.

Let D′_{s,k} be the infinite string d′_{s,k}(1)d′_{s,k}(2)d′_{s,k}(3) ⋯, where d′_{s,k}(n) is 0 if node n in F′_{s,k} is an internal node, and is 1 if node n is a leaf node.

Figure 9: The tree F′_{1,3}.

Figure 10: The tree F′_{2,3}.

Theorem 14. For s ≥ 1,

D′_{s,k} = E_{0}0^{s−1}(E_{0})^{k−1}0^{s}(E_{1})^{k−1}0^{s}(E_{2})^{k−1}0^{s}(E_{3})^{k−1}0^{s} ⋯
= D_{0}0^{s−1}(D_{0})^{k−1}0^{s−1}(D_{1})^{k−1}0^{s−1}(D_{2})^{k−1} ⋯  (21)

For s ≤ 0, with r′ = (−s + 1)(k − 1) and r = (−s + 2)(k − 1),

D′_{s,k} = (E_{0})^{−s+1}(E_{0})^{r′}(E_{1})^{r′}(E_{2})^{r′}(E_{3})^{r′} ⋯
= (D_{0})^{−s+2}(D_{0})^{r}(D_{1})^{r}(D_{2})^{r}(D_{3})^{r} ⋯  (22)

Proof. We first deal with the case where s ≥ 1 and then the case where s ≤ 0.

Assume that s ≥ 1. The first equality comes from the definition of F′_{s,k}. First, notice that the E_{n} we defined at the beginning of Section 3 is equivalent to a postorder traversal of a k-tree of height n, with 1 representing the leaf nodes and 0 representing the internal nodes. For example, if k = 3, then E_{2} = 1110111011100 is obtained from the first 13 nodes of the tree in Figure 9, with the 0’s occuring in positions 4, 8, 12, 13.

We start with a single leaf node.

Then, we label the super-node s − 1 times, followed by labeling k − 1 k-trees of height 1, followed by labeling the super-node one last time. After labeling the first super-node we move on to the second one, where we again label the super-node s − 1 times, but now we have to label k − 1 k-trees of height 2 before labeling the super-node one last time. We continue in this manner, labeling every node in F′_{s,k}.

We now prove (21). It is easily seen that E_{0} 0^{s−1} (E_{0})^{k−1} = D_{0} 0^{s−1} (D_{0})^{k−1} since E_{0} = D_{0}. Now, using Lemma 3, we have

E_{0} 0^{s−1} (E_{0})^{k−1} 0^{s} (E_{1})^{k−1} 0^{s} (E_{2})^{k−1} 0^{s} (E_{3})^{k−1} ⋯
= D_{0} 0^{s−1} (D_{0})^{k−1} 0^{s} (E_{1})^{k−1} 0^{s} (E_{2})^{k−1} 0^{s} (E_{3})^{k−1} ⋯
= D_{0} 0^{s−1} (D_{0})^{k−1} 0^{s−1} (D_{1})^{k−1} 0^{s+1} (E_{2})^{k−1} 0^{s} (E_{3})^{k−1} ⋯
= D_{0} 0^{s−1} (D_{0})^{k−1} 0^{s−1} (D_{1})^{k−1} 0^{s−1} (D_{2})^{k−1} 0^{s+2} (E_{3})^{k−1} ⋯
= D_{0} 0^{s−1} (D_{0})^{k−1} 0^{s−1} (D_{1})^{k−1} 0^{s−1} (D_{2})^{k−1} 0^{s−1} (D_{3})^{k−1} · · · .

We now assume that s ≤ 0. The first equality follows from the definition of F′_{s,k}. Note that by Lemma 3,

(D_{n})^{k}0^{n+1} = 0^{n}(E_{n})^{k}0 = 0^{n}E_{n+1}.  (23)

We will use (23) to prove by induction on n that

(D_{0})^{−s}(D_{0})^{r}(D_{1})^{r}(D_{2})^{r} ⋯ (D_{n})^{r}0^{n+1} = (E_{0})^{−s+1}(E_{0})^{r′}(E_{1})^{r′}(E_{2})^{r′} ⋯ (E_{n})^{r′}E_{n+1}.

When n = 0 then it is easy to check that D_{0}^{−s+2}D_{0}^{r}0 = E_{0}^{−s+1}E_{0}^{r′}E_{1}. So assume that the equation above is true (for n). Note that r′ = r − k + 1. Then

(D_{0})^{−s+2}(D_{0})^{r}(D_{1})^{r}(D_{2})^{r} ⋯ (D_{n})^{r}(D_{n+1})^{r}0^{n+2}
= (D_{0})^{−s+2}(D_{0})^{r}(D_{1})^{r}(D_{2})^{r} ⋯ (D_{n})^{r}(D_{n+1})^{r−k}0^{n+1}(E_{n+2})
= (D_{0})^{−s+2}(D_{0})^{r}(D_{1})^{r}(D_{2})^{r} ⋯ (D_{n})^{r}0^{n+1}(E_{n+1})^{r−k}(E_{n+2})
= (E_{0})^{−s+1}(E_{0})^{r′}(E_{1})^{r′}(E_{2})^{r′} ⋯ (E_{n})^{r′}E_{n+1}(E_{n+1})^{r−k}(E_{n+2})
= (E_{0})^{−s+1}(E_{0})^{r′}(E_{1})^{r′}(E_{2})^{r′} ⋯ (E_{n})^{r′}(E_{n+1})^{r′}(E_{n+2})

Thus it is true for n + 1 and the proof is completed.

Corollary 15. Let a′_{s,k}(n) be the number of nodes at the bottom level of the tree T′_{s,k}(n) and let a_{s,k}(n) be the number of nodes at the bottom level of the tree T_{s,k}(n). Then, for all integers s,

a′_{s,k}(n) = a_{s−1,k}(n).

Proof. This follows from the above theorem. Notice that the second equality is the same as the sequence for D_{s−1,k} given in Lemma 21. It follows that the d(n) sequence for a′_{s,k} and a_{s−1,k} are the same, and therefore, the sequences are the same.

6 Analysis of labels on the leaves

The labels on the leaves of T_{s,k} are given by the sequences p_{s,k} (some examples are given in Table 1). In this section we determine an exact expression for these numbers and also a generating function for them. Using this exact expression we can determine their asymptotic value, and hence the asymptotic value of the a_{s,k} numbers. A number of connections with previous results in the literature are noted. Central to our results is the generalized ruler function.

6.1 The ruler function and its generalizations

Let r_{1}, r_{2}, r_{3}, r_{4}, ⋯ be the transition sequence of the k-ary reflected Gray code; in the case of k = 2 this sequence is also known as the “ruler function” (A001511). The generalized ruler sequence is R_{∞} where R_{1} = 1^{k−1} and R_{n+1} = (R_{n}, n + 1)^{k−1}, R_{n}.

Lemma 16. The ordinary generating function, R(z), of the generalized ruler function is

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

Proof. Observe that if all the 0’s are removed from the sequence r_{1}−1, r_{2}−1, r_{3}−1, r_{4}−1, … then the ruler function is again obtained. The non-zero values occur in the positions that are divisible by k. Thus the ruler function satisfies

R(z) = \frac{z}{1 − z} + R(z^{k}).  (25)

Equation (24) is obtained by iterating (25).

For further generating functions of this type, see the paper of Stephan [20].

6.2 A “morphism” related to the run lengths of the 0’s

We will now try to determine the sequence of integers, call it Z_{s}, of the lengths of runs of 0’s that occur in D_{s}. This sequence will effectively provide another characterization of D_{s} since the lengths of the runs of 1’s is k, except at the very beginning. We will employ Theorem 6. Let ρ denote the “morphism” that maps the integer t to the sequence of k integers t + 1, 1, …, 1, and let ρ′ map t to the sequence of k integers 1, …, 1, t + 1. Let ξ̄ be the following mapping of strings of integers to strings of integers.

ξ̄_{s}(u) = \begin{cases}(s + 1) · 1^{k−2} · ρ(u), & if s ≥ 0; \\ 1^{(−s+1)(k−1)} · ρ(u), & if s ≤ 0. \end{cases}  (26)

The infinite sequence ξ̄_{s}^{∞}(ε) is often used so we give it a name: X̄_{s} := ξ̄_{s}^{∞}(ε). For example,

X̄_{−1,2} = 1121213121312141213121 · · · .  (27)

Theorem 17. The sequence of run lengths of 0’s in D_{s,k} is

Z_{s} = \begin{cases}s · X̄_{s}, & if s ≥ 0; \\ X̄_{s}, & if s ≤ 0. \end{cases}

Proof. We again think of growing the tree by repeatedly grafting on a new level. We first explain (26) and then the expression for Z_{s}(n).

Consider a penultimate node x which is the leftmost child of its parent, and suppose that t internal nodes are between it and the previous leaf; i.e., it corresponds to the final 0 in a maximal run of t 0’s. After the graft x is replaced with an internal node and k internal nodes y_{1}, y_{2}, …, y_{k}. There are now t + 1 internal nodes between y_{1} and the previous leaf, and each of y_{2}, …, y_{k} have leaves following and preceding them; i.e., they correspond to runs consisting of a single 0. The previous discussion explains the occurrence of ρ(u) in (26). In the case where s ≥ 0, when we graft it is only the leftmost penultimate node that does not follow the pattern, but its parent and siblings do follow the pattern, and the length of their runs of 0’s are s + 1 followed by k − 2 1’s. In the case where s ≤ 0, when we graft the first (−s + 1)(k − 1) internal nodes do not follow the pattern since they are the only ones without internal nodes as parents. Clearly their corresponding run lengths are one.

In our discussion above, when s ≥ 0 we ignored the leftmost internal node. Clearly, it contributes a run of s 0’s. This accounts for the extra s in the expression for Z_{s}(n).

Corollary 18. The sequence of lengths of successive maximal runs of the form 10 ⋯ 0 in D_{s,k} is

Z_{s} = \begin{cases}X̄_{s}, & if s ≥ 0; \\ 1^{−s} · X̄_{s}, & if s ≤ 0. \end{cases}

Proof. This can be proven using the same sort of reasoning used in Theorem 17.

In the corollary below we state the relationship between X̄_{s}(n) and p_{s}(n).

Corollary 19. For n ≥ 1,

p_{s}(n) = \begin{cases}1 + ∑_{j=1}^{n−1} X̄_{s}(j), & if s ≥ 0 and n ≥ 1; \\ n, & if s ≤ 0 and n ≤ (−s + 1); \\ (−s + 1) + ∑_{j=1}^{n−(−s+1)} X̄_{s}(j), & if s ≤ 0 and n ≥ (−s + 1). \end{cases}

Proof. The key observation is that p_{s}(n) is one plus the sum the lengths of the first n − 1 maximal substrings of the form 10 ⋯ 0. Thus the result follows by an application of Corollary 18.

Lemma 20. For all k ≥ 2,

D_{0} = 1^{k}0^{r_{1}}1^{k}0^{r_{2}}1^{k}0^{r_{3}}1^{k}0^{r_{4}} ⋯  (28)
= 10^{r_{1}−1}10^{r_{2}−1}10^{r_{3}−1}10^{r_{4}−1} ⋯  (29)

Proof. Equation (29) is true by the observation made in the proof of Lemma 16. Since |R_{n}| = k^{n} − 1, we have r_{k^{n}+i} = r_{i} for 1 ≤ i ≤ k^{n+1} − k^{n} − 1 and r_{k^{n}} = n + 1. We will show that

E_{n} = 1^{k}0^{r_{1}}1^{k}0^{r_{2}} ⋯ 1^{k}0^{r_{k^{n−1}}},  (30)

which will finish the proof of (28) since D_{0} = E_{∞} by Lemma 5. Since we know for n = 0 that E_{1} = E_{0}^{k}0, we can proceed by induction and find

E_{n+1} = (E_{n})^{k}0
= 1^{k}0^{r_{1}}1^{k}0^{r_{2}} ⋯ 1^{k}0^{r_{k^{n−1}}}1^{k}0^{r_{1}}1^{k}0^{r_{2}} ⋯ 1^{k}0^{r_{k^{n−1}}}0
= 1^{k}0^{r_{1}}1^{k}0^{r_{2}} ⋯ 1^{k}0^{r_{k^{n−1}}}1^{k}0^{r_{k^{n−1}+1}}1^{k}0^{r_{k^{n−1}+2}} ⋯ 1^{k}0^{r_{k^{n}−1}}1^{k}0^{r_{k^{n−1}}}0
= 1^{k}0^{r_{1}}1^{k}0^{r_{2}} ⋯ 1^{k}0^{r_{k^{n−1}}}1^{k}0^{r_{k^{n−1}+1}}1^{k}0^{r_{k^{n−1}+2}} ⋯ 1^{k}0^{r_{k^{n}−1}}1^{k}0^{n+1}.

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 21. Let s_{j} = r_{j} + s[[j is a power of k]]}. Then for any s ≥ 0,

D_{s} = 10^{s_{1}−1}10^{s_{2}−1}10^{s_{3}−1}10^{s_{4}−1} ⋯  (31)

Proof. Equation (31) comes from the second equality (29) in Lemma 20, and the fact that a new super-node will be added after we have seen a complete left subtree, which will have k^{i} leaf nodes, for some integer i. Therefore, we need to add s 0’s after every k^{i}-th leaf node, for each integer i. This gives us

D_{s} = 10^{s}0^{r_{1}−1}10^{r_{2}−1} ⋯ 10^{s}0^{r_{k}−1}1 ⋯ 10^{s}0^{r_{k^{2}}−1} ⋯
= 10^{s+r_{1}−1}10^{r_{2}−1} ⋯ 10^{s+r_{k}−1}1 ⋯ 10^{s+r_{k^{2}}−1} ⋯
= 10^{s_{1}−1}10^{s_{2}−1}10^{s_{3}−1}10^{s_{4}−1}10^{s_{5}−1}10^{s_{6}−1}10^{s_{7}−1}10^{s_{8}−1}10^{s_{9}−1} ⋯

6.3 An exact expression for p_{s}(n) for s ≥ 0.

Since the p_{s,k}(n) numbers give the positions of the 1’s in D_{s} the following corollary is true. The s = 1 case of this corollary is implicit in Proposition 4.1 of [13]. They use the notation #S(N) for the number of occurrences of N in the infinite sequence a(1), a(2), . . .. Clearly, #S(N) = p_{1}(n + 1) − p_{1}(n).

Corollary 22. For all n ≥ 1 and s ≥ 0,

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

Let ϵ_{k}(q) denote the largest power of k that divides q (see [11], pg. 114). In [11] it is shown for k prime that

ϵ_{k}(n!) = ∑_{j≥1} ⌊\frac{n}{k^{j}} ⌋ ,  (32)

but it is easy to see that the expression is correct for any positive integer k. Let ν_{k}(n) denote the sum of the base k digits of n. The following result is due to Legendre [11, 16]. A different proof also appears in Boros and Moll [4], but the one below is particularly nice.

Lemma 23. Let n = (b_{0}b_{1} ⋯ b_{m})_{k}, so that ν_{k}(n) = ∑_{i=0}^{m} b_{i}. Then,

∑_{j≥0} ⌊\frac{n}{k^{j}} ⌋ = \frac{kn − ν_{k}(n)}{k − 1}.  (33)

Proof. Multiply the left-hand side of the equation by k − 1 and simplify:

(k − 1) ∑_{j≥0} ⌊\frac{n}{k^{j}} ⌋ = (k − 1) ∑_{j=0}^{m}(b_{0}b_{1} ⋯ b_{j})_{k}

= kn + ∑_{j=0}^{m−1}(b_{0}b_{1} ⋯ b_{j}0)_{k} − ∑_{j=0}^{m−1}(b_{0}b_{1} ⋯ b_{j}b_{j+1})_{k} − (b_{0})_{k}
= kn − (b_{0} + b_{1} + ⋯ + b_{m})
= kn − ν_{k}(n).

Lemma 24. For all n ≥ 1,

∑_{j=1}^{n} r_{j} = n + ϵ_{k}(n!).

Proof. This follows by the same sort of reasoning used in [11] in the case k = 2.

Theorem 25. For all n ≥ 1 and s ≥ 0,

p_{s}(n) = s⌈log_{k} n⌉ + n + ϵ_{k}((n − 1)!)
= s⌈log_{k} n⌉ + 1 + ∑_{j≥0} ⌊\frac{n − 1}{k^{j}}⌋

= s⌈log_{k} n⌉ + \frac{kn − ν_{k}(n−1) − 1}{k − 1}.

Proof. By summing the equation in Corollary 22 and applying Lemma 24 we obtain

p_{s}(n + 1) = 1 + ∑_{j=0}^{n} r_{j} + s ∑_{j=0}^{n} [[n is a power of k]]
= 1 + n + ϵ_{k}(n!) + s(1 + ⌊log_{k}(n)⌋).

Observing that 1 + ⌊log_{k}(n)⌋ = ⌈log_{k}(n + 1)⌉ and substituting n − 1 for n gives us the first equation of the theorem. The other equations follow from Lemma 23 and (32).

For s = 1, this result is closely related to Proposition 4.1 of [13]. In Proposition 4.1, Higham and Tanny consider the quantity max{m : a(m) = n}, call it M(n). Clearly, p_{1}(n) = 1 + M(n − 1).

6.4 An exact expression for p_{s}(n) for s ≤ 0.

It is also possible to derive an exact expression for p_{s}(n) for s < 0, but it is less elegant than the expression given in Theorem 25. However, is does rely on a nice decomposition of the sequence p_{s}(n). Decompose the k-ruler function as P_{1}P_{2}P_{3} ⋯ where |P_{i}| = k^{i−1}. For example, with k = 2,

\underbrace{1}_{P_{1}} \underbrace{21}_{P_{2}} \underbrace{3121}_{P_{3}} \underbrace{41213121}_{P_{4}} \underbrace{5121312141213121}_{P_{5}} · · · .

Lemma 26. For all s ≤ 0,

X̄_{s} = 1^{−s+1}P_{1}^{−s+1}P_{2}^{−s+1}P_{3}^{−s+1} · · · .  (34)

Proof. Note in (26) that only difference between the s = 0 cases and the s < 0 cases is the number of blocks of 1^{k−1} that are prepended to the string before ρ is applied. Since the s = 0 case gives the k-ruler function and each successive generation is k times as large as the previous, we get the type of interleaving stated in the lemma.

Theorem 27. Let m = ⌈log_{k}(1 + n/(−s + 1))⌉ and n′ = (n−s) mod k^{m−1}. Then, for n ≥ 1 and s < 0, we have

p_{s}(n + (−s + 1)) = sm + [m] ⌊\frac{n − s}{k^{m−1}}⌋ + \frac{kn′ + ν_{k}(n′)}{k − 1}.  (35)

Proof. We omit the details, but outline some of the basic ideas. We will show that p_{s}(n + (−s + 1)) = (−s + 1) + A + B + C, where the values of A, B, and C are given below.

A = (−s + 1)([m] − m), B = [m] (⌊\frac{n − s}{k^{m−1}}⌋ − (−s + 1)) ,

and C = m + \frac{kn′ − ν_{k}(n′)}{k − 1}.

First note that m is such that n (as an index) lies somewhere in R_{m}^{−s+1}. Then A accounts for the sum of all the integers in R_{0}^{−s+1}R_{1}^{−s+1} ⋯ R_{m−1}^{−s+1}. Within R_{m}^{−s+1}, the index n lies within the ⌊\frac{n−s}{k^{m−1}} ⌋-th R_{m}. Finally, within that R_{m} the additional sum to get to the index n is given by C.

The table below shows some of the quantities discussed in the proof above for the case where s = −2 and k = 2.

R_{1} R_{1}^{2} R_{1}^{3} R_{2} R_{2}^{2} R_{2}^{3}  R_{3}
A 0 0 0 3 3 3 3 3 3 12 12 12 12
B 0 1 2 0 0 3 3 6 6 0 0 0 0
C 1 1 1 2 3 2 3 2 3 3 4 6 7

Theorem 28. Asymptotically, given constants k ≥ 2 and integer s, for increasing n,

p_{s}(n) ∼ \frac{k}{k − 1}n and a_{s}(n) ∼ \frac{k − 1}{k}n.

Proof. We first consider the case where s ≥ 0. Since d is the sum of base k digits of n, we have d = O(log_{k} n). Thus by Theorem 25,

p_{s}(n) = s⌈log_{k} n⌉ + \frac{kn − d − 1}{k − 1} = \frac{kn}{k − 1} + O(log n) ∼ \frac{kn}{k − 1}.

Let n = km/(k − 1). Since a_{s} is a well-behaved function and a_{s}(p_{s}(m)) = m, we have a_{s}(km/(k − 1)) ∼ m. In other words a_{s}(n) ∼ (k − 1)n/k.

For the case where s < 0 we use (35). The three terms there for large n are O(log n) + (n + O(1))k/(k − 1) + O(1). Thus, p_{s}(n) ∼ nk/(k − 1), and as before we can conclude also that a_{s}(n) ∼ (k − 1)n/k.

6.5 Generating Functions

In this subsection we determine the generating function of X̄_{s}, which we denote X̄_{s}(z), and use it to determine the ordinary generating function of the p_{s} sequence.

Consider again (26). Observe that subtracting 1 from each element of (s + 1) · 1^{k−2} · ρ(u) results in an s in position 1, the sequence u in positions k, 2k, 3k, …, and 0’s elsewhere. Thus, for s ≥ 0 we get that X̄_{s}(z) satisfies the equation

X̄_{s}(z) = sz + \frac{z}{1 − z} + X̄_{s}(z^{k}),

which can be iterated to obtain

X̄_{s}(z) = ∑_{m≥0} (sz^{k^{m}} + \frac{z^{k^{m}}}{1 − z^{k^{m}}} ) .  (36)

For s ≤ 0, similar reasoning reveals that, with r′ = (−s)(k − 1),

X̄_{s}(z) = \frac{z}{1 − z} + z^{r′} X̄_{s}(z^{k}),

which can be iterated to obtain

X̄_{s}(z) = ∑_{m≥0} \frac{z^{r′(1+k+···+k^{m−1})+k^{m}}}{1 − z^{k^{m}}}
= ∑_{m≥0} \frac{z^{(−s+1)k^{m}+s}}{1 − z^{k^{m}}} .  (37)

Note that the two generating functions (36) and (37) coincide when s = 0. Theorem 29. For all s ≥ 0 and k ≥ 2,

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

For all s ≤ 0 and k ≥ 2,

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

Proof. Assume first that s ≥ 0. From Corollary 19 we obtain the first equality below.

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

Now assume that s ≤ 0. From Corollary 19 we obtain the first equality below. The second follows by simplifying the first two terms and using (37).

∑_{n≥0} p_{s}(n)z^{n} = (z + 2z^{2} + ⋯ + (−s+1)z^{−s+1}) + \frac{(−s+1)z^{−s+2}}{1 − z} + \frac{z^{−s+1}}{1 − z} X̄(z)
= \frac{z(1 − z^{−s+1})}{(1 − z)^{2}} + \frac{z^{−s+1}}{1 − z} ∑_{m≥0} \frac{z^{(−s+1)k^{m}+s}}{1 − z^{k^{m}}}
= \frac{z}{1 − z} (\frac{1 − z^{−s+1}}{1 − z} + ∑_{m≥0} \frac{z^{(−s+1)k^{m}}}{1 − z^{k^{m}}} ) ,

which is equal to the sum in the statement of the theorem (note that sum is over m ≥ 1).

6.6 Some comments on the difference p(n + 1) − p(n)

The sequence p(n + 1) − p(n) for s = −1 and k = 2 is 1, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, … and is describing in the OEIS entry \underline{A091090} as “in binary representation: number of editing steps (delete, insert, or substitute) to transform n into n + 1”. It is characterized by the recurrence relation a(2n) = 1, a(2n + 1) = a(n) + 1 with a(0) = a(1) = 1. I.e., if a number is even then it can be transformed into its successor by changing the final 0 to a 1; but if it is odd, then the final bit changes from 1 to 0, and the remaining bits need to change to their successor. The initial condition is very important, since it is only the change from 1 to 2 where the “insert” operation is used; i.e., in taking (1)_{2} to (10)_{2}. The delete operation need never be used. The ordinary generating function thus satisfies the recurrence relation

A(z) = \frac{z}{1 − z} + zA(z^{2}),

Iterating, we obtain

A(z) = ∑_{m≥0} \frac{z^{1+2+···+2^{m}}}{1 − z^{2^{m}}} = ∑_{m≥0} \frac{z^{2^{m+1}−1}}{1 − z^{2^{m}}} .

This later expression is attributed to Vladeta Jovovic (2004) in OEIS \underline{A091090}. The sequence itself was submitted by Reinhard Zumkeller in 2003. A comparison of A(z) with (38) reveals that A(z) is indeed (a shifted version of) the generating function of p(n + 1) − p(n), or that is exactly X̄_{−1}(z) (see (37)).

We can generalize this example as follows to larger values of k, but again with s = −1. In k-ary representation, transform n into n + 1 where the allowed editing steps are substitute, delete, and change (k − 1)_{k} to (10)_{k}. The recurrence relation becomes a(kn) = a(kn + 1) = ⋯ = a(kn + k − 2) = 1 and a(kn + k − 1) = a(n) + 1, with initial conditions a(0) = a(1) = ⋯ = a(k−1) = 1.

We do not know how to generalize to other values of s the “edit” interpretation; however, the recurrence relation can be generalized for X̄(n) as follows.

X̄(n) = \begin{cases}1, & if 1 ≤ n ≤ (−s + 1)(k − 1); \\ 1, & if n − (−s + 1)(k − 1) − 1 ≢ 0 (mod k); \\ 1 + X̄(1 + (n − (−s + 1)(k − 1) − 1)/k), & otherwise. \end{cases}

The proof follows from the definition of X̄(n) in (26).

7 Cloitre/Sloane Self-referential Sequence

In this section we consider the recurrence relation

b_{k}(n) = \begin{cases}k+1, & if n = 1; \\ 1 + b_{k}(n − 1), & if n ∈ \{b_{k}(1), …, b_{k}(n − 1)\}; \\ k+1 + b_{k}(n − 1), & if n ∉ \{b_{k}(1), …, b_{k}(n − 1)\}. \end{cases}  (39)

Note that (4) is obtained when k = 2.

Let C_{k} be the tree F_{0,k} after the bottom level is removed, but the remaining labels are left intact (the leftmost leaf is also made into an ordinary node). We identify nodes with their labels. Figure 11 shows C_{3} (compare with F_{0,3} in Figure 3). Let ϕ_{k} = ϕ_{k}(1), ϕ_{k}(2), ϕ_{k}(3), … be the sequence of labels of nodes of C_{k} when read off in preorder. Thus ϕ_{3} is the sequence that starts

4, 8, 12, 13, 17, 21, 25, 26, 30, 34, 38, 39, 40, 44, 48, 52, 53, 57, 61, …

Observe that ϕ_{3} appears to be the same as b_{3}; we prove this below for general k. It is interesting to note that the sequences p_{0,k}(n) and ϕ_{k}(n) partition the positive integers, since each positive integer occurs uniquely as the label of a node in F_{0,k}.

Lemma 30.

ϕ_{k}(n) = \begin{cases}k+1, & if k = 1; \\ 1 + ϕ_{k}(n − 1), & if ϕ_{k}(n) is a leftmost child in C_{k}; \\ k+1 + ϕ_{k}(n − 1), & if ϕ_{k}(n) is not a leftmost child in C_{k}. \end{cases}

Proof. Clearly ϕ_{k}(1) = k + 1.

Consider the node x labeled ϕ_{k}(n) in C_{k}. We consider two cases depending on whether x is the leftmost child of its parent, or not.

Since the tree is labeled in preorder, the predecessor of a leftmost child is its parent in F_{0,k}, namely ϕ_{k}(n − 1). Thus ϕ_{k}(n) = 1 + ϕ_{k}(n − 1).

The predecessor of a non-leftmost child in F_{0,k} is a leaf (this is a general property of trees labeled in preorder). The predecessor of a non-leftmost child in C_{k} is thus also a leaf. Hence if x is a non-leftmost child of its parent, then in F_{0,k} the k predecessors of ϕ_{k}(n) are the (bottom level) leaves ϕ_{k}(n) − k, …, ϕ_{k}(n) − 2, ϕ_{k}(n) − 1, from left to right. The predecessor of (the leftmost-child) ϕ_{k}(n) − k is the node ϕ_{k}(n) − k − 1, which is a leaf in C_{k}. In C_{k} the nodes ϕ_{k}(n) − 1, ϕ_{k}(n) − 2, …, ϕ_{k}(n) − k have been removed from F_{0,k}, and k + 1 + ϕ_{k}(n − 1) is a leaf; thus ϕ_{k}(n) = k + 1 + ϕ_{k}(n − 1).

We now show that (ϕ_{k}(n) − n)/k satisfies a meta-Fibonacci recurrence relation.

Theorem 31. For all n ≥ 1, b_{k}(n) = ϕ_{k}(n) = n + ka_{0,k}(n).

Proof. Define the infinite tree S_{k} obtained by taking F_{0,k} and labeling node n with ϕ_{k}(n). Another way of obtaining S_{k} is by shifting all the labels in the nodes in C_{k} one position earlier in preorder, maintaining the requirement that the super-nodes receive no labels. That is, the empty leaf gets the label k + 1 = ϕ(1), and in general ϕ_{k}(n) in C_{k} becomes ϕ_{k}(n + 1) in S_{k}. The tree S_{3} is shown in Figure 12. Observe that a node is not a leftmost child in C_{k} if and only if that node is a leaf in S_{k}. This is true because the preorder predecessor of a leftmost child is its parent, and the preorder predecessor of a non-leftmost child x is the rightmost leaf in the subtree rooted at the left sibling of x.

Now consider node n in F_{0,k}. In S_{k} the corresponding node is ϕ_{k}(n). By definition, the value n occurs in ϕ_{k} exactly when ϕ_{k}(n) is not a leaf in S_{k}.

Combining our two observations: A node ϕ_{k}(n) is not a leftmost child in C_{k} if and only if n does not occur in ϕ_{k}.

Figure 11: The tree C_{3}.

Figure 12: The tree S_{3}.

It follows, by Lemma 30, that

ϕ_{k}(n) = \begin{cases}k+1, & if n = 1; \\ 1 + ϕ_{k}(n − 1), & if n ∈ \{ϕ_{k}(1), …, ϕ_{k}(n − 1)\}; \\ k+1 + ϕ_{k}(n − 1), & if n ∉ \{ϕ_{k}(1), …, ϕ_{k}(n − 1)\}. \end{cases}  (40)

Since it satisfies the same recurrence relation, ϕ_{k}(n) is the same as the self-referential sequence b_{k}(n) defined in (39).

We know that d_{0,k}(n) = a_{0,k}(n) − a_{0,k}(n − 1) is 1 or 0 according to whether n is a leaf or not in F_{0,k}. Similarly ϕ_{k}(n) − ϕ_{k}(n − 1) is k or 1 according to whether n is a leaf or not in C_{k}. Thus

ϕ_{k}(n) = ϕ_{k}(n − 1) + 1 + k(a_{0,k}(n) − a_{0,k}(n − 1)).

Iterating, we obtain ϕ_{k}(n) = n + ka_{0,k}(n) as claimed.

8 More Recurrence Relations

In this section we develop recurrence relations for a_{s}(n) that are not nested. This shows that nesting is not crucial, but the resulting recurrence relations are not nearly as elegant.

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

a_{0,k}([h] + m) = k^{h−1} + a_{0,k}(m).

Proof. Since D_{0} = E_{h}E_{h} ⋯ = (E_{h−1})^{k}0(E_{h−1})^{k}0 ⋯ and |E_{h−1}| = [h], the equality d([h] + m) = d(m) holds for 1 ≤ m ≤ k^{h} − 1. The range for m comes from the fact that |(E_{h−1})^{k}| = [h] + (k − 1)[h] = [h] + k^{h} − 1. Since we defined d(0) = 0 the range can be extended to include m = 0. The number of 1’s in E_{h−1} is #_{1}(E_{h−1}) = k^{h−1}. Thus

a_{0,k}([h] + m) = ∑_{p=0}^{[h]} d(p) + ∑_{p=0}^{m} d([h] + p) = #_{1}(E_{h−1}) + ∑_{p=0}^{m} d(p) = k^{h−1} + a_{0,k}(m). (41)

Lemma 33. For s ≥ 0 and k ≥ 2,

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

Proof. The labels on the nodes in subforest h in F_{s,k} are exactly the values of n lying in the first range above. This is true because the number of ordinary nodes to the left of h can be found by adding the number of nodes in all of the subtrees. The first subtree is simply one node. The remaining subtrees are k-ary trees of height j = 1, 2, …, h−1. These k-ary trees each have 1 + k + ⋯ + k^{j−1} = [j] nodes. By the construction of F_{s,k}, we have k−1 of each subtree of height j (except, as previously mentioned, the extra tree of height 1). Summing the number of nodes in all of the subtrees gives us

1 + ∑_{j=1}^{h−1}(k − 1)[j] = 1 + ∑_{j=1}^{h−1}(k^{j} − 1) = −h + 2 + ∑_{j=1}^{h−1} k^{j} = [h] − h + 1.

The number of super-nodes is sh. Thus, the lowest label of a node in subforest h of our tree is [h] + (s−1)h + 1 + 1 = [h] + (s−1)h + 2 and the highest label is [h] + (s−1)h + 1 + (k−1)[h] = (s−1)h + 1 + k(1 + k + ⋯ + k^{h−1}) = [h+1] + (s−1)h.

Corollary 34. a_{1,k}(n) = a(n − ⌊log_{k}((n−1)(k−1) + 1)⌋)

Proof. If s = 1, the super-nodes of F_{1,k} are numbered [h] + 1. Hence node n is contained in subforest h = ⌊log_{k}((n−1)(k−1) + 1)⌋.

Taking s = 1 in Lemma 33 we obtain a_{1,k}(n) = a_{0,k}(n − h) in the range [h] + 2 ≤ n ≤ [h+1]. In that range h = ⌊log_{k}((n−1)(k−1) + 1)⌋. We need to check what happens when n is a super-node, in other words, when n = [h] + 1. By the Lemma 33 a_{1,k}([h] + 1) = k^{h−1}. In F_{0,k}, the node [h] + 1 − h is the rightmost node in subforest h−1, and thus a_{0,k}([h] + 1 − h) = k^{h−1}.

Theorem 35. If 1 ≤ n ≤ s+1, then a(n) = 1. If n = s+i and 2 ≤ i ≤ k then a(n) = i. If n > s+k, then there are four cases, listed below.

If [h] + (s−1)h − s + 2 ≤ n ≤ [h] + (s−1)h + 2, then

a(n) = k^{h−1}.

If 1 ≤ m ≤ [h−1], then

a([h] + (s−1)h + 2 + m) = k^{h−2} + a([h] + 1 + (s−1)h + m − [h−1] − s).

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

a([h] + [h−1] + (s−1)h + 2 + m) = k^{h−2} + a([h] + (s−1)h + 2 + m).

If 1 ≤ m ≤ (k−2)[h], then

a(2[h] + (s−1)h + 1 + m) = k^{h−1} + a([h] + (s−1)h + 1 + m).

Proof. Let the node n be in the subforest h or in the super-node, call it y, that is the parent of the subforest h. Let x_{1}, …, x_{k−1} be the k−1 children of y which are not the left-most child of y, and denote the k subtrees of some x_{i} to be T_{i,1}, T_{i,2}, …, T_{i,k}. We will establish the following recurrence relation.

a(n) = \begin{cases}k^{h−1}, & if n = x_{1} or n ∈ y; \\ k^{h−2} + a(n − [h−1] − s − 1), & if n ∈ T_{1,1}; \\ k^{h−2} + a(n − [h−1]), & if n ∈ T_{1,i} where i = 2, 3, …, k; \\ k^{h−1} + a(n − [h]); & otherwise. \end{cases}  (42)

Clearly, if n = x_{1} or n ∈ y, a(n) = k^{h−1}. Let T be the subtree whose root is the rightmost child of the leftmost child of y. In the second case above, we are relating the subtree T_{1,1} to T. In this case we skip over k^{h−2} leaves and [h−1] + s + 1 nodes. In the third case above, we are relating the remaining subtree of T_{1,i} to T_{1,i−1}. In this case we skip over k^{h−2} leaves and [h−1] nodes. The final case relates the subtree rooted at x_{i} to the subtree rooted at x_{i−1}. In this case we are skipping over k^{h−1} leaves and [h] nodes.

From the proof Lemma 33 we know that the labels in the super-node y are the labels in the range [h] + (s − 1)h − s + 2 to [h] + (s − 1)h + 1. Therefore, since x_{1} is the next node that is labeled, x_{1} = [h] + (s − 1)h + 2. Thus, the leftmost child of x_{1}, which is the root of T_{L}, is x_{1} + 1 = [h] + (s − 1)h + 3. The second child of x_{1} would be [h] + [h−1] + (s − 1)h + 3, and x_{2} would be 2[h] + (s − 1)h + 2. Thus, we know the range of values for each of the cases in (42), and we can see that the theorem statement is another way of writing (42).

It should be clear from Theorem 35 that there are f_{s,k}(n) and g_{s,k}(n) such that a(n) = f_{s,k}(n) + a(n − g_{s,k}(n)); such an expression for s = 1 is given in Corollary 34. However, there does not seem to be any nice way of expressing them in general. As an example of the challenges involved, one of the breaks in the cases above occurs when n = [h]+(s−1)(h−1)+1. This can be solved for h to yield

h = \frac{1}{(s−1)k′ ln k} ((k′(n−2+s)+1) ln k − (s−1)k′W (\frac{k^{(k′(n−2+s)+1)/((s−1)k′)} ln k}{(s − 1)k′} )) ,

where W is the Lambert W-function (solution of z = W (z)e^{W (z)}), and k′ = k − 1.

9 Conclusions and Open Problems

In this paper, we showed three combinatorial interpretations for the sequence a_{s,k}(n). The first two are based on our generation of the infinite ordered trees F_{s,k} and F′_{s+1,k}, and the third is based on integer compositions. We also proved several equations which relate the a_{s,k}(n) sequences to one another. We also provided generating functions for a_{s,k}(n), as well as the related sequences d_{s,k}(n) and p_{s,k}(n).

Listed below are a few open problems related to these sequences.

• If A(z) is the generating function of an increasing sequence a_{n}, is there any general way to determine the generating function B(z) of the 0,1 sequence where b_{m} = 1 if and only if there is some n for which a_{n} = m. Conversely, is there a general way to determine A(z) from B(z).

• It is interesting that ϕ_{3}(n) − 1 appears to be OEIS sequence \underline{A096346}, which is the complement of the sequence \underline{A004128}(n) = ∑_{j≥0}⌊n/3^{j}⌋, the 3-adic valuation of 3n!. We conjecture that this is true.

• Find a composition interpretation of a_{s,k} for s < 0.

• Are there any nice generalizations of the Cloitre-Sloane style self-referential recurrence relations that are related to a_{s,k} for s ≠ 0?

10 Acknowledgements

We wish to thank Brad Jackson and Steve Tanny for helpful comments related to this research, and Jeffrey Shallit for pointing us to [2]. Thanks also to Benoit Cloitre for helpful comments related to the material in Section 7. Carla Savage was instrumental in the development of the correspondence in Section 4.2. We wish to thank the referees of this paper for their careful reading, which lead to several improvements in the presentation. This research was supported in part by a Discovery Grant from NSERC.

References

[1] R. B. J. T. Allenby and R. C. Smith, Some sequences resembling Hofstadter’s, J. Korean Math. Soc. 40 (1003) 921–932.

[2] 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.

[3] B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter’s Q-sequence, J. Integer Sequences, 10 (2007), Article 07.7.1.

[4] G. Boros and V. Moll, Irresistible Integrals: Symbolics, Analysis and Experiments in the Evaluation of Integrals, Cambridge University Press, 2004.

[5] J. Callaghan, J. J. Chew III, and S. M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM J. Discrete Mathematics 18 (2005) 794–824.

[6] Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.

[7] B. Cloitre, N. J. A. Sloane, and M. J. Vandermast, Numerical analogues of Aronson’s sequence, J. Integer Sequences, 6 (2003), Article 03.2.2.

[8] B. Cloitre and N. J. A. Sloane, Personal communication, March 2007.

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

[10] C. Deugau and F. Ruskey, Complete k-ary trees and generalized meta-Fibonacci sequences, Fourth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, September 18-22, 2006, Institut Ilie Cartan, Nancy, France, Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings Series Volume AG (2006), 203–214.

[11] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, second edition, 1994.

[12] R. K. Guy, Unsolved Problems in Number Theory, Springer, New York, Third Edition, 2004.

[13] J. Higham and S. Tanny, More well-behaved meta-Fibonacci sequences, Cong. Numerantium, 98 (1993) 3–17.

[14] D. R. Hofstadter, Metamagical Themas, Basic Books, NY, 1985.

[15] B. Jackson and F. Ruskey, Meta-Fibonacci sequences, binary trees and extremal compact codes, Electronic J. Combin., 13 (2006), #R26.

[16] A. M. Legendre, Théorie des Nombres, Firmin Didot Frères, Paris, 1830.

[17] Jon Perry, Symmetric Ferrar Diagrams, website,

www.users.globalnet.co.uk/^{∼}perry/maths/symmetricferrars/symmetricferrars.htm,

accessed March 2005.

[18] K. Pinn, Order and chaos in Hofstadter’s Q(n) sequence, Complexity 4 (1999) 41–46.

[19] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/^{∼}njas/sequences/, accessed October 2008.

[20] R. Stephan, Divide-and-conquer generating functions, Part I: Elementary sequences,

    http://arxiv.org/abs/math/0307027, 2003.

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

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A10. Keywords: Meta-fibonacci sequence, ruler function, k-ary tree, morphism, nested recurrence relation, composition.

(Concerned with sequences \underline{A006949}, \underline{A045412}, \underline{A046699}, \underline{A053735}, \underline{A079559}, \underline{A091090}, \underline{A096346}, \underline{A101925}, \underline{A120501}, \underline{A120502}, \underline{A120503}, \underline{A120504}, \underline{A120505}, \underline{A120506}, \underline{A120507}, \underline{A120508}, \underline{A120509}, \underline{A120510}, \underline{A120511}, \underline{A120512}, \underline{A120513}, \underline{A120514}, \underline{A120515}, \underline{A120516}, \underline{A120517}, \underline{A120518}, \underline{A120519}, \underline{A120520}, \underline{A120521}, \underline{A120522}, \underline{A120523}, \underline{A120524}, \underline{A120525}, \underline{A120526}, \underline{A120527}, \underline{A120528}, \underline{A120529}, \underline{A120530}, \underline{A120531}, and \underline{A120532}.)

Received March 24 2009; revised version received May 1 2009. Published in Journal of Integer Sequences, May 12 2009.

Return to Journal of Integer Sequences home page.