\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}
\usepackage{mathtools}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Extending a Recent Result on \\
\vskip .1in
Hyper $m$-ary Partition Sequences
}
\vskip 1cm
\large
Timothy B. Flowers\\
Department of Mathematics\\
Indiana University of Pennsylvania\\
Indiana, PA 15705\\
USA\\
\href{mailto:flowers@iup.edu}{\tt flowers@iup.edu} \\
\ \\
Shannon R. Lockard\\
Department of Mathematics\\
Bridgewater State University\\
Bridgewater, MA 02324\\
USA\\
\href{mailto:Shannon.Lockard@bridgew.edu}{\tt Shannon.Lockard@bridgew.edu} \\
\end{center}
\vskip .2in
\begin{abstract}
A hyper $m$-ary partition of an integer $n$ is defined to be a partition of $n$ where each part is a power of $m$ and each distinct power of $m$ occurs at most $m$ times. Let $h_m(n)$ denote the number of hyper $m$-ary partitions of $n$ and consider the resulting sequence. We show that the hyper $m_1$-ary partition sequence is a subsequence of the hyper $m_2$-ary partition sequence, for $2 \leq m_1 < m_2$.
\end{abstract}
\section{Introduction}
In 2004, Courtright and Sellers \cite{m-ary} defined a hyper $m$-ary partition of an integer $n$ to be a partition of $n$ for which each part is a power of $m$ and each power of $m$ occurs at most $m$ times. They denote the number of hyper $m$-ary partitions of $n$ as $h_m(n)$ and showed that they satisfy the following recurrence relation:
\begin{eqnarray}
h_m(mq) &=& h_m(q) + h_m(q-1), \label{recur1} \\
h_m(mq+s) &=& h_m(q), \text{ for } 1 \le s \leq m-1. \label{recur2}
\end{eqnarray}
Several of these hyper $m$-ary partition sequences can be found in the On-line Encyclopedia of Integer Sequences \cite{OEIS}. In particular, $h_2$ is \seqnum{A002487}, $h_3$ is \seqnum{A054390}, $h_4$ is \seqnum{A277872}, and $h_5$ is \seqnum{A277873}.
The sequence $h_2$ \seqnum{A002487}, the hyperbinary partition sequence, is well known. It is commonly known as the Stern sequence based on Stern's work \cite{stern}. Northshield \cite{northshield} gives an extensive summary of the many uses and applications of \seqnum{A002487}. Calkin and Wilf \cite{recounting} also studied $h_2$, outlining a connection between this sequence and a sequence of fractions they defined and used to give an enumeration of the rationals. Since then, several authors have studied similar restricted binary and $m$-ary partition functions; see \cite{sohn, ours, reznick} for additional examples.
In this paper, we will be analyzing hyper $m$-ary partitions of $n$ while also considering the base $m$ representation of $n$. Thus, it will be convenient to have clear and distinct notation. In particular, for $m\geq 2$, let $(n_r,n_{r-1},\ldots,n_1,n_0)_m$ be the base $m$ representation of positive integer $n$ where $0 \leq n_i < m$, $n_r \neq 0$, and $n = \sum_{i=0}^{r} n_i m^i$. Also, for ${2 \leq m_1 < m_2}$ and $n = (n_r,n_{r-1}, \ldots,n_1,n_0)_{m_1}$, we define a change of base function, $F_{m_1,m_2}(n) = (n_r,n_{r-1}, \ldots,n_1,n_0)_{m_2}$.
Next, we write a hyper $m$-ary partition of $n$ as $[x_r,x_{r-1}, \ldots,x_1,x_0]_m$ where $0 \leq x_i \leq m$ and $n = \sum_{i=0}^{r} x_i m^i$. Here, we may allow any of the $x_i$ to be 0 so that each hyper $m$-ary partition of $n$ is the same length $r$ as the base $m$ representation of $n$. Furthermore, let $H_m(n)$ be the set of all distinct hyper $m$-ary partitions of $n$. Observe that $h_m(n)$ is the cardinality of this set.
Recently, the authors gave an identity relating $h_2$ to $h_3$ and then generalized this identity to show that $h_2$ is a subsequence of $h_m$ for any $m$ \cite{ours}. This result involved giving a bijection between $H_2(\ell)$ and $H_m(k)$, where $k = F_{2,m}(\ell)$. In this note, the authors will follow a similar process to show that $h_{m_1}$ is a subsequence of $h_{m_2}$, for $2 \leq m_1 < m_2$.
\section{A preliminary example}
Consider the integer $37 = (1,1,0,1)_3$ and use the change of base function to find the integer with the same digits in base 4. In particular, $F_{3,4}(37) = (1,1,0,1)_4 = 81$. Now consider the hyper $3$-ary partitions of 37 and the hyper $4$-ary partitions of 81.
\begin{minipage}{.45\textwidth}
\begin{eqnarray*}
37 &=& 1 \cdot 3^3 + 1 \cdot 3^2 + 1 \cdot 3^0 \\
&=& 1 \cdot 3^3 + 3\cdot 3^1 + 1 \cdot 3^0 \\
&=& 3 \cdot 3^2 + 3\cdot 3^1 + 1\cdot 3^0
\end{eqnarray*}
\end{minipage}
\hfill
\begin{minipage}{.45\textwidth}
\begin{eqnarray*}
81 &=& 1 \cdot 4^3 + 1 \cdot 4^2 + 1 \cdot 4^0 \\
&=& 1 \cdot 4^3 + 4\cdot 4^1 + 1 \cdot 4^0 \\
&=& 4 \cdot 4^2 + 4\cdot 4^1 + 1\cdot 4^0
\end{eqnarray*}
\end{minipage}
\\ \\
\noindent Adopting the notation for hyper $m$-ary partitions and the sets of these partitions, rewrite these partitions in the following way:
\begin{eqnarray*}
H_3(37) &=& \left\{\, [1,1,0,1]_3,\, [1,0,3,1]_3,\, [0,3,3,1]_3 \, \right\}; \\
H_4(81) &=& \left\{\, [1,1,0,1]_4,\, [1,0,4,1]_4,\, [0,4,4,1]_4 \, \right\}.
\end{eqnarray*}
Note that the number of hyper $3$-ary partitions of 37 is the same as the number of hyper $4$-ary partitions of 81. In other words,
$$h_3(37) = h_4\left(F_{3,4}(37)\right) = h_4(81) \, .$$
We also observe that the coefficients of the partitions are similar, indicating that there is a relationship between the partitions in each set. This relationship will be further explored in the next section.
\section{Bijections between hyper $m$-ary partitions and hyper $(m+1)$-ary partitions}
We now verify the result suggested by the example in the prior section by considering hyper $m$-ary partitions of an integer $\ell$ and the hyper $(m+1)$-ary partitions of $k = F_{m,m+1}(\ell)$.
\begin{lemma}\label{mtom+1_bijection}
For a positive integer $\ell$, let $k = F_{m,m+1}(\ell)$. Define $g_m: H_{m+1}(k) \rightarrow H_m(\ell) $ by mapping
$$[c_r, c_{r-1}, \ldots, c_2 ,c_1 ,c_0]_{m+1} \mapsto [b_r ,b_{r-1}, \cdots, b_2, b_1, b_0]_{m}$$
according to the following rules:
\begin{align*}
c_i = 0 &\longrightarrow b_i = 0 \\
c_i = 1 &\longrightarrow b_i = 1 \\
& \, \, \, \,\, \vdots \\
c_i = m-2 &\longrightarrow b_i = m-2 \\
c_i = m - 1 &\longrightarrow b_i = m -1 \\
c_i = m &\longrightarrow b_i = m - 1 \\
c_i = m + 1 &\longrightarrow b_i = m .
\end{align*}
Then $g_m$ is a bijection.
\end{lemma}
\begin{proof}
It is clear from the definition that $g_m$ is a function. So we first show that $g_m$ is one-to-one. Suppose $x = [x_r, x_{r-1}, \ldots x_2, x_1, x_0]_{m+1}$ and $y = [y_r, y_{r-1}, \ldots y_2, y_1, y_0]_{m+1}$ are two hyper $(m+1)$-ary partitions of $k$ such that $x \neq y$. Then there must be at least one digit that doesn't match. Let $J = \{ j_1, j_2, \dots, j_n \}$ be the set of indices such that $x_j \neq y_j$. Then we have two cases.
First suppose without loss of generality that there is an index $j$ such that $x_j \notin \{ m-1, m \}$. Then the $j^{th}$ digit of $g_m(x)$ will be different than the $j^{th}$ digit of $g_m(y)$. Thus $g_m(x) \neq g_m(y)$.
Now suppose that $x_j \in \{ m-1,m \}$ and $y_j \in \{ m-1,m \}$ for all $j \in J$. Let $J_1 = \{ j \in J: x_j = m-1 \}$ and $J_2 = \{ j \in J: x_j = m \}$. Note that $y_j = m$ for all $j \in J_1$ and $y_j = m-1$ for all $j \in J_2$. Also observe that
\begin{eqnarray*}
x &=& \sum_{j \notin J} x_j m^j + \sum_{j \in J_1} (m-1) m^j + \sum_{j \in J_2} m \cdot m^j \\
y &=& \sum_{j \notin J} y_j m^j + \sum_{j \in J_1} m \cdot m^j + \sum_{j \in J_2} (m-1) m^j.
\end{eqnarray*}
Since $x_j = y_j$ for all $j\notin J$,
\begin{eqnarray*}
x - y &=& \sum_{j \in J_1} (m-1-m) m^j + \sum_{j \in J_2} (m-m+1) m^j \\
&=& \sum_{j \in J_2} m^j - \sum_{j \in J_1} m^j.
\end{eqnarray*}
Observe that $x-y = 0$ since $x$ and $y$ are two different hyper $(m+1)$-ary partitions of the same number $k$, implying
\[
\sum_{j \in J_2} m^j - \sum_{j \in J_1} m^j = 0.
\]
However, since $J_1$ and $J_2$ are disjoint, this is impossible. Thus it must be the case that when $x \neq y$, one of $x_j$ or $y_j$ must be outside of $\{ m-1, m \}$ so that $g_m(x) \neq g_m(y)$ as seen above. Thus $g_m$ is one-to-one.
To show that $g_m$ is onto, consider $b = [b_r, b_{r-1}, \cdots, b_2, b_1, b_0]_m \in H_m(\ell)$. We then define ${c=[c_r, c_{r-1}, \cdots, c_2, c_1, c_0]_{m+1}}$ in the following way. If $b_i \in \{ 0,1,2,\dots,m-3,m-2 \}$, then set $c_i = b_i$ and if $b_i=m$, set $c_i=m+1$. Now suppose $b_i = m-1$. Let $v$ be the minimal index with $v* m_1 + 1$. To do this, we need the following lemma about hyper $m_2$-ary partitions of an integer $n$.
In the following proof, observe that multiplying a partition $[x_r, x_{r-1}, \cdots, x_2, x_1, x_0]_m$ by $m$ corresponds to shifting the coefficients to the left one place and adding an additional 0 as the last coefficient.
\begin{lemma}\label{which_digitsM}
Let $m_2 > m_1 + 1$. If the base $m_2$ representation of an integer $n$ contains only digits from the set $\{ 0,1,2,\ldots, m_1 -1 \}$, then there are no hyper $m_2$-ary partitions of $n$ which use any of the coefficients $m_1, m_1 + 1, \ldots, m_2 - 2$.
\end{lemma}
\begin{proof}
We will prove this by induction on $n$. Assume that for all $q m_1 + 1$. From the definition of $k$, we know the base $m_2$ representation of $k$ includes only digits less than or equal to $m_1 - 1$. So, we apply Lemma \ref{which_digitsM} to conclude that none of the hyper $m_2$-ary partitions in $H_{m_2}(k)$ have any coefficients between $m_1$ and $m_2 - 2$, inclusive. Thus, $\phi$ need only specify how to map coefficients from the set $\{0,1, \ldots, m_1 - 1, m_2 - 1, m_2 \}$.
Now, using the bijection $g_m$ given in Lemma \ref{mtom+1_bijection}, define a new function $G:H_{m_2}(k) \rightarrow H_{m_1}(\ell)$ as follows:
$$ G = g_{m_1} \circ g_{m_1 + 1} \circ g_{m_1 + 2} \circ \cdots \circ g_{m_2 - 2} \circ g_{m_2 - 1} \ .$$
It is clear from Lemma \ref{mtom+1_bijection} that when we apply $G$ to any $m_2$-ary partition coefficient which is less than or equal to $m_1 - 1$, the coefficient maps to itself. When we apply $G$ to a partition coefficient of $m_2 - 1$, we see that
$$ m_2 - 1 \xmapsto{g_{m_2 -1}} \, m_2 - 2 \xmapsto{g_{m_2 -2}} \, m_2 - 3 \xmapsto{g_{m_2 -3}} \, \cdots \, \xmapsto{g_{m_1}} m_1 - 1 \ .$$
Finally, when we apply $G$ to a partition coefficient of $m_2$, we see that
$$ m_2 \xmapsto{g_{m_2 -1}} \, m_2 - 1 \xmapsto{g_{m_2 -2}} \, m_2 - 2 \xmapsto{g_{m_2 -3}} \, \cdots \, \xmapsto{g_{m_1}}
m_1 \ .$$
Thus, $G = \phi$.
We have $\phi$ equal to a finite composition of bijective functions. Therefore, $\phi$ is a bijection.
\end{proof}
Lemma \ref{general_theorem} leads to the following identity between values of $h_{m_1}$ and $h_{m_2}$.
\begin{theorem}
Let $2 \leq m_1 < m_2$. For positive integer $\ell$, set $k = F_{m_1,m_2}(\ell)$. Then
\[
h_{m_2}(k) = h_{m_1}(\ell).
\]
\end{theorem}
\begin{proof}
The values $\ell$ and $k$ given here match Lemma \ref{general_theorem} and we know that $h_{m_1}(\ell) = | H_{m_1}(\ell) |$ and $h_{m_2}(k) = | H_{m_2}(k) |$. Lemma \ref{general_theorem} gives a bijection between these finite sets. Therefore, we conclude that the sets must have the same cardinality.
\end{proof}
As an immediate corollary, we now state a final result regarding the relationships between hyper $m$-ary partition sequences for different values of $m$.
\begin{corollary}
Let $2 \leq m_1 \leq m_2$. Then $h_{m_1}$ is a subsequence of $h_{m_2}$.
\end{corollary}
These theorems extend the results in \cite{ours}, ultimately showing that the subsequence identity holds for any hyper $m_1$-ary and hyper $m_2$-ary partition sequences.
\section{Acknowledgments}
The authors wish to thank the referee for insightful comments and suggestions. This feedback helped us clarify the notation and improved the overall quality of the paper.
\begin{thebibliography}{9}
\bibitem{recounting} N. Calkin and H. Wilf, Recounting the rationals,
{\it Amer. Math. Monthly} {\bf 107} (2000), 360--363.
\bibitem{m-ary} K. Courtright and J. Sellers, Arithmetic properties for
hyper $m$-ary partition functions, {\it Integers} {\bf 4} (2004), A6.
\bibitem{sohn} J. Eom, G. Jeong, and J. Sohn, Three different ways to
obtain the values of hyper $m$-ary partition functions, {\it Bull.
Korean Math. Soc.} {\bf 53} (2016), 1857--1868.
\bibitem{ours} T. B. Flowers and S. R. Lockard, Identifying an $m$-ary
partition identity through an $m$-ary tree, {\it Integers} {\bf 16}
(2016), A10.
\bibitem{northshield} S. Northshield, Stern's diatomic sequence
$0,1,1,2,1,3,2,3,1,4,\ldots$, {\it Amer. Math. Monthly} {\bf 117}
(2010), 581--598.
\bibitem{reznick} B. Reznick, Some binary partition functions, in B.
Berndt, ed., {\it Analytic Number Theory: Proceedings of a Conference
in Honor of Paul T. Bateman}, Birkh{\"a}user, 1990, pp.~451--477.
\bibitem{OEIS} N. J. A. Sloane, The On-Line Encyclopedia of Integer
Sequences. Published electronically at \url{http://oeis.org}, 2017.
\bibitem{stern} M. A. Stern, {\"U}ber eine zahlentheoretische Funktion,
{\it J. Reine Angew. Math.} {\bf 55} (1858), 193--220.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A17. \\
\noindent \emph{Keywords: } integer partition, hyper $m$-ary partition.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A002487},
\seqnum{A054390},
\seqnum{A277872}, and
\seqnum{A277873}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 30 2016;
revised versions received February 9 2017; June 13 2017; June 23 2017.
Published in {\it Journal of Integer Sequences}, July 1 2017.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
*