% Revision of Mar 19, 2009, for submission to JIS. % Revision of April 28, 2009, final version for JIS. \documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} % \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Example} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \def\I#1{{[\![#1]\!]}} % Iversonian \def\G#1{{G(\langle #1 ,1 \rangle)}} % G( < ... , 1 > ) % new commands \newcommand{\coord}[3]{{\left(#1,#2\right)}^{#3}} \newcommand{\subone}[1]{#1^\prime} \newcommand{\A}[1]{\left<#1\right>} % \newcommand{\G}[1]{G \left(#1\right)} \newcommand{\GA}[1]{\G{\A{#1}}} \newcommand{\p}[1]{(#1)} \newcommand{\T}[3]{{\mathcal{T}}_{#1,#2}({#3})} % \newcommand{\T}[3]{{\mathcal{T}}_{#1}^{#2}({#3})} \newcommand{\Aofn}[3]{a_{#1,#2}({#3})} % \newcommand{\aofn}[3]{a_{#1}^{#2}({#3})} \newcommand{\aofn}[3]{a({#3})} % \newcommand{\aofn}[3]{a_{#1}^{#2}({#3})} \newcommand{\an}[1]{a({#1})} \newcommand{\dofn}[3]{d_{#1,#2}({#3})} % \newcommand{\dofn}[3]{d_{#1}^{#2}({#3})} \newcommand{\dn}[1]{d({#1})} \newcommand{\pofn}[3]{p_{#1,#2}({#3})} % \newcommand{\pofn}[3]{p_{#1}^{#2}({#3})} \newcommand{\pn}[1]{p({#1})} \newcommand{\kh}[2]{\mathbf{[}{#2}\mathbf{]}} % \newcommand{\kh}[2]{[{#2}]_{#1}} \begin{document} % \maketitle \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf The Combinatorics of Certain $k$-ary \\ \vskip .1in Meta-Fibonacci Sequences } \vskip 1cm \large Frank Ruskey and Chris Deugau \\ University of Victoria \\ Victoria, BC V8W 3P6 \\ Canada \\ \href{mailto:ruskey@cs.uvic.ca}{\tt ruskey@cs.uvic.ca}\\ \href{mailto:chrisde@gmail.com}{\tt chrisde@gmail.com} \\ \end{center} \vskip .2in \begin{abstract} This paper is concerned with a family of $k$-ary meta-Fibonacci sequences described by the recurrence relation \[ a(n) = \sum_{i=1}^k a(n{-}i - (s{-}1) - a(n{-}i)), \] where $s$ may be any integer, positive or negative. If $s \ge 0$, then the initial conditions are $a(n) = 1$ for $1 \le n \le s+1$ and $a(n) = n-s$ for $s+1 < n \le s+k$. If $s \le 0$, then the initial conditions are $a(n) = n$ for $1 \le n \le 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 \ge 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) \sim n(k-1)/k$). We also show that these sequences are related to a ``self-describing" sequence of Cloitre and Sloane. \end{abstract} % \keywords{\textbf{Keywords:} Meta-fibonacci, ruler function, $k$-ary tree, morphism} % \today \section{Introduction} %\maketitle A \emph{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 \emph{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 \cite{Guy}(Problem E31), Pinn \cite{Pinn99}). The most famous of these sequences is most likely that of Hofstadter \cite{Hofstadter85}, 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 well-behaved 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 \ge 0$, Jackson and Ruskey \cite{JacksonRuskey} showed that the sequences with $x(n) = y(n)+1 = n-s$ for $s \ge 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 \cite{Tanny}. The case of $s=0$ was considered before by Conolly \cite{Conolly}. Prior to the paper \cite{JacksonRuskey}, 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 \cite{JacksonRuskey} was based on binary trees. This paper, among several other things, extends the results of \cite{JacksonRuskey} to $k$-ary trees and to negative values of $s$. We will refer to the sequences $(a(1),a(2),\ldots)$ that are solutions to the recurrence relation \begin{equation} a(n) = \sum_{i=1}^k a(\ n{-}i - (s{-}1) - a(n{-}i) \ ) \label{eq:a(n)} \end{equation} as \emph{$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 \emph{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 \cite{CCT}, building on the earlier work of Higham and Tanny \cite{HighamTanny}. It is known that $k$-ary meta-Fibonacci sequences are quite sensitive to their initial conditions. For example, consider Figures \ref{fig:init111} and \ref{fig:init123}. These both show sequences generated by (\ref{eq:a(n)}) for $s=0$, but with different initial conditions. In Figure \ref{fig:init111}, $a(1)=a(2)=a(3)=1$; in Figure \ref{fig:init123}, $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 \cite{CCT} for $n \ge 1$ (e.g., Figure 1.5, p.\ 797). The paper \cite{CCT} was mainly concerned with the recurrence relation (\ref{eq:a(n)}) when the initial conditions are all 1's. % we refer to this sequence as $T(n)$. Because of the very different behavior of the two sequences, we are unable to use any of the results of \cite{CCT}, nor do the results overlap in any significant way. \begin{figure}[t] \includegraphics[width=5.5in]{Initial111.eps} \caption{For $1 \le n \le 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$.} \label{fig:init111} \end{figure} \begin{figure} \includegraphics[width=5.5in]{Initial123.eps} \caption{For $1 \le n \le 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$.} \label{fig:init123} \end{figure} The initial conditions used in this paper for $a(n)$ when $s \ge 0$ are \begin{equation} a(n) = 1 \mbox{ for } 1 \le n \le s+1 \mbox{ and } a(n) = n-s \mbox{ for } s+1 < n \le s+k. \label{eq:initial} \end{equation} When $s \le 0$, the initial conditions are \begin{equation} a(n) = n \mbox{ for } 1 \le n \le k(-s+1). \label{eq:initialneg} \end{equation} We will show that, with the initial conditions (\ref{eq:initial}) and (\ref{eq:initialneg}), these sequences also occur in natural combinatorial settings, % that they satisfy a recurrence relation of the % form $a(n) = f_{s,k}(n) + a( n - g_{s,k}(n) )$, that they have a fairly elegant ordinary generating function, and determine their asymptotics. In particular, for any fixed $s$ and $k \ge 2$, we give three 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 \ref{fig:init111}, was proven in \cite{CCT} (Corollary 4.16 and Corollary 5.14), namely $T(n) \sim (k-1)n/k$. In Theorem \ref{thm:asymptotic} 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 \emph{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 \cite{CloitreSloaneVandermast} and Hofstadter \cite{Hofstadter85}. Recently, Cloitre and Sloane \cite{CloitreSloane} observed experimentally that the self-referential sequence (OEIS\footnote{The OEIS is Neil Sloane's online encyclopedia of integer sequences \cite{OEIS}.} \seqnum{A045412}) defined by \begin{equation} b(n) = \begin{cases} 3, & \mbox{ if } n = 1; \\ 1 + b( n-1 ), & \mbox{ if } n \in \{b(1),\ldots,b(n-1)\} ; \\ 3 + b( n-1 ), & \mbox{ if } n \not\in \{b(1),\ldots,b(n-1)\}; \\ \end{cases} \label{eq:recurCloitre} \end{equation} is related to a meta-Fibonacci recurrence relation, and asked for a proof. In Section \ref{section:cloitre}, we will provide a proof, based on our tree interpretation of meta-Fibonacci sequences, for a generalized version of (\ref{eq:recurCloitre}) where 3 is replaced by $k+1$. \subsection{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 \cite{ChrisFrank}. \begin{table}[h] \small{ \begin{tabular}{c|cccccccccccccccccccccccccccc} $n$&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19 \\ \hline % $X(n)$ & A002572& 1&1&1&2&3&5&9&16&28&50&89&159&285&510&914&1639&2938 \\ $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 \\ \hline $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 \\ \hline $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 \\ \hline \hline $\Aofn{-1}{3}{n}$ &1&2&3&4&5&6&6&7&8&9&9&10&11&12&12&13&14&15&15 \\ $\Aofn{0}{3}{n}$ & 1&2&3&3&4&5&6&6&7&8&9&9&9&10&11&12&12&13&14 \\ $\Aofn{1}{3}{n}$ & 1&1&2&3&3&3&4&5&6&6&7&8&9&9&9&9&10&11&12 \\ $\Aofn{2}{3}{n}$ & 1&1&1&2&3&3&3&3&4&5&6&6&7&8&9&9&9&9&9 \\ \hline $\dofn{-1}{3}{n}$ & 1&1&1&1&1&1&0&1&1&1&0&1&1&1&0&1&1&1&0 \\ $\dofn{0}{3}{n}$ & 1&1&1&0&1&1&1&0&1&1&1&0&0&1&1&1&0&1&1 \\ $\dofn{1}{3}{n}$ & 1&0&1&1&0&0&1&1&1&0&1&1&1&0&0&0&1&1&1 \\ $\dofn{2}{3}{n}$ & 1&0&0&1&1&0&0&0&1&1&1&0&1&1&1&0&0&0&0 \\ \hline $\pofn{-1}{3}{n}$ &1&2&3&4&5&6&8&9&10&12&13&14&16&17&18&20&21&22&25 \\ $\pofn{0}{3}{n}$ & 1&2&3&5&6&7&9&10&11&14&15&16&18&19&20&22&23&24&27 \\ $\pofn{1}{3}{n}$ & 1&3&4&7&8&9&11&12&13&17&18&19&21&22&23&25&26&27&30 \\ $\pofn{2}{3}{n}$ & 1&4&5&9&10&11&13&14&15&20&21&22&24&25&26&28&29&30&33 \\ \end{tabular} } \caption{The values of $\Aofn{s}{k}{n}$, $\dofn{s}{k}{n}$, and $\pofn{s}{k}{n}$ for $k = 2,3$, $s = -1,0,1,2$, and $1 \le n \le 19$.} \label{table:numbers} \end{table} % \newpage \section{Meta-Fibonacci Sequences and Complete $k$-ary Trees} \label{sec:main} \begin{figure} \includegraphics[width=5.5in]{3tree-F0.eps} \caption{The tree $\mathcal{F}_{0,3}$.} \label{fig:F0} \end{figure} \begin{figure} \includegraphics[width=5.5in]{3tree-F1.eps} \caption{The tree $\mathcal{F}_{1,3}$.} \label{fig:F1} \end{figure} \begin{figure} \includegraphics[width=5.5in]{3tree-F2.eps} \caption{The tree $\mathcal{F}_{2,3}$.} \label{fig:F2} \label{fig:F23} \end{figure} Figure \ref{fig:F0} shows part of an infinite ordered ternary tree $\mathcal{F}_{0,3}$. For all $k \ge 2$, a $k$-ary version of this tree, $\mathcal{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 \emph{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 $\mathcal{F}_{0,k}$ consists of a succession of complete $k$-ary trees of sizes \begin{equation} 1,\underbrace{1,1,\ldots,1}_{k-1} , \underbrace{1{+}k, \ldots, 1{+}k}_{k-1}, \ldots, \underbrace{1{+}k{+}\cdots{+}k^h, \ldots, 1{+}k{+}\cdots{+}k^h}_{k-1}, \ldots \label{eq:sizes} \end{equation} % We refer to the subtree with $2^h-1$ nodes as \emph{subtree $h$}, % except for the leftmost subtree, which is subtree 0. The nodes of these subtrees are labeled in preorder. In $\mathcal{F}_{0,k}$ there is a one-way infinite path of unlabeled nodes (drawn with rectangles in Figure \ref{fig:F0}), which we refer to as the \emph{delay path}. The nodes along the delay path are called \emph{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 \emph{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 $\mathcal{F}_{s,k}$ first for $s > 0$ and then for $s < 0$. For $s \ge 0$, the unlabeled structure of the tree is the same as for $\mathcal{F}_{0,k}$; it is mainly the labeling of the supernodes that changes. The trees $\mathcal{F}_{1,3}$ and $\mathcal{F}_{2,3}$ are shown in Figures \ref{fig:F1} and \ref{fig:F2}. 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 (\ref{eq:sizes}), with the leftmost super-node occurring to the left of the first brace. \begin{figure} \includegraphics[width=5.5in]{2tree-F-1.eps} \caption{The tree $\mathcal{F}_{-1,2}$.} \label{fig:neg1_2} \end{figure} \begin{figure} \includegraphics[width=5.5in]{2tree-F-2.eps} \caption{The tree $\mathcal{F}_{-2,2}$.} \label{fig:neg2_2} \end{figure} \begin{figure} \includegraphics[width=5.5in]{3tree-F-1.eps} \caption{The tree $\mathcal{F}_{-1,3}$.} \label{fig:neg1_3} \end{figure} We now generalize the trees for $s \le 0$ and $k \ge 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 $\ell > 0$, the leftmost $-s+1$ nodes at level $\ell$ are unlabeled, and all other nodes are labeled. We sometimes say that an unlabeled node is \emph{empty}. The trees $\mathcal{F}_{-1,2}$, $\mathcal{F}_{-2,2}$, and $\mathcal{F}_{-1,3}$, are shown in Figures \ref{fig:neg1_2}, \ref{fig:neg2_2}, and \ref{fig:neg1_3}, respectively. Denote by $\T{s}{k}{n}$ the tree induced from $\mathcal{F}_{s,k}$ by the nodes with labels $1,2,\ldots,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 $\Aofn{s}{k}{n}$ to be the number of nodes at the bottom level (i.e., level 0) in $\T{s}{k}{n}$. Also define $\dofn{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 $\pofn{s}{k}{n}$ to be the positions occupied by the 1's in the $\dofn{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 $\Aofn{s}{k}{0} = \dofn{s}{k}{0} = \pofn{s}{k}{0} = 0$. Table \ref{table:numbers} gives the values of $\Aofn{s}{k}{n}$, $\dofn{s}{k}{n}$, and $\pofn{s}{k}{n}$ for $k = 2,3$, $s = -1,0,1,2$ and $1 \le n \le 19$. The values of all of these table entries for $s \ge 0$, as well as values for $k=4$, are in the OEIS (as sequences \seqnum{A006949}, \seqnum{A046699}, \seqnum{A079559}, \seqnum{A101925}, and \seqnum{A120501}--\seqnum{A120532}). For fixed $s$ these numbers are related as follows, \begin{equation} \Aofn{s}{k}{n} = \sum_{j=0}^n \dofn{s}{k}{j} \ \ \mbox{ and } \ \ \pofn{s}{k}{n} = \min\{ j : \Aofn{s}{k}{j} = n \}. \label{eq:sumd} \end{equation} 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. % \section{Meta-Fibonacci Sequences and Complete $k$-Trees} \begin{lemma} Let $1 \le i \le k$. The quantity \[ \aofn{s}{k}{ n{-}i - (s{-}1) - \aofn{s}{k}{n{-}i} } \] is the number of leaves in $\T{s}{k}{n}$ that are the $i$-th child of their parent, if \begin{itemize} \item $s \ge 0$ and $n > s+k$, or \item $s \le 0$ and $n > k(-s+1)$. \end{itemize} \label{lemma:leaves} \end{lemma} \begin{proof} % We will prove this in detail for the case where $s \ge 0$; % the other case is very similar and most details are omitted. 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) = \aofn{s}{k}{n - (s {-} 1) - \aofn{s}{k}{n} }$. We will show that $f(i) = \overline{a}(n-i)$ for $1 \le i \le k$. % The condition $n > s+k$ guarantees that the tree has at least $k$ leaves. First, observe that if all the leaves at the last level are removed from the infinite tree $\mathcal{F}_{s,k}$, then the same unlabeled infinite tree structure remains. We now define a process, called \emph{chopping}, that takes $\T{s}{k}{n}$ and returns the tree $\mathsf{chop}(\T{s}{k}{n})$ obtained by removing all the $a(n)$ leaves at the last level, and then relabeling so that $\mathsf{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 \le 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$ \emph{labels}, although the number of \emph{nodes} that it contains will be different unless $s = 1$. By our discussion above, in $\mathsf{chop}(\T{s}{k}{n}) = \T{s}{k}{n'}$ \begin{itemize} \item the number of labels is $n' = n-(s-1)-a(n)$, and \item the number of nodes is $n-a(n)$. \end{itemize} % To restore the labeled structure the leftmost super-node is made % into an ordinary node; this is accomplished by subtracting by $s - 1$ from the % number of labels in the tree. % This process of removing level 0 (the leaves) and then relabeling is called \emph{chopping} the last level. % By the discussion above, the number of labels after chopping $\T{s}{k}{n}$ is % equal to $n - (s{-}1) - \aofn{s}{k}{n}$. % % Therefore, the number of nodes at the penultimate level of $\T{s}{k}{n}$ is % \begin{equation} % \overline{a}(n) = \aofn{s}{k}{n - (s{-}1) - \aofn{s}{k}{n}}. % \label{eq:penult1} % \end{equation} It therefore follows that at the penultimate level in $\T{s}{k}{n}$ \begin{itemize} \item the number of labels is $\overline{a}(n)+(s-1)$, and \item the number of nodes is $\overline{a}(n) = \aofn{s}{k}{n - (s {-} 1) - \aofn{s}{k}{n} }$. \end{itemize} 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) = \cdots = 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) = \cdots = \overline{a}(n-k) \] because none of the nodes $n-1, n-2, \ldots, 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 \le i \le 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) = \cdots = f(r) \;\;\; \text{ and } \;\;\; f(r{+}1) = \cdots = 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) = \cdots = \overline{a}(n-r)$ because nodes $n,\ldots,n-r+1$ are all leaves, and so their removal does not change the number of penultimate nodes. Also, $\overline{a}(n-r-1) = \cdots = \overline{a}(n-k)$, because node $n-r$ is at the penultimate level and nodes $n-r-1, \ldots, 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 \le i \le k$, which finishes the proof. % \medskip % We will make a few comments about the $s \le 0$ case. % In the chopping we need to add $-s+1$ labels, so that (\ref{eq:penult1}) still holds. % The rest of the proof is more-or-less identical, the main difference being that % we have to pay particular attention to the new initial conditions. % SAY MORE ABOUT THIS??? \end{proof} % THEOREM 2.1 \begin{theorem} If $(s \ge 0 \mbox{ and } n > s{+}k)$ or $(s \le 0 \mbox{ and } n > k(-s+1))$, then \begin{equation} \aofn{s}{k}{n} = \sum_{i=1}^k \aofn{s}{k}{n - i - (s {-} 1) - \aofn{s}{k}{n{-}i} }. \label{eq:ask} \end{equation} % If $1 \le n \le s$, then $\aofn{s}{k}{n} = 1$. If $s \ge 0$, then the base cases are $a(n) = 1$ for $1 \le n \le s+1$, and $a(n) = n-s$ for $s+1 < n \le s+k$. If $s \le 0$, then the base cases are $a(n) = n$ for $1 \le n \le k(-s+1)$. \label{thm:main} \end{theorem} \begin{proof} The base cases are easy to check. Equation (\ref{eq:ask}) follows immediately from Lemma \ref{lemma:leaves}, since every leaf is the $i$-th child of its parent for some unique $i$, where $1 \le i \le k$. \end{proof} % \newpage \section{Binary strings, morphisms, and $\mathcal{D}_{s,k}$} \label{section:morphism} Define $\mathcal{D}_{s,k}$ to be the infinite string $d_{s,k}(1) d_{s,k}(2) d_{s,k}(3) \cdots $. 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. \begin{lemma} For all $n \ge 0$, we have $0^n E_n = D_n\ 0^n$. \label{lemma:Inversion} \end{lemma} \begin{proof} Our proof is by induction on $n$. The statement is true if $n = 0$ since $D_0 = E_0 = 1$. % $n = 1$, $0 E_1^k = 0 ((E_0^k)^k 0) = 0 (1^k 0) = (0 1^k) 0 = D_1^k 0$. Assuming that it is true for $n$, for $n+1$ we have \begin{gather*} 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 = \cdots \\ \cdots = 0\ (D_n)^k\ 0^n\ 0 = D_{n+1} \ 0^{n+1}. \end{gather*} \end{proof} % added proof not in previous paper \begin{lemma} For $n \ge 0$ and $k \ge 2$, \begin{equation} D_0 (D_0)^{k-1} (D_1)^{k-1} \cdots (D_n)^{k-1} = (E_n)^{k-1} (E_{n-1})^{k-1} \cdots (E_1)^{k-1} (E_0)^{k-1} E_0. \label{eq:bigmess} \end{equation} \label{lemma:D0induct} \end{lemma} \begin{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 \begin{equation} (D_{n})^{k-1} =\ 0^{n}\ (E_{n})^{k-2}\ (E_{n-1})^{k-1}\ \cdots\ (E_1)^{k-1}\ (E_0)^{k-1} E_0 \label{eq:stringend} \end{equation} Equation (\ref{eq:stringend}) is true if $n = 0$. For $n+1$ we have \begin{eqnarray*} (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}\ \cdots\ (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}\ \cdots\ (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}\ \cdots\ (E_1)^{k-1}\ (E_0)^{k-1} E_0. \\ \end{eqnarray*} In a somewhat similar fashion we may also prove by induction on $n$ that \begin{equation} (E_n)^{k-1}\ (E_{n-1})^{k-1}\ \cdots (E_1)^{k-1}\ (E_0)^{k-1}\ E_0\ 0^{n+1} = E_{n+1}. \label{eq:stringst} \end{equation} Now back to the proof of the lemma. Assuming that it is true for $n$, then for $n + 1$, %To complete the proof of the lemma %We proceed by induction. We combine (\ref{eq:bigmess}) with (\ref{eq:stringend}) and get \begin{eqnarray*} \lefteqn{ D_0 (D_0)^{k-1} (D_1)^{k-1} \cdots (D_{n})^{k-1} (D_{n+1})^{k-1} } \\ &=& (E_{n})^{k-1} (E_{n-1})^{k-1} \cdots (E_1)^{k-1} (E_0)^k\ (D_{n+1})^{k-1} \\ &=& (E_{n})^{k-1} (E_{n-1})^{k-1} \cdots (E_1)^{k-1} (E_0)^k\ 0^{n+1}\ (E_{n+1})^{k-2} (E_{n})^{k-1} \cdots (E_1)^{k-1} (E_0)^{k-1} E_0 \\ &=& E_{n+1}\ (E_{n+1})^{k-2}(E_n)^{k-1} \cdots (E_1)^{k-1} (E_0)^{k-1} E_0 \\ &=& (E_{n+1})^{k-1}(E_n)^{k-1} \cdots (E_1)^{k-1} (E_0)^{k-1} E_0. \end{eqnarray*} The first equality follows from the inductive assumption; the second follows from (\ref{eq:stringend}); the third follows from (\ref{eq:stringst}). \end{proof} The following Theorem gives explicit expressions for $\mathcal{D}_s$ in terms of $D_n$. In a sense, it provides string representations of the tree structures $\mathcal{F}_{s,k}$ introduced earlier. % Lemma 2.2 \begin{theorem} For all $k \ge 2$ and $s \ge 0$, \begin{equation} \mathcal{D}_{s,k} = D_0 0^s (D_0)^{k-1} 0^s (D_1)^{k-1} 0^s (D_2)^{k-1} \cdots \label{eq:dks-1} \end{equation} If $s = 0$, then \begin{equation} \mathcal{D}_{0,k} = D_0 (D_0)^{k-1} (D_1)^{k-1} (D_2)^{k-1} (D_3)^{k-1} \cdots = E_\infty. \label{eq:D0} \end{equation} For all $k \ge 2$ and $s \le 0$, \begin{equation} \mathcal{D}_{s,k} = D_0^{-s+1} (D_0)^{r} (D_1)^{r} (D_2)^{r} (D_3)^{r} \cdots, \label{eq:Dnegs} \end{equation} where $r = (-s+1)(k-1)$. \label{lemma:Einfty} \end{theorem} \begin{proof} Equation (\ref{eq:dks-1}) comes from the definition of $\mathcal{F}_{s,k}$. The $0^s$ factors represent the placement of the super-nodes. The first equality in (\ref{eq:D0}) is implied by (\ref{eq:Dnegs}). The second equality in (\ref{eq:D0}) comes from Lemma \ref{lemma:D0induct}. Since $E_n$ is a prefix of $E_{n+1}$, the expression $E_\infty$ is well-defined. Hence $\mathcal{D}_{0,k} = E_\infty$. Define a node in $\mathcal{F}_{s,k}$ to be a \emph{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 $\ell > 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 $\ell$ before encountering any with roots at level $\ell+1$. Furthermore, each subtree with a root at level $\ell$ produces the sequence $D_\ell$. Thus overall, we get the sequence on the righthand side of the equality (\ref{eq:Dnegs}). \end{proof} \subsection{Using morphisms to describe $\mathcal{D}_s$} Let $\varepsilon$ denote the empty string. A \emph{morphism} is a function $f : \Sigma \rightarrow \Sigma^*$, where $\Sigma$ is an alphabet and $\Sigma^*$ is the set of all strings over that alphabet. The function $f$ is extended to a mapping over $\Sigma^*$ by application to each symbol of the string: if $a_1 a_2 \cdots a_n \in \Sigma^*$, then $f(a_1 a_2 \cdots a_n) = f(a_1)f(a_2) \cdots f(a_n)$. Also, $f(\varepsilon) = \varepsilon$. It is worth observing that $D_n$ is the $n$-th iterate of the morphism $0 \mapsto 0$ and $1 \mapsto 01^k$, with $D_0 = 1$; let us call this morphism $\sigma$. Similarly, $E_n$ is the $n$-th iterate of the morphism $0 \mapsto 0$ and $1 \mapsto 1^k 0$, with $E_0 = 1$; let us call this morphism $\tau$. Various properties of this morphism, particularly in the case where $k = 2$, are explored in Allouche, Betrema, and Shallit \cite{ABS}. Here's the induction proof of the crucial property, $E_n = \tau^n(1)$, of $\tau$. \[ E_{n+1} = (E_n)^k0 = (\tau^n(1))^k0 = \tau^n( 1^k0 ) = \tau^n( \tau( 1 )) = \tau^{n+1}(1). \] Note that $E_{n+1} = \tau( E_n )$. For a binary string $u$, define \begin{equation} \xi_{s,k}( u ) = \begin{cases} 0^{s} 1^{k-1}, \cdot \sigma(u) & \text{ if } s \ge 0; \\ 1^{(-s+1)(k-1)}, \cdot \sigma(u) & \text{ if } s \le 0. \end{cases} \label{eq:xi} \end{equation} As usual, the $k$ will be dropped from the subscript if no confusion can arise. Consider the calculation of $\xi_{-2,2}^4( \varepsilon )$ shown below. \begin{eqnarray*} \xi_{-2}^4( \varepsilon ) & = & \xi_{-2}^3( 111 \cdot \sigma(\varepsilon)\ ) \ = \ \xi_{-2}^3( 111\ ) \\ & = & \xi_{-2}^2( 111 \cdot \sigma( 111 )\ ) \ = \ \xi_{-2}^2( 111\ 011\ 011\ 011\ ) \\ & = & \xi_{-2}^1( 111\ 011011011\ 0011011\ 0011011\ 0011011\ ) \\ & = & 111\ 011011011\ 001101100110110011011\ \\ & & 000110110011011\ 000110110011011\ 000110110011011. \end{eqnarray*} This is a prefix of $\mathcal{D}_{-2,2}$, except for a missing 111 at the front. Below we show that this holds in general. \begin{theorem} For all $k \ge 2$ \begin{equation} \mathcal{D}_{s,k} = \begin{cases} 1, \cdot \xi_s^\infty( \varepsilon ) & \text{ if } s \ge 0; \\ 1^{-s+1} \cdot \xi_s^\infty( \varepsilon ), & \text{ if } s \le 0. \end{cases} \label{eq:Dxi} \end{equation} \label{thm:Dxi} \end{theorem} \begin{proof} For this proof we employ the tree interpretation of $\mathcal{D}_s$ in a new way. Imagine that instead of chopping the last level, we are instead \emph{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 $\sigma$; 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 \le 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 $1 0^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 $\sigma$ in (\ref{eq:xi}), and then tacking on the initial 1 as a final step in (\ref{eq:Dxi}). If $s \le 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 (\ref{eq:xi}) holds. Those initial $-s+1$ leaves are accounted for in (\ref{eq:Dxi}) by the $1^{-s+1}$. \end{proof} % =============================================================================================== \subsection{Generating functions for $\mathcal{D}_s$} Generally, if $S = s(1)s(2)s(3) \cdots $ is a string then we use $S(z)$ to denote the ordinary generating function $S(z) = \sum_{i \ge 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 $\mathcal{A}_s(z)$ and $\mathcal{D}_s(z)$ denote the ordinary generating functions of the $\Aofn{s}{k}{n}$ and $\dofn{s}{k}{n}$ sequences, respectively. Directly from the definitions we get the equation shown below: \[ \mathcal{A}_s(z) = \frac{\mathcal{D}_s(z)}{1 - z}. \] In the notation for the $q$-binomial coefficients \cite{qbinom}, we have $[_1^h]_k = 1+k+\cdots+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 $\mathcal{A}_s(z)$ is determined by $\mathcal{D}_s(z)$ and $\mathcal{D}_s(z)$ is easier to treat, we first concentrate our attention on $\mathcal{D}_s(z)$. If $S$ is a string, then $|S|$ denotes the number of characters in $S$. \begin{lemma} For $n \ge 0$, we have $|D_n| = |E_n| = \kh{k}{n + 1} = 1+k+\cdots+k^n$. \end{lemma} \begin{proof} From their definitions, it is obvious that $|D_n| = |E_n|$. We know that $D_{0} = 1$, so $|D_{0}| = 1 = \kh{k}{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 + \cdots + k^n) = [n+2]$. \end{proof} \begin{lemma} \begin{eqnarray*} D_n(z) &=& z^{n+1} (1 {+} z^{\kh{k}{1}} {+} z^{2 \kh{k}{1}} {+} \cdots {+} z^{(k-1) \kh{k}{1}}) \cdots (1 {+} z^{\kh{k}{n}} {+} \cdots {+} z^{(k-1) \kh{k}{n}}) \\ &=& z^{n+1} \prod^n_{i=1} \sum^{k-1}_{j=0} z^{j \kh{k}{i}} = z^{n+1} \prod^n_{i=1} \frac{1 - z^{k[i]}}{1 - z^{[i]}} \text{,} \end{eqnarray*} \begin{eqnarray*} E_n(z) &=& z (1 {+} z^{\kh{k}{1}} {+} z^{2 \kh{k}{1}} {+} \cdots {+} z^{(k-1) \kh{k}{1}}) \cdots (1 {+} z^{\kh{k}{n}} {+} \cdots {+} z^{(k-1) \kh{k}{n}}) \\ &=& z \prod^n_{i=1} \sum^{k-1}_{j=0} z^{j \kh{k}{i}} = z \prod^n_{i=1} \frac{1 - z^{k[i]}}{1 - z^{[i]}}. \end{eqnarray*} \label{lemma:genfuncs} \end{lemma} \begin{proof} From the recurrence relation $D_0 = 1$ and $D_{n+1} = 0(D_{n})^k$ we obtain $D_0(z) = z$ and \begin{eqnarray*} D_{n+1}(z) &=& z D_n(z) + z^{|0D_n|}D_n(z) + z^{|0(D_n)^2|}D_n(z) + \cdots + z^{|0(D_n)^{k-1}|}D_n(z) \\ &=& z D_n(z) + z^{\kh{k}{n+1}+1}D_n(z) + z^{2\kh{k}{n+1}+1}D_n(z) + \cdots + z^{(k-1)\kh{k}{n+1}+1} D_n(z) \\ &=& z (1 + z^{\kh{k}{n+1}} + z^{2 \kh{k}{n+1}} + \cdots + z^{(k-1) \kh{k}{n+1}}) D_n(z). \end{eqnarray*} Similarly, $E_0(z) = z$ and $E_{n+1}(z) = (1 + z^{\kh{k}{n+1}} + z^{2 \kh{k}{n+1}} + \cdots + z^{(k-1) \kh{k}{n+1}}) E_n(z)$. The results now follow by induction. \end{proof} Observe that Lemma \ref{lemma:genfuncs} 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 \ref{lemma:Inversion}. \begin{corollary} \[ \mathcal{D}_0(z) = z \prod_{i \ge 1} \sum^{k-1}_{j=0} z^{j \kh{k}{i}} = z \prod_{i \ge 1} \frac{1 - z^{k[i]}}{1 - z^{[i]}}. \] \label{col:D0z} \end{corollary} \begin{proof} Follows from Lemma \ref{lemma:genfuncs} and the equation $\mathcal{D}_0 = E_\infty$ from Lemma \ref{lemma:Einfty}. \end{proof} \begin{theorem} The generating function $\mathcal{D}_{s,k}(z)$, for $s \ge 0$, is equal to \begin{equation} z\left(1 + z^{s+k^0}\left( \frac{1 - z^{(k-1)[1]}}{1 - z^{[1]}} + z^{s + k^1}\frac{1 - z^{k[1]}}{1 - z^{[1]}} \left(\frac{1 - z^{(k-1)[2]}}{1 - z^{[2]}} + z^{s+k^2} \frac{1 - z^{k[2]}}{1 - z^{[2]}} \left(\frac{1 - z^{(k-1)[3]}}{1 - z^{[3]}} \cdots \right.\right.\right.\right. \end{equation} \end{theorem} \begin{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\cdots$ from Lemma \ref{lemma:dks} into its generating function. Since \[ |D_0 0^s(D_0)^{k-1}0^s \cdots (D_{n-1})^{k-1}0^s| = s + 1 + \sum_{i=0}^{n-1} ((k-1)[i+1] + s) = s + n(s - 1) + [n+1], \] we can write \begin{eqnarray} \mathcal{D}_s(z) \nonumber &=& z+\sum_{n \ge 0}z^{s + n(s-1) + [n{+}1]} D_n(z) (1 + z^{|D_n|} + \cdots + z^{(k{-}2) |D_n|}) \\ \label{eq:DsDn} &=& z + \sum_{n \ge 0} \sum_{i=1}^{k-1} z^{s + n(s-1) + i[n+1]} D_n(z) \\ \nonumber &=& z + \sum_{n \ge 0} \sum_{i=1}^{k-1} z^{s + n(s-1) + i[n+1] + 1} x_1 x_2 \cdots x_n, \end{eqnarray} where $x_i = z(1 + z^{[i]} + \cdots + z^{(k-1)[i]}) = z \kh{z^{\kh{k}{i}}}{k} $. Recall that $D_n(z) = z x_1 x_2 \cdots x_n$ and expand the summation to obtain \begin{eqnarray*} \mathcal{D}_s(z) &=& z + (z (z^{s+\kh{k}{1}} {+} \cdots {+} z^{s+(k-1)\kh{k}{1}})) + (zx_1 (z^{2s - 1 + \kh{k}{2}} {+} \cdots {+} z^{2s - 1 + (k-1)\kh{k}{2}})) + \cdots \\ &=& z(1 + (z^{s+\kh{k}{1}} {+} \cdots {+} z^{s+(k-1)\kh{k}{1}}) + (x_1 (z^{2s - 1 + \kh{k}{2}} {+} \cdots {+} z^{2s - 1 + (k-1)\kh{k}{2}})) + \cdots \\ &=& z(1 + z^{s+\kh{k}{1}}((1 {+} \cdots {+} z^{(k-2)\kh{k}{1}}) + (x_1 (z^{s - 1 + k\kh{k}{1}} {+} \cdots {+} z^{s - 1 + (k-2)\kh{k}{2} + k\kh{k}{1}})) + \cdots \\ &=& z(1 + z^{s+k^0}((1 {+} \cdots {+} z^{(k-2)\kh{k}{1}}) + z^{s - 1 + k\kh{k}{1}}x_1 ((1 {+} \cdots {+} z^{(k-2)\kh{k}{2}}) + \cdots \\ &=& z\left(1 + z^{s+k^0}\left( \frac{1 - z^{(k-1)[1]}}{1 - z^{[1]}} + z^{s + k^1}\frac{1 - z^{k[1]}}{1 - z^{[1]}} \left(\frac{1 - z^{(k-1)[2]}}{1 - z^{[2]}} + z^{s+k^2} \frac{1 - z^{k[2]}}{1 - z^{[2]}} \cdots \right.\right.\right. \end{eqnarray*} \end{proof} \begin{theorem} For all $s \ge 0$ and $k \ge 2$, \[ \mathcal{A}_{s,k}(z) = \begin{cases} \displaystyle{\frac{z}{1-z} \prod_{i \ge 1} \frac{1-z^{k[i]}}{1-z^{[i]}}}, & \text{ if } s = 0;\\ \displaystyle{z \frac{1 - z^s}{1-z} \sum_{n \ge 0} \prod_{i=1}^n z^{s} \frac{1 - z^{k[i]}}{1 - z^{[i]}}}; & \text{ if } s > 0. \end{cases} \] \label{thm:askgen} \end{theorem} \begin{proof} The case for $s=0$ is simply obtained by dividing $\mathcal{D}_0(z)$ from Corollary \ref{col:D0z} 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 \begin{eqnarray*} (1 - z) R(z) &=& z (1-z^s) \sum_{n \ge 0} \prod_{i=1}^n z^s \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ % &=& z \sum_{n \ge 0} \prod_{i=1}^n z^s \frac{1 - z^{k[i]}}{1 - z^{[i]}} - z^{s+1} \sum_{n \ge 0} \prod_{i=1}^n z^s \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ &=& z + z \sum_{n \ge 1} z^{sn} \prod_{i=1}^n \frac{1 - z^{k[i]}}{1 - z^{[i]}} - z^{s+1} \sum_{n \ge 0} \prod_{i=1}^n z^s \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ &=& z + z \sum_{n \ge 1} z^{sn} \prod_{i=1}^n \frac{1 - z^{k[i]}}{1 - z^{[i]}} - z^{s+1} \sum_{n \ge 1} \prod_{i=1}^{n-1} z^s \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ % &=& z + z \sum_{n \ge 1} z^{sn} \prod_{i=1}^n \frac{1 - z^{k[i]}}{1 - z^{[i]}} - z^{s+1} \sum_{n \ge 1} z^{s(n-1)} \prod_{i=1}^{n-1} \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ % &=& z + z \sum_{n \ge 1} z^{sn} \prod_{i=1}^n \frac{1 - z^{k[i]}}{1 - z^{[i]}} - z \sum_{n \ge 1} z^{sn} \prod_{i=1}^{n-1} \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ &=& z + z \sum_{n \ge 1} z^{sn} \left(\prod_{i=1}^n \frac{1 - z^{k[i]}}{1 - z^{[i]}} - \prod_{i=1}^{n-1} \frac{1 - z^{k[i]}}{1 - z^{[i]}}\right) \\ &=& z + z \sum_{n \ge 1} z^{sn} \left( \frac{1 - z^{n[i]}}{1 - z^{[i]}} - 1 \right) \left(\prod_{i=1}^{n-1} \frac{1 - z^{k[i]}}{1 - z^{[i]}}\right) \\ &=& z + \sum_{n \ge 1} z^{sn+1} \sum_{j=1}^{k-1} z^{j[n]} \prod_{i=1}^{n-1} \frac{1 - z^{k[i]}}{1 - z^{[i]}} \\ &=& z + \sum_{n \ge 0} z^{sn+s+1} \sum_{j=1}^{k-1} z^{j[n+1]} \prod_{i=1}^{n} \frac{1 - z^{k[i]}}{1 - z^{[i]}}, \\ \end{eqnarray*} 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 + \cdots + k^{h-1}$, and the final equality comes from substituting $n+1$ for $n$. The remaining equation after the last step is equal to $\mathcal{D}_{s}(z)$ by (\ref{eq:DsDn}), and therefore we have the generating function for $\mathcal{A}_{s}(z)$ as determined above. \end{proof} We have not managed to find a particularly nice form of $\mathcal{D}_s(z)$ for $s < 0$. However, it is possible to derive that, for $s < 0$, \[ \mathcal{D}_s(z)/z = \frac{1-z^{-s+1}}{1-z} + z^{-s+1} \sum_{n \ge 0} z^{r([1]+[2]+\cdots+[n])} \frac{1-z^{r[n+1]}}{1-z^{[n+1]}} \prod_{i=1}^n \frac{1-z^{k[i]}}{1-z^{[i]}}, \] by using (\ref{eq:Dnegs}), the expression for $D_n(z)$ in Lemma \ref{lemma:genfuncs}, and the fact that $|D_n| = [n+1]$. As before, $r = (-s+1)(k-1)$. It would be nice to simplify this generating function. %=================================================================================================================== \section{Compositions (and partitions) of an integer} \label{section:compositions} Jon Perry \cite{Perry} has observed experimentally that $a_{1,2}(n)$ counts the number of compositions of $n$ such that, for some $m$, \[ n_0 + n_1 + \cdots + n_m = n \ \ \mbox{ where } \ \ n_i \in \{1,2^i\} \mbox{ for } i=0,1,\ldots,m. \] He uses a notation similar to $\langle 1 \rangle+\langle 1,2 \rangle + \langle 1,4 \rangle+ \langle 1,8 \rangle + \cdots $ to denote the set of such compositions and notes that many other combinatorial objects are in one-to-one correspondence with similar composition rules \cite{Perry}. We call these rules \emph{specifications}. Jackson and Ruskey \cite{JacksonRuskey} showed that if $s > 0$, then $a_{s,2}(n)$ counted the number of compositions of $n$ with specification \[ \langle 1,2,\ldots,s \rangle + \langle s, 2 + s - 1 \rangle + \langle s, 4 + s - 1 \rangle + \langle s, 8 + s - 1 \rangle + \cdots. \] 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$. \begin{corollary} If $s = 0$, then the number of compositions of $n$ with specification \[ \mathbb{Z}^+ + \langle 0,[1],\ldots,(k-1)[1] \rangle + \langle 0,[2],\ldots,(k-1)[2] \rangle + \cdots \] is $\Aofn{0}{k}{n}$. For $s \ge 1$, the number of compositions of $n$ with specification \[ \langle 1,2,\ldots,s \rangle + \langle s,s+[1],\ldots,s+(k-1)[1] \rangle + \langle s,s+[2],\ldots,s+(k-1)[2] \rangle + \cdots \] is $\Aofn{s}{k}{n}$. \label{cor:compo} \end{corollary} \begin{proof} This is clear from the generating function of $\mathcal{A}_{s,k}(z)$ given in Theorem \ref{thm:askgen} by observing that $z(1 - z^s)/(1 - z) = (z + z^2 + \cdots + z^s)$. Substituting into our summation gives \[ (z {+} z^2 {+} \cdots {+} z^s)(1 + z^s(1 {+} z^{[1]} {+} \cdots {+} z^{k[1]}) + z^{s}(1 {+} \cdots {+} z^{k[1]})z^s(1 {+} \cdots {+} z^{k[2]}) + \cdots \] \end{proof} % As an example: $\Aofn{2}{4}{10} = 5 % = |\{ 1{+}2{+}7, 1{+}3{+}2{+}2{+}2, 1{+}5{+}2{+}2, 2{+}2{+}2{+}2{+}2, 2{+}4{+}2{+}2 \}|$. As an example, $\Aofn{2}{3}{20} = 10$, and the 10 corresponding compositions are given below: \\ \noindent $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 $\Aofn{2}{3}{n}$ counts both the number of bottom level nodes of the tree $\mathcal{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. \subsection{A result of Allouche, Betrema, and Shallit} The generating function for $\mathcal{D}_0(z)/z$ given in Corollary \ref{col:D0z} can be written as \[ \prod_{i \ge 1} \frac{1 - z^{k[i]}}{1 - z^{[i]}} = \prod_{i \ge 1} (1+z^{[i]}+z^{2[i]}+\cdots+z^{(k-1)[i]}). \] This is the generating function for the number of partitions of $n$ of the form \begin{equation} n = \varepsilon_1 [1] + \varepsilon_2 [2] + \varepsilon_3 [3] + \cdots, \label{eq:shallit} \end{equation} where $\varepsilon_i \in \{0,1,\ldots,k-1\}$. Since $(k-1)[1]+(k-1)[2]+\cdots+(k-1)[m] < [m+1]$, if there is a partition of the form (\ref{eq:shallit}), then it is unique (of course, we already know this since $\mathcal{D}_s$ is a 0-1 sequence). The values of $n$ expressible as in (\ref{eq:shallit}) are exactly the numbers of the form $p_0(m)-1$. This relation between partitions of the form (\ref{eq:shallit}) and the $\mathcal{D}_0$ sequence (as generated by the morphism $\rho$) was noted in \cite{ABS} for general $k$ and proven in the case $k=2$ (see the ``Remarque" on page 241). Suppose that $n$ can be written as (\ref{eq:shallit}). Then \begin{eqnarray*} (k-1)n & = & \sum_{i \ge 1} \varepsilon_i (k^i -1) \\ & = & \sum_{i \ge 1} \varepsilon_i k^i - \sum_{i \ge 1} \varepsilon_i \\ & = & m - \nu_k(m), \end{eqnarray*} where $m$ is the integer $\sum_{k \ge 1} \varepsilon_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 (\ref{eq:shallit}). \subsection{A one-to-one correspondence} \label{sec:Carla} This correspondence was discovered in collaboration with Carla Savage. In the tree $\mathcal{T}_{s,k}(n)$ a path from a leaf to the root can be considered as a $k$-ary number $m = (b_d \cdots b_1 b_0)_k$, so that \[ m = \sum_{j=0}^{d} b_j k^j, \] where $b_j \in \{0,1,\ldots,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 \cdots 00)_k$, and the right-most path to the $k$-ary representation of $n-1$. Define the mapping $\psi$ that takes this $k$-ary number and returns the composition \[ \psi(m) = \sum_{j=0}^d (s + b_j (1+k+\cdots+k^j)) = \sum_{j=0}^d (s + b_j [j]). \] If $s = 0$, then transforming $\psi(m)$ into a composition of $n$ is simple: \[ n = (n-\psi(m))+\psi(m). \] This composition has the required specification. Otherwise, assume that $s > 0$. We can now transform $\psi(m)$ into a composition of $n$ as follows: \begin{equation} n = (1+( (n-\psi(m)) \bmod{s} )) + \psi(m) + s \left\lfloor \frac{n-\psi(m)}{s} \right\rfloor ; \label{eq:corres} \end{equation} that is, take $\psi(m)$, add $\lfloor (n-\psi(m))/s \rfloor$ parts $s$, and an initial part $(1+( (n-\psi(m)) \bmod{s} ))$. Note that the resulting composition is of specification \begin{equation} \langle 1,2,\ldots,s \rangle + \langle s,s+[1],\ldots,s+(k-1)[1] \rangle + \langle s,s+[2],\ldots,s+(k-1)[2] \rangle + \cdots. \label{eq:specification} \end{equation} Below we continue the example that follows Corollary \ref{cor:compo}. \begin{tabular}{|c|c|c|l|} \hline $m$ & $(b_2b_1b_0)_3$ & $\psi(m)$ & $n = 20$ \\ \hline 0 & 000 & $2+2+2$ & $2{+}\mathbf{2{+}2{+}2}{+}2{+}2{+}2{+}2{+}2{+}2$ \\ 1 & 001 & $3+2+2$ & $1{+}\mathbf{3{+}2{+}2}{+}2{+}2{+}2{+}2{+}2{+}2$ \\ 2 & 002 & $4+2+2$ & $2{+}\mathbf{4{+}2{+}2}{+}2{+}2{+}2{+}2{+}2$ \\ 3 & 010 & $2+6+2$ & $2{+}\mathbf{2{+}6{+}2}{+}2{+}2{+}2{+}2$ \\ 4 & 011 & $3+6+2$ & $1{+}\mathbf{3{+}6{+}2}{+}2{+}2{+}2{+}2$ \\ 5 & 012 & $4+6+2$ & $2{+}\mathbf{4{+}6{+}2}{+}2{+}2{+}2$ \\ 6 & 020 & $2+10+2$ & $2{+}\mathbf{2{+}10{+}2}{+}2{+}2$ \\ 7 & 021 & $3+10+2$ & $1{+}\mathbf{3{+}10{+}2}{+}2{+}2$ \\ 8 & 022 & $4+10+2$ & $2{+}\mathbf{4{+}10{+}2}{+}2{+}2$ \\ 9 & 100 & $2+2+15$ & $1{+}\mathbf{2{+}2{+}15}$ \\ \hline \end{tabular} In order to prove that this is a one-to-one correspondence we need the following lemma. \begin{lemma} If $m$ corresponds to a root-to-leaf path in $\mathcal{T}_{s,k}(n)$ then $n > \psi(m)$. \label{lemma:npsi} \end{lemma} \begin{proof} Let $n'$ be the rightmost leaf in $\mathcal{T}_{s,k}(n)$; thus $n' \le 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 \cdots 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 + \cdots + k^j ) b_j. \] Thus the number of nodes to the left of the path is \[ d(s-1) + \sum_{j=0}^d (1 + k + \cdots + k^j ) b_j. \] Therefore, \[ n' = 1+s+d + d(s-1) + \sum_{j=0}^d (1 + k + \cdots + k^j ) b_j = 1 + \sum_{j=0}^d s + (1 + k + \cdots + k^j ) b_j. \] Thus $1 + \psi(m) = n' \le n$, which implies that $n > \psi(m)$. \end{proof} Lemma \ref{lemma:npsi} shows that (\ref{eq:corres}) 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+ \cdots + x_t$ of specification (\ref{eq:specification}) consider the sub-composition $x_0 + \cdots + x_d$ where $d+1$ is the height of $\mathcal{T}_{s,k}(n)$; that is, $d$ is the largest integer such that \[ n \le (s-1)d + (1+k+\cdots+k^d). \] For $i = 0,1,\ldots,d$ we have $x_i \in \{ s, s+[i+1], \ldots, 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 \cdots b_1 b_0)_k$, which will correspond to a leaf in $\mathcal{T}_{s,k}(n)$ if $n$ is large enough, which it will be, because of the way that $d$ was chosen. % =============================================================================================================== \section{A Postorder Labeling} In Section \ref{sec:main}, we described the labeling of the infinite ordered $k$-ary trees $\mathcal{F}_{s,k}$, and the relationship between these trees and the sequences $\Aofn{s}{k}{n}, \dofn{s}{k}{n},$ and $\pofn{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 $\mathcal{F}'_{s,k}$ to represent our postorder labeling. The tree $\mathcal{F}'_{s,k}$ has exactly the same shape as $\mathcal{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 \le 0$, the change is very simple; each subtree is labeled in postorder, not preorder. For $s \ge 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 \ref{fig:F1p} and \ref{fig:F2p} show the start of $\mathcal{F}'_{1,3}$ and $\mathcal{F}'_{2,3}$ respectively. \begin{figure}[t] \includegraphics{3tree-F1-p.eps} \caption{The tree $\mathcal{F}'_{1,3}$.} \label{fig:F1p} \end{figure} \begin{figure}[t] \includegraphics{3tree-F2-p.eps} \caption{The tree $\mathcal{F}'_{2,3}$.} \label{fig:F2p} \end{figure} Define $a'_{s,k}(n)$ to be the number of nodes at the bottom level of the tree $\mathcal{T}'_{s,k}(n)$, where $\mathcal{T}'_{s,k}(n)$ is the forest induced by the first $n$ labeled nodes of $\mathcal{F}'_{s,k}$. For example, referring to Figure \ref{fig:F1p}, 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, \ldots, \] which is equal to the sequence $a_{0,3}(n)$ (See Table \ref{table:numbers}). 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 $\mathcal{D}'_{s,k}$ be the infinite string $d'_{s,k}(1) d'_{s,k}(2) d'_{s,k}(3) \cdots $, where $d'_{s,k}(n)$ is $0$ if node $n$ in $\mathcal{F}'_{s,k}$ is an internal node, and is $1$ if node $n$ is a leaf node. \newpage \begin{theorem} For $s \ge 1$, \begin{eqnarray} \mathcal{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\cdots \nonumber \\ &=& D_0 0^{s-1} (D_0)^{k-1} 0^{s-1} (D_1)^{k-1} 0^{s-1} (D_2)^{k-1} \cdots \label{eq:Dppos} \end{eqnarray} For $s \le 0$, with $r' = (-s+1)(k-1)$ and $r = (-s+2)(k-1)$, \begin{eqnarray} \mathcal{D}'_{s,k} &=& (E_0)^{-s+1} (E_0)^{r'} (E_1)^{r'} (E_2)^{r'} (E_3)^{r'} \cdots \nonumber \\ &=& (D_0)^{-s+2} (D_0)^{r} (D_1)^{r} (D_2)^{r} (D_3)^{r} \cdots \label{eq:Dpneg} \end{eqnarray} \label{thm:aprime} \end{theorem} \begin{proof} % First, notice that the $E_n$ we defined above 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. We first deal with the case where $s \ge 1$ and then the case where $s \le 0$. Assume that $s \ge 1$. The first equality comes from the definition of $\mathcal{F}'_{s,k}$. First, notice that the $E_n$ we defined at the beginning of Section \ref{section:morphism} 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 \ref{fig:F1p}, 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 $\mathcal{F}'_{s,k}$. We now prove (\ref{eq:Dppos}). 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 \ref{lemma:Inversion}, we have \begin{eqnarray*} \lefteqn{ 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} \cdots } \\ &=& 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} \cdots \\ &=& 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} \cdots \\ &=& 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} \cdots \\ &=& 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} \cdots. \\ \end{eqnarray*} We now assume that $s \le 0$. The first equality follows from the definition of $\mathcal{F}'_{s,k}$. Note that by Lemma \ref{lemma:Inversion}, \begin{equation} (D_n)^k 0^{n+1} = 0^n (E_n)^k 0 = 0^n E_{n+1}. \label{eq:DtoE} \end{equation} We will use (\ref{eq:DtoE}) to prove by induction on $n$ that \[ (D_0)^{-s} (D_0)^{r} (D_1)^{r} (D_2)^{r} \cdots (D_n)^{r} 0^{n+1} = (E_0)^{-s+1} (E_0)^{r'} (E_1)^{r'} (E_2)^{r'} \cdots (E_n)^{r'} E_{n+1}. \] When $n = 0$ then it is easy to check that $D_0^{-s+2}D_0^r0 = 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 \begin{eqnarray*} & & (D_0)^{-s+2} (D_0)^{r} (D_1)^{r} (D_2)^{r} \cdots (D_n)^{r} (D_{n+1})^{r} 0^{n+2} \\ & = & (D_0)^{-s+2} (D_0)^{r} (D_1)^{r} (D_2)^{r} \cdots (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} \cdots (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'} \cdots (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'} \cdots (E_n)^{r'} (E_{n+1})^{r'} (E_{n+2}) \\ \end{eqnarray*} Thus it is true for $n+1$ and the proof is completed. \end{proof} \begin{corollary} Let $a'_{s,k}(n)$ be the number of nodes at the bottom level of the tree $\mathcal{T}'_{s,k}(n)$ and let $a_{s,k}(n)$ be the number of nodes at the bottom level of the tree $\mathcal{T}_{s,k}(n)$. Then, for all integers $s$, \[ a'_{s,k}(n) = a_{s-1,k}(n). \] \end{corollary} \begin{proof} This follows from the above theorem. Notice that the second equality is the same as the sequence for $\mathcal{D}_{s-1,k}$ given in Lemma \ref{lemma:dks}. 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. \end{proof} %====================================== Analysis of leaf labels ============================================== % \newpage \section{Analysis of labels on the leaves} The labels on the leaves of $\mathcal{T}_{s,k}$ are given by the sequences $p_{s,k}$ (some examples are given in Table \ref{table:numbers}). 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. \subsection{The ruler function and its generalizations} %------------------------------------------------------- Let $r_1, r_2, r_3, r_4, \cdots$ 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_\infty$ where $R_1 = 1^{k-1}$ and $R_{n+1} = (R_n, n + 1)^{k-1}, R_n$. \begin{lemma} The ordinary generating function, $R(z)$, of the generalized ruler function is \begin{equation} \sum_{j \ge 1} r_j z^j = \sum_{n \ge 0} \frac{z^{k^n}}{1 - z^{k^n}}. \label{eq:toproveruler} \end{equation} \label{lemma:ruler} \end{lemma} \begin{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, \ldots$ 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 \begin{equation} R(z) = \frac{z}{1 - z} + R(z^k). \label{eq:rulerGFrecur} \end{equation} Equation (\ref{eq:toproveruler}) is obtained by iterating (\ref{eq:rulerGFrecur}). \end{proof} For further generating functions of this type, see the paper of Stephan \cite{Stephan}. \subsection{A ``morphism" related to the run lengths of the 0's} %--------------------------------------------- We will now try to determine the sequence of integers, call it $\mathcal{Z}_s$, of the lengths of runs of 0's that occur in $\mathcal{D}_{s}$. This sequence will effectively provide another characterization of $\mathcal{D}_{s}$ since the lengths of the runs of 1's is $k$, except at the very beginning. We will employ Theorem \ref{thm:Dxi}. Let $\rho$ denote the ``morphism" that maps the integer $t$ to the sequence of $k$ integers $t+1,1,\ldots,1$, and let $\rho'$ map $t$ to the sequence of $k$ integers $1,\ldots,1,t+1$. Let $\bar\xi$ be the following mapping of strings of integers to strings of integers. \begin{equation} \bar\xi_s( u ) = \begin{cases} (s+1) \cdot 1^{k-2} \cdot \rho(u), & \text{ if } s \ge 0; \\ 1^{(-s+1)(k-1)} \cdot \rho(u), & \text{ if } s \le 0. \end{cases} \label{eq:barxi} \end{equation} The infinite sequence $\bar\xi_s^\infty( \varepsilon )$ is often used so we give it a name: $\bar{\mathcal{X}}_s := \bar\xi_s^\infty( \varepsilon )$. For example, \begin{equation} \bar{\mathcal{X}}_{-1,2} = 1 1 2 1 2 1 3 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 \cdots. \label{ea:Xn1p2} \end{equation} \begin{theorem} The sequence of run lengths of 0's in $\mathcal{D}_{s,k}$ is \[ \mathcal{Z}_s = \begin{cases} s \cdot \bar{\mathcal{X}}_s, & \text{ if } s \ge 0; \\ \bar{\mathcal{X}}_s, & \text{ if } s \le 0. \end{cases} \] \label{thm:runs0} \end{theorem} \begin{proof} We again think of growing the tree by repeatedly grafting on a new level. We first explain (\ref{eq:barxi}) and then the expression for $\mathcal{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, \ldots, y_k$. There are now $t+1$ internal nodes between $y_1$ and the previous leaf, and each of $y_2,\ldots,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 $\rho(u)$ in (\ref{eq:barxi}). In the case where $s \ge 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 \le 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 \ge 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 $\mathcal{Z}_s(n)$. \end{proof} \begin{corollary} The sequence of lengths of successive maximal runs of the form $10 \cdots 0$ in $\mathcal{D}_{s,k}$ is \[ \mathcal{Z}_s = \begin{cases} \bar{\mathcal{X}}_s, & \text{ if } s \ge 0; \\ 1^{-s} \cdot \bar{\mathcal{X}}_s, & \text{ if } s \le 0. \end{cases} \] \label{corr:runs100} \end{corollary} \begin{proof} This can be proven using the same sort of reasoning used in Theorem \ref{thm:runs0}. \end{proof} In the corollary below we state the relationship between $\bar{\mathcal{X}}_s(n)$ and $p_s(n)$. \begin{corollary} For $n \ge 1$, \[ p_s(n) = \begin{cases} % 1, & \text{ if } s \ge 0 \text{ and } n = 1; \\ 1 + \sum_{j=1}^{n-1} \bar{\mathcal{X}}_s(j), & \text{ if } s \ge 0 \mbox{ and } n \ge 1; \\ n, & \text{ if } s \le 0 \text{ and } n \le (-s+1); \\ (-s+1)+ \sum_{j=1}^{n-(-s+1)} \bar{\mathcal{X}}_s(j), & \text{ if } s \le 0 \mbox{ and } n \ge (-s+1). \end{cases} \] \label{coro:pxi} \end{corollary} \begin{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 \cdots 0$. Thus the result follows by an application of Corollary \ref{corr:runs100}. \end{proof} % Lemma 2.7 from old paper \begin{lemma} For all $k \ge 2$, \begin{eqnarray} \mathcal{D}_0 &=& 1^k 0^{r_1} 1^k 0^{r_2} 1^k 0^{r_3} 1^k 0^{r_4} \cdots \label{eq:d0kA} \\ &=& 1 0^{r_1-1} 1 0^{r_2-1} 1 0^{r_3-1} 1 0^{r_4-1} \cdots \label{eq:d0kB} \end{eqnarray} \label{lemma:d0k} \end{lemma} \begin{proof} Equation (\ref{eq:d0kB}) is true by the observation made in the proof of Lemma \ref{lemma:ruler}. Since $|R_{n}| = k^n - 1$, we have $r_{k^n+i} = r_i$ for $1 \le i \le k^{n+1} - k^n - 1$ and $r_{k^n} = n+1$. We will show that \begin{equation} E_n = 1^k 0^{r_1} 1^k 0^{r_2} \cdots 1^k 0^{r_{k^{n-1}}}, \end{equation} which will finish the proof of (\ref{eq:d0kA}) since $\mathcal{D}_0 = E_\infty$ by Lemma \ref{lemma:Einfty}. Since we know for $n=0$ that $E_{1} = E_{0}^k 0$, we can proceed by induction and find \begin{eqnarray*} E_{n+1} &=& (E_n)^{k} 0 \\ &=& 1^k0^{r_1}1^k0^{r_2}\cdots1^k0^{r_{k^{n-1}}} 1^k0^{r_1}1^k0^{r_2}\cdots1^k0^{r_{k^{n-1}}} 0 \\ &=& 1^k0^{r_1}1^k0^{r_2}\cdots1^k0^{r_{k^{n-1}}} 1^k0^{r_{k^{n-1}+1}}1^k0^{r_{k^{n-1}+2}}\cdots1^k0^{r_{k^n-1}}1^k0^{r_{k^{n-1}}}0 \\ &=& 1^k0^{r_1}1^k0^{r_2}\cdots1^k0^{r_{k^{n-1}}} 1^k0^{r_{k^{n-1}+1}}1^k0^{r_{k^{n-1}+2}}\cdots1^k0^{r_{k^n-1}}1^k0^{n+1}. \end{eqnarray*} \end{proof} We can extend some of the previous results about $\mathcal{D}_0$ to $\mathcal{D}_s$. For proposition $P$ the notation $\I{P}$ means $1$ if $P$ is true and $0$ if $P$ is false. \begin{lemma} Let $s_j = r_j + s \I{j \text{ is a power of } k} \}$. Then for any $s \ge 0$, \begin{equation} \mathcal{D}_s = 10^{s_1-1} 10^{s_2-1} 10^{s_3-1} 10^{s_4-1} \cdots \label{eq:dks-2} \end{equation} \label{lemma:dks} \end{lemma} \begin{proof} Equation (\ref{eq:dks-2}) comes from the second equality (\ref{eq:d0kB}) in Lemma \ref{lemma:d0k}, 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 \begin{eqnarray*} \mathcal{D}_s &=& 10^s0^{r_1-1}10^{r_2-1}\cdots10^s0^{r_k-1}1\cdots10^s0^{r_{k^2}-1} \cdots \\ &=& 10^{s+r_1-1}10^{r_2-1}\cdots10^{s+r_k-1}1 \cdots 10^{s+r_{k^2}-1} \cdots \\ &=& 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} \cdots \end{eqnarray*} \end{proof} \subsection{An exact expression for $p_s(n)$ for $s \ge 0$.} Since the $p_{s,k}(n)$ numbers give the positions of the 1's in $\mathcal{D}_s$ the following corollary is true. The $s = 1$ case of this corollary is implicit in Proposition 4.1 of \cite{HighamTanny}. They use the notation $\#\mathcal{S}(N)$ for the number of occurrences of $N$ in the infinite sequence $a(1),a(2),\ldots$. Clearly, $\#\mathcal{S}(N) = p_1(n+1) - p_1(n)$. \begin{corollary} For all $n \ge 1$ and $s \ge 0$, \[ p_s(n+1) - p_s(n) = r_n + s \I{n \mbox{ is a power of k}}. \] \label{corr:pdiff} \end{corollary} Let $\epsilon_k(q)$ denote the largest power of $k$ that divides $q$ (see \cite{GKP}, pg. 114). In \cite{GKP} it is shown for $k$ prime that \begin{equation} \epsilon_k( n! ) \ =\ \sum_{j \ge 1} \left\lfloor \frac{n}{k^j} \right\rfloor, \label{eq:epsilon} \end{equation} but it is easy to see that the expression is correct for any positive integer $k$. Let $\nu_k(n)$ denote the sum of the base $k$ digits of $n$. The following result is due to Legendre \cite{GKP,Legendre}. A different proof also appears in Boros and Moll \cite{Boros}, but the one below is particularly nice. \begin{lemma} Let $n = (b_0 b_1 \cdots b_m)_k$, so that $\nu_k(n) = \sum_{i=0}^m b_i$. Then, \begin{equation} \sum_{j \ge 0} \left\lfloor \frac{n}{k^j} \right\rfloor = \frac{kn - \nu_k(n)}{k -1}. \end{equation} \label{lem:connect} \end{lemma} \begin{proof} Multiply the left-hand side of the equation by $k-1$ and simplify: \begin{eqnarray*} (k-1) \sum_{j \ge 0} \left\lfloor \frac{n}{k^j} \right\rfloor & = & (k-1) \sum_{j=0}^m (b_0 b_1 \cdots b_j)_k \\ & = & kn + \sum_{j=0}^{m-1} (b_0 b_1 \cdots b_j 0)_k - \sum_{j=0}^{m-1} (b_0 b_1 \cdots b_j b_{j+1})_k - (b_0)_k \\ & = & kn - (b_0+b_1+ \cdots +b_m) \\ & = & kn - \nu_k(n). \end{eqnarray*} \end{proof} \begin{lemma} For all $n \ge 1$, \[ \sum_{j=1}^n r_j = n + \epsilon_k( n! ). \] \label{lemma:sumruler} \end{lemma} \begin{proof} This follows by the same sort of reasoning used in \cite{GKP} in the case $k = 2$. \end{proof} \begin{theorem} For all $n \ge 1$ and $s \ge 0$, \begin{eqnarray*} p_s(n) & = & s \lceil \log_k n \rceil + n + \epsilon_k( (n-1)! ) \\ & = & s \lceil \log_k n \rceil + 1 + \sum_{j \ge 0} \left\lfloor \frac{n-1}{k^j} \right\rfloor \\ & = & s \lceil \log_k n \rceil + \frac{kn-\nu_k(n{-}1)-1}{k-1}. \end{eqnarray*} \label{thm:ps(n)} \end{theorem} \begin{proof} By summing the equation in Corollary \ref{corr:pdiff} and applying Lemma \ref{lemma:sumruler} we obtain \begin{eqnarray*} p_s(n+1) &=& 1 + \sum_{j=0}^n r_j + s \sum_{j=0}^n \I{n \mbox{ is a power of }k} \\ &=& 1 + n + \epsilon_k( n! ) + s (1 + \lfloor \log_k(n) \rfloor). \end{eqnarray*} Observing that $1 + \lfloor \log_k(n) \rfloor = \lceil \log_k (n+1) \rceil$ and substituting $n-1$ for $n$ gives us the first equation of the theorem. The other equations follow from Lemma \ref{lem:connect} and (\ref{eq:epsilon}). \end{proof} For $s=1$, this result is closely related to Proposition 4.1 of \cite{HighamTanny}. 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)$. \subsection{An exact expression for $p_s(n)$ for $s \le 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 \ref{thm:ps(n)}. 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 \cdots$ 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} \ \cdots. \] \begin{lemma} For all $s \le 0$, \begin{equation} \bar{\mathcal{X}}_s = 1^{-s+1} P_1^{-s+1} P_2^{-s+1} P_3^{-s+1} \cdots. \label{eq:xiP} \end{equation} \end{lemma} \begin{proof} Note in (\ref{eq:barxi}) 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 $\rho$ 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. \end{proof} \begin{theorem} Let $m = \left\lceil \log_k (1+n/(-s+1)) \right\rceil$ and $n' = (n-s) \bmod{k^{m-1}}$. Then, for $n \ge 1$ and $s < 0$, we have \begin{equation} p_s(n+(-s+1)) = sm + [m] \left\lfloor \frac{n-s}{k^{m-1}} \right\rfloor + \frac{kn' + \nu_k(n')}{k-1}. \label{eq:ps_neg_exact} \end{equation} \end{theorem} \begin{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] \left( \left\lfloor \frac{n-s}{k^{m-1}} \right\rfloor -(-s+1) \right), \] \[ \mbox{and } \;\;\;\;\;\;\;\; C = m + \frac{kn' - \nu_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} \cdots R_{m-1}^{-s+1}$. Within $R_m^{-s+1}$, the index $n$ lies within the $\left\lfloor \frac{n-s}{k^{m-1}} \right\rfloor$-th $R_m$. Finally, within that $R_m$ the additional sum to get to the index $n$ is given by $C$. \end{proof} The table below shows some of the quantities discussed in the proof above for the case where $s = -2$ and $k = 2$. \begin{center} \begin{tabular}{|c|ccccccccccccc|} \hline & $R_1$ & $R_1^2$ & $R_1^3$ & \multicolumn{2}{c}{$R_2$} & \multicolumn{2}{c}{$R_2^2$} & \multicolumn{2}{c}{$R_2^3$} & \multicolumn{4}{c|}{$R_3$} \\ \hline $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 \\ \hline \end{tabular} \end{center} \begin{theorem} Asymptotically, given constants $k \ge 2$ and integer $s$, for increasing $n$, \begin{equation*} p_s(n) \sim \frac{k}{k-1} n \;\;\; \mbox{ and } \;\;\; a_s(n) \sim \frac{k-1}{k} n. \end{equation*} \label{thm:asymptotic} \end{theorem} \begin{proof} We first consider the case where $s \ge 0$. Since $d$ is the sum of base $k$ digits of $n$, we have $d = O( \log_k n )$. Thus by Theorem \ref{thm:ps(n)}, \[ p_s(n) = s \lceil \log_k n \rceil + \frac{kn-d-1}{k-1} = \frac{kn}{k-1} + O( \log n ) \sim \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) ) \sim m$. In other words $a_s( n ) \sim (k-1)n/k$. For the case where $s < 0$ we use (\ref{eq:ps_neg_exact}). The three terms there for large $n$ are $O(\log n) + (n+O(1))k/(k-1) + O(1)$. Thus, $p_s(n) \sim nk/(k-1)$, and as before we can conclude also that $a_s( n ) \sim (k-1)n/k$. \end{proof} \subsection{Generating Functions} In this subsection we determine the generating function of $\bar{\mathcal{X}}_s$, which we denote $\bar{\mathcal{X}}_s(z)$, and use it to determine the ordinary generating function of the $p_s$ sequence. Consider again (\ref{eq:barxi}). Observe that subtracting 1 from each element of $(s+1) \cdot 1^{k-2} \cdot \rho(u)$ results in an $s$ in position 1, the sequence $u$ in positions $k, 2k, 3k, \ldots$, and 0's elsewhere. Thus, for $s \ge 0$ we get that $\bar{\mathcal{X}}_s(z)$ satisfies the equation \[ \bar{\mathcal{X}}_s(z) = sz + \frac{z}{1-z} + \bar{\mathcal{X}}_s(z^k), \] which can be iterated to obtain \begin{equation} \bar{\mathcal{X}}_s(z) = \sum_{m \ge 0} \left( sz^{k^m} + \frac{z^{k^m}}{1-z^{k^m}} \right). \label{eq:Xzpos} \end{equation} For $s \le 0$, similar reasoning reveals that, with $r' = (-s)(k-1)$, \[ \bar{\mathcal{X}}_s(z) = \frac{z}{1-z} + z^{r'} \bar{\mathcal{X}}_s(z^k), \] which can be iterated to obtain \begin{eqnarray} \bar{\mathcal{X}}_s(z) & = & \sum_{m \ge 0} \frac{z^{r'(1+k+\cdots+k^{m-1})+k^m}}{1-z^{k^m}} \nonumber \\ & = & \sum_{m \ge 0} \frac{z^{(-s+1)k^m+s}}{1-z^{k^m}}. \label{eq:Xigf} \end{eqnarray} Note that the two generating functions (\ref{eq:Xzpos}) and (\ref{eq:Xigf}) coincide when $s=0$. \begin{theorem} For all $s \ge 0$ and $k \ge 2$, \[ \sum_{n \ge 0} p_s(n)z^n = \frac{z}{1-z}\left( 1 + \sum_{m \ge 0} z^{k^m} \left( s + \frac{1}{1 - z^{k^m}} \right) \right). \] For all $s \le 0$ and $k \ge 2$, \begin{equation} \sum_{n \ge 0} p_s(n)z^n = \frac{z}{1-z}\left( \frac{1}{1-z} + \sum_{m \ge 1} \frac{z^{(-s+1)k^{m}}}{1 - z^{k^m}} \right). \label{eq:gfpneg} \end{equation} \end{theorem} \begin{proof} Assume first that $s \ge 0$. From Corollary \ref{coro:pxi} we obtain the first equality below. \begin{eqnarray*} \sum_{n \ge 0} p_s(n)z^n & = & \frac{z}{1-z} + \frac{z}{1-z}\bar{\mathcal{X}}(z) \\ & = & \frac{z}{1-z} \left( 1 + \sum_{m \ge 0} \left( sz^{k^m} + \frac{z^{k^m}}{1-z^{k^m}} \right) \right). \end{eqnarray*} Now assume that $s \le 0$. From Corollary \ref{coro:pxi} we obtain the first equality below. The second follows by simplifying the first two terms and using (\ref{eq:Xigf}). \begin{eqnarray*} \sum_{n \ge 0} p_s(n)z^n & = & (z+2z^2+\cdots+(-s{+}1)z^{-s+1}) + \frac{(-s{+}1)z^{-s+2}}{1-z} + \frac{z^{-s+1}}{1-z}\bar{\mathcal{X}}(z) \\ & = & \frac{z(1-z^{-s+1})}{(1-z)^2} + \frac{z^{-s+1}}{1-z} \sum_{m \ge 0} \frac{z^{(-s+1)k^m+s}}{1-z^{k^m}} \\ & = & \frac{z}{1-z} \left( \frac{1-z^{-s+1}}{1-z} + \sum_{m \ge 0} \frac{z^{(-s+1)k^m}}{1-z^{k^m}} \right), \end{eqnarray*} which is equal to the sum in the statement of the theorem (note that sum is over $m \ge 1$). \end{proof} \subsection{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,\ldots \] and is describing in the OEIS entry \seqnum{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) = \sum_{m \ge 0} \frac{z^{1+2+\cdots+2^m}}{1-z^{2^m}} = \sum_{m \ge 0} \frac{z^{2^{m+1}-1}}{1-z^{2^m}}. \] This later expression is attributed to Vladeta Jovovic (2004) in OEIS \seqnum{A091090}. The sequence itself was submitted by Reinhard Zumkeller in 2003. A comparison of $A(z)$ with (\ref{eq:gfpneg}) reveals that $A(z)$ is indeed (a shifted version of) the generating function of $p(n+1)-p(n)$, or that is exactly $\bar{\mathcal{X}}_{-1}(z)$ (see (\ref{eq:Xigf})). 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) = \cdots = a(kn+k-2) = 1$ and $a(kn+k-1) = a(n)+1$, with initial conditions $a(0) = a(1) = \cdots = 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 $\bar{\mathcal{X}}(n)$ as follows. \[ \bar{\mathcal{X}}(n) = \begin{cases} 1, & \text{ if } 1 \le n \le (-s+1)(k-1); \\ 1, & \text{ if } n-(-s+1)(k-1)-1 \not\equiv 0 \ ({\rm mod}\ k); \\ 1 + \bar{\mathcal{X}}(1+(n-(-s+1)(k-1)-1)/k ), & \text{ otherwise.} \end{cases} \] The proof follows from the definition of $\bar{\mathcal{X}}(n)$ in (\ref{eq:barxi}). % \newpage \section{Cloitre/Sloane Self-referential Sequence} \label{section:cloitre} In this section we consider the recurrence relation \begin{equation} b_k(n) = \begin{cases} k{+}1, & \mbox{ if } n = 1; \\ 1 + b_k( n-1 ), & \mbox{ if } n \in \{b_k(1),\ldots,b_k(n-1)\} ; \\ k{+}1 + b_k( n-1 ), & \mbox{ if } n \not\in \{b_k(1),\ldots,b_k(n-1)\}. \\ \end{cases} \label{eq:recurCloitreK} \end{equation} Note that (\ref{eq:recurCloitre}) is obtained when $k = 2$. Let $\mathcal{C}_{k}$ be the tree $\mathcal{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 \ref{fig:treeC} shows $\mathcal{C}_3$ (compare with $\mathcal{F}_{0,3}$ in Figure \ref{fig:F0}). Let $\phi_k = \phi_k(1), \phi_k(2), \phi_k(3), \ldots$ be the sequence of labels of nodes of $\mathcal{C}_{k}$ when read off in preorder. Thus $\phi_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, \ldots \] Observe that $\phi_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 $\phi_k(n)$ partition the positive integers, since each positive integer occurs uniquely as the label of a node in $\mathcal{F}_{0,k}$. \begin{lemma} \[ \phi_k(n) = \begin{cases} k{+}1, & \mbox{ if } k = 1; \\ 1 + \phi_k( n-1 ), & \mbox{ if } \phi_k(n) \mbox{ is a leftmost child in } \mathcal{C}_{k}; \\ k{+}1 + \phi_k( n-1 ), & \mbox{ if } \phi_k(n) \mbox{ is not a leftmost child in } \mathcal{C}_{k}. \end{cases} \] \label{lemma:phiC} \end{lemma} \begin{proof} Clearly $\phi_k(1) = k+1$. Consider the node $x$ labeled $\phi_k(n)$ in $\mathcal{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 $\mathcal{F}_{0,k}$, namely $\phi_k(n-1)$. Thus $\phi_k(n) = 1 + \phi_k(n-1)$. The predecessor of a non-leftmost child in $\mathcal{F}_{0,k}$ is a leaf (this is a general property of trees labeled in preorder). The predecessor of a non-leftmost child in $\mathcal{C}_{k}$ is thus also a leaf. Hence if $x$ is a non-leftmost child of its parent, then in $\mathcal{F}_{0,k}$ the $k$ predecessors of $\phi_k(n)$ are the (bottom level) leaves $\phi_k(n)-k, \ldots, \phi_k(n)-2, \phi_k(n)-1$, from left to right. The predecessor of (the leftmost-child) $\phi_k(n)-k$ is the node $\phi_k(n)-k-1$, which is a leaf in $\mathcal{C}_{k}$. In $\mathcal{C}_{k}$ the nodes $\phi_k(n)-1, \phi_k(n)-2, \ldots, \phi_k(n)-k$ have been removed from $\mathcal{F}_{0,k}$, and $k+1 + \phi_k(n-1)$ is a leaf; thus $\phi_k(n) = k+1 + \phi_k(n-1)$. \end{proof} We now show that $(\phi_k(n) - n)/k$ satisfies a meta-Fibonacci recurrence relation. \begin{theorem} For all $n \ge 1$, $b_k(n) = \phi_k(n) = n + k a_{0,k}(n)$. \end{theorem} \begin{proof} Define the infinite tree $\mathcal{S}_k$ obtained by taking $\mathcal{F}_{0,k}$ and labeling node $n$ with $\phi_k(n)$. Another way of obtaining $\mathcal{S}_k$ is by shifting all the labels in the nodes in $\mathcal{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 = \phi(1)$, and in general $\phi_k(n)$ in $\mathcal{C}_k$ becomes $\phi_k(n+1)$ in $\mathcal{S}_k$. The tree $\mathcal{S}_3$ is shown in Figure \ref{fig:treeS}. Observe that a node is not a leftmost child in $\mathcal{C}_k$ if and only if that node is a leaf in $\mathcal{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$. % By definition, a number $j$ is not in $\phi$ if and only if $j$ is a leaf % in $\mathcal{F}_{0,k}$. Now consider node $n$ in $\mathcal{F}_{0,k}$. In $\mathcal{S}_k$ the corresponding node is $\phi_k(n)$. By definition, the value $n$ occurs in $\phi_k$ exactly when $\phi_k(n)$ is not a leaf in $\mathcal{S}_k$. Combining our two observations: A node $\phi_k(n)$ is not a leftmost child in $\mathcal{C}_k$ if and only if $n$ does not occur in $\phi_k$. It follows, by Lemma \ref{lemma:phiC}, that \begin{equation} \phi_k(n) = \begin{cases} k{+}1, & \mbox{ if } n = 1; \\ 1 + \phi_k( n-1 ), & \mbox{ if } n \in \{\phi_k(1),\ldots,\phi_k(n-1)\} ; \\ k{+}1 + \phi_k( n-1 ), & \mbox{ if } n \not\in \{\phi_k(1),\ldots,\phi_k(n-1)\}. \\ \end{cases} \label{eq:recurCloitrePhi} \end{equation} Since it satisfies the same recurrence relation, $\phi_k(n)$ is the same as the self-referential sequence $b_k(n)$ defined in (\ref{eq:recurCloitreK}). 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 $\mathcal{F}_{0,k}$. Similarly $\phi_k(n) - \phi_k(n-1)$ is $k$ or $1$ according to whether $n$ is a leaf or not in $\mathcal{C}_k$. Thus \[ \phi_k(n) = \phi_k(n-1) + 1 + k (a_{0,k}(n) - a_{0,k}(n-1)). \] Iterating, we obtain $\phi_k(n) = n + k a_{0,k}(n)$ as claimed. \end{proof} % \begin{figure} % \includegraphics[width=5in]{cloitre1.eps} % \caption{Figure 1 in the submitted manuscript.} % \label{fig:treeF} % \end{figure} \begin{figure} \includegraphics[width=5in]{3treeCloitreC.eps} \caption{The tree $\mathcal{C}_3$.} \label{fig:treeC} \end{figure} \begin{figure} \includegraphics[width=5in]{3treeCloitreS.eps} \caption{The tree $\mathcal{S}_3$.} \label{fig:treeS} \end{figure} % \newpage \section{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 2.3 \begin{corollary} The numbers $\Aofn{0}{k}{n}$ satisfy the following recurrence relation for $0 \le m < k^h$, \[ \Aofn{0}{k}{\kh{k}{h} + m} = k^{h-1} + \Aofn{0}{k}{m}. \] \end{corollary} \begin{proof} Since $\mathcal{D}_0 = E_h E_h \cdots = (E_{h-1})^k0 (E_{h-1})^k0 \cdots$ and $|E_{h-1}| = \kh{k}{h}$, the equality $d(\kh{k}{h} + m) = d(m)$ holds for $1 \le m \le k^h-1$. The range for $m$ comes from the fact that $|(E_{h-1})^k| = \kh{k}{h} + (k - 1) \kh{k}{h} = \kh{k}{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 \begin{equation} \Aofn{0}{k}{\kh{k}{h} + m} = \sum_{p=0}^{\kh{k}{h}} d(p) + \sum_{p=0}^m d(\kh{k}{h} + p) = \#_1(E_{h-1}) + \sum_{p=0}^m d(p) = k^{h-1} + \Aofn{0}{k}{m}. \end{equation} \end{proof} % Lemma 2.4 \begin{lemma} For $s \ge 0$ and $k \ge 2$, \[ \Aofn{s}{k}{n} = \begin{cases} \Aofn{0}{k}{n - sh}, & \text{ if } \kh{k}{h} + (s{-}1)h + 2 \le n \le \kh{k}{h{+}1} + (s{-}1)h; \\ k^{h-1}, & \text{ if } \kh{k}{h} + (s{-}1)h - s + 2 \le n \le \kh{k}{h} + (s{-}1)h + 1. \end{cases} \] \label{lemma:s0recurrence} \end{lemma} \begin{proof} The labels on the nodes in subforest $h$ in $\mathcal{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, \ldots, h{-}1$. These $k$-ary trees each have $1 + k + \cdots + k^{j-1} = \kh{k}{j}$ nodes. By the construction of $\mathcal{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 \begin{align*} 1 &+ \sum_{j=1}^{h-1} (k-1) \kh{k}{j} = 1 + \sum_{j=1}^{h-1} (k^j - 1) = -h + 2 + \sum_{j=1}^{h-1} k^j = \kh{k}{h} - h + 1. \end{align*} The number of super-nodes is $sh$. Thus, the lowest label of a node in subforest $h$ of our tree is $\kh{k}{h} + (s {-} 1)h + 1 + 1 = \kh{k}{h} + (s {-} 1)h + 2$ and the highest label is $\kh{k}{h} + (s {-} 1)h + 1 + (k{-}1)\kh{k}{h} = (s {-} 1)h + 1 + k(1 + k + \cdots + k^{h-1}) = \kh{k}{h{+}1} + (s{-}1)h$. \end{proof} % Corollary 2.5 \begin{corollary} $\Aofn{1}{k}{n} = \aofn{0}{k}{n - \lfloor \log_k ((n{-}1)(k{-}1) + 1) \rfloor}$ \label{corr:corr35} \end{corollary} \begin{proof} If $s = 1$, the super-nodes of $\mathcal{F}_{1,k}$ are numbered $\kh{k}{h} + 1$. Hence node $n$ is contained in subforest $h = \lfloor \log_k ((n{-}1)(k{-}1) + 1) \rfloor$. Taking $s = 1$ in Lemma \ref{lemma:s0recurrence} we obtain $\Aofn{1}{k}{n} = \Aofn{0}{k}{n - h}$ in the range $\kh{k}{h} + 2 \le n \le \kh{k}{h{+}1}$. In that range $h = \lfloor \log_k ((n{-}1)(k{-}1) + 1) \rfloor$. We need to check what happens when $n$ is a super-node, in other words, when $n = \kh{k}{h} + 1$. By the Lemma \ref{lemma:s0recurrence} $\Aofn{1}{k}{\kh{k}{h} + 1} = k^{h-1}$. In $\mathcal{F}_{0,k}$, the node $\kh{k}{h} + 1 - h$ is the rightmost node in subforest $h{-}1$, and thus $a_{0,k}(\kh{k}{h} + 1 - h) = k^{h-1}$. \end{proof} % Theorem 2.6 \begin{theorem} If $1 \le n \le s{+}1$, then $\aofn{s}{k}{n} = 1$. If $n = s{+}i$ and $2 \leq i \leq k$ then $\aofn{s}{k}{n} = i$. If $n > s{+}k$, then there are four cases, listed below. If $\kh{k}{h} + (s {-} 1)h - s + 2 \le n \le \kh{k}{h} + (s {-} 1)h + 2$, then \[ \aofn{s}{k}{n} = k^{h-1}. \] If $1 \le m \le \kh{k}{h{-}1}$, then \[ \aofn{s}{k}{\kh{k}{h} + (s{-}1)h + 2 + m} = k^{h-2} + \aofn{s}{k}{\kh{k}{h} + 1 + (s {-} 1)h + m - \kh{k}{h{-}1} - s}. \] If $1 \le m \le k^{h-1}-1$, then \[ \aofn{s}{k}{\kh{k}{h} + \kh{k}{h{-}1} + (s{-}1)h + 2 + m} = k^{h-2} + \aofn{s}{k}{\kh{k}{h} + (s{-}1)h + 2 + m}. \] If $1 \le m \le (k{-}2)\kh{k}{h}$, then \[ \aofn{s}{k}{2 \kh{k}{h} + (s{-}1)h + 1 + m} = k^{h-1} + \aofn{s}{k}{\kh{k}{h} + (s{-}1)h + 1 + m}. \] \label{thm:acases} \end{theorem} \begin{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, \ldots, 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}, \ldots, T_{i,k}$. We will establish the following recurrence relation. \begin{equation} \an{n} = \begin{cases} k^{h-1}, & \text{if } n = x_1 \text{ or } n \in y; \\ k^{h-2} + \an{n - [h{-}1] - s - 1}, & \text{if } n \in T_{1,1}; \\ k^{h-2} + \an{n - [h{-}1]}, & \text{if } n \in T_{1,i} \text{ where } i = 2, 3, \ldots, k; \\ k^{h-1} + \an{n - [h]}; & \text{otherwise}. \\ \end{cases} \label{eq:cases} \end{equation} Clearly, if $n = x_1$ or $n \in y$, $\an{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 \ref{lemma:s0recurrence} 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 (\ref{eq:cases}), and we can see that the theorem statement is another way of writing (\ref{eq:cases}). \end{proof} It should be clear from Theorem \ref{thm:acases} that there are $f_{s,k}(n)$ and $g_{s,k}(n)$ such that $\an{n} = f_{s,k}(n) + a( n - g_{s,k}(n) )$; such an expression for $s = 1$ is given in Corollary \ref{corr:corr35}. 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} \left( (k'(n{-}2{+}s){+}1) \ln k -(s{-}1)k' W \left( \frac{k^{(k'(n{-}2{+}s){+}1)/((s{-}1)k')} \ln k }{(s-1)k'} \right) \right), \] where $W$ is the Lambert W-function (solution of $z = W(z)e^{W(z)}$), and $k' = k - 1$. \section{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 $\mathcal{F}_{s,k}$ and $\mathcal{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. \begin{itemize} \item 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)$. \item It is interesting that $\phi_3(n)-1$ appears to be OEIS sequence \seqnum{A096346}, which is the complement of the sequence $\seqnum{A004128}(n) = \sum_{j \ge 0} \lfloor n/3^j \rfloor$, the 3-adic valuation of $3n!$. We conjecture that this is true. \item Find a composition interpretation of $a_{s,k}$ for $s < 0$. \item Are there any nice generalizations of the Cloitre-Sloane style self-referential recurrence relations that are related to $a_{s,k}$ for $s \neq 0$? \end{itemize} %\acknowledgements \section{Acknowledgements} \label{sec:ack} We wish to thank Brad Jackson and Steve Tanny for helpful comments related to this research, and Jeffrey Shallit for pointing us to \cite{ABS}. Thanks also to Benoit Cloitre for helpful comments related to the material in Section \ref{section:cloitre}. Carla Savage was instrumental in the development of the correspondence in Section \ref{sec:Carla}. 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. \nocite{*} \bibliographystyle{abbrvnat} \begin{thebibliography}{99} \bibitem{AllenbySmith} R. B. J. T. Allenby and R. C. Smith, Some sequences resembling Hofstadter's, {\it J. Korean Math. Soc.} \textbf{40} (1003) 921--932. \bibitem{ABS} J.-P. Allouche, J. Betrema, and J. O. Shallit, Sur des points fixes de morphismes d'un mono\"ide libre, {\it Informatique th\'eorique et Applications}, \textbf{23} (1989) 235--249. \bibitem{BKT} B. Balamohan, A. Kuznetsov, and S. Tanny, \hfil\\ \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.html}{On the behavior of a variant of Hofstadter's Q-sequence}, {\it J. Integer Sequences}, \textbf{10} (2007), Article 07.7.1. \bibitem{Boros} G. Boros and V. Moll, {\it Irresistible Integrals: Symbolics, Analysis and Experiments in the Evaluation of Integrals}, Cambridge University Press, 2004. \bibitem{CCT} J. Callaghan, J. J. Chew III, and S. M. Tanny, On the behavior of a family of meta-Fibonacci sequences, {\it SIAM J. Discrete Mathematics} \textbf{18} (2005) 794--824. \bibitem{qbinom} Peter J. Cameron, \emph{Combinatorics: Topics, Techniques, Algorithms}, Cambridge University Press, 1994. \bibitem{CloitreSloaneVandermast} B. Cloitre, N. J. A. Sloane, and M. J. Vandermast, \hfil \\ \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cloitre/cloitre2.html}{Numerical analogues of Aronson's sequence}, {\it J. Integer Sequences}, \textbf{6} (2003), Article 03.2.2. \bibitem{CloitreSloane} B. Cloitre and N. J. A. Sloane, Personal communication, March 2007. \bibitem{Conolly} B. W. Conolly, Meta-Fibonacci sequences, Chapter XII in S. Vajda, \emph{Fibonacci \& Lucas Numbers, and the Golden Section}, Ellis Horwood Limited, 1989. \bibitem{ChrisFrank} C. Deugau and F. Ruskey, Complete k-ary trees and generalized meta-Fibonacci sequences, {\it Fourth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities}, September 18-22, 2006, Institut Ilie Cartan, Nancy, France, {\it Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings Series Volume} \textbf{AG} (2006), 203--214. \bibitem{GKP} R. L. Graham, D. E. Knuth, and O. Patashnik, \emph{Concrete Mathematics}, Addison-Wesley, second edition, 1994. \bibitem{Guy} R. K. Guy, \emph{Unsolved Problems in Number Theory}, Springer, New York, Third Edition, 2004. \bibitem{HighamTanny} J. Higham and S. Tanny, More well-behaved meta-Fibonacci sequences, {\it Cong. Numerantium,} \textbf{98} (1993) 3--17. \bibitem{Hofstadter85} D. R. Hofstadter, \emph{Metamagical Themas}, Basic Books, NY, 1985. \bibitem{JacksonRuskey} B. Jackson and F. Ruskey, \href{http://www.combinatorics.org/Volume_13/Abstracts/v13i1r26.html}{Meta-Fibonacci sequences, binary trees and extremal compact codes}, {\it Electronic J. Combin.}, \textbf{13} (2006), \#R26. \bibitem{Legendre} A. M. Legendre, \emph{Th\'eorie des Nombres}, Firmin Didot Fr\`eres, Paris, 1830. \bibitem{Perry} Jon Perry, \emph{Symmetric Ferrar Diagrams}, website, \hfil\\ \url{www.users.globalnet.co.uk/~perry/maths/symmetricferrars/symmetricferrars.htm}, accessed March 2005. \bibitem{Pinn99} K. Pinn, Order and chaos in Hofstadter's $Q(n)$ sequence, {\it Complexity} \textbf{4} (1999) 41--46. \bibitem{OEIS} N. J. A. Sloane, \emph{The On-Line Encyclopedia of Integer Sequences}, \hfil\\ \url{http://www.research.att.com/~njas/sequences/}, accessed October 2008. \bibitem{Stephan} R. Stephan, Divide-and-conquer generating functions, Part I: Elementary sequences, \href{http://arxiv.org/abs/math/0307027}{\tt http://arxiv.org/abs/math/0307027}, 2003. \bibitem{Tanny} S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, {\it Discrete Math.}, \textbf{105} (1992) 227--239. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A10. \noindent \emph{Keywords:} Meta-fibonacci sequence, ruler function, $k$-ary tree, morphism, nested recurrence relation, composition. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A006949}, \seqnum{A045412}, \seqnum{A046699}, \seqnum{A053735}, \seqnum{A079559}, \seqnum{A091090}, \seqnum{A096346}, \seqnum{A101925}, \seqnum{A120501}, \seqnum{A120502}, \seqnum{A120503}, \seqnum{A120504}, \seqnum{A120505}, \seqnum{A120506}, \seqnum{A120507}, \seqnum{A120508}, \seqnum{A120509}, \seqnum{A120510}, \seqnum{A120511}, \seqnum{A120512}, \seqnum{A120513}, \seqnum{A120514}, \seqnum{A120515}, \seqnum{A120516}, \seqnum{A120517}, \seqnum{A120518}, \seqnum{A120519}, \seqnum{A120520}, \seqnum{A120521}, \seqnum{A120522}, \seqnum{A120523}, \seqnum{A120524}, \seqnum{A120525}, \seqnum{A120526}, \seqnum{A120527}, \seqnum{A120528}, \seqnum{A120529}, \seqnum{A120530}, \seqnum{A120531}, and \seqnum{A120532}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 24 2009; revised version received May 1 2009. Published in {\it Journal of Integer Sequences}, May 12 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}