\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}

\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{mathrsfs}
\usepackage{epic}
\usepackage{curves}
\usepackage{amsthm}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Minimal $r$-Complete Partitions}
\vskip 1cm
\large
\O ystein J. R\o dseth\\
Department of Mathematics\\
University of Bergen\\
Johs. Brunsgt. 12\\
N-5008 Bergen\\
Norway\\
\href{mailto:rodseth@math.uib.no}{\tt rodseth@math.uib.no}\\

\end{center}

\vskip .2 in

\begin{abstract}
A minimal $r$-complete partition of an integer $m$ is a partition of
$m$ with as few parts as possible, such that all the numbers
$1,\dots,rm$ can be written as a sum of parts taken from the
partition, each part being used at most $r$ times. This is a
generalization of M-partitions (minimal 1-complete partitions). The
number of M-partitions of $m$ was recently connected to the binary
partition function and two related arithmetic functions. In this
paper we study the case $r\geq2$, and connect the number of minimal
$r$-complete partitions to the $(r+1)$-ary partition function and a
related arithmetic function.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\section{Introduction}
Let $\lambda=(\lambda_0,\lambda_1,\ldots,\lambda_n)$ be a partition of
the natural number $m$ into $n+1$ parts $\lambda_i$ arranged in
non-decreasing order,
\[
m=\lambda_0+\lambda_1+\cdots+\lambda_n,
  \qquad
  1\leq\lambda_0\leq\lambda_1\leq\cdots\leq\lambda_n.
\]
The sum of the parts is called the \emph{weight} of the partition and
is denoted by $|\lambda|$, while $n+1$ is the \emph{length} of the
partition.

MacMahon \cite{mac1}, \cite[pp. 217--223]{mac2} calls the partition
$\lambda$ of weight $m$ \emph{perfect} if each positive integer less
than $m$ can be written in a \emph{unique} way as a sum of distinct
parts $\lambda_i$. Park \cite{park1} calls $\lambda$ a \emph{complete
partition} of $m$ if the representation property is maintained,
while the uniqueness constraint is dropped. (O'Shea \cite{oshea} calls
this a \emph{weak M-partition}.) Prior to Park's paper,
infinite complete sequences had been introduced by Hoggatt and King
\cite{h&k}, and studied by Brown \cite{brown}.

Park \cite{park2} generalized the notion of a complete partition to
$r$-\emph{complete partitions} for a positive integer $r$. The
partition $\lambda=(\lambda_0,\dots,\lambda_n)$ of $m$ is $r$-complete
if each integer $w$ in the interval $0\leq w\leq rm$ can be written as
\begin{equation} \label{w}
w=\alpha_0\lambda_0+\dots+\alpha_n\lambda_n\qquad\text{with}\quad
0\leq\alpha_i\leq r.
\end{equation}
Clearly, ``complete'' is the same as ``1-complete''. An $r$-complete
partition is also $(r+1)$-complete.

We call an $r$-complete partition of $m$ of minimal length a
\emph{minimal $r$-complete partition} of $m$.
O'Shea \cite{oshea} uses the term \emph{M-partition} in place of minimal
complete partition. He showed that for half the numbers $m$,
the number of M-partitions of $m$ is equal to the number of binary
partitions of $2^{n+1}-1-m$, where $n=\lfloor\log_2 m\rfloor$. (In a binary
partition, all parts are powers of $2$.) O'Shea's partial enumeration 
formula was completed by us in \cite{rdz}.

In this paper we connect the minimal $r$-complete partition function
(for $r\geq2$) to the $(r+1)$-ary partition function and a related
arithmetic function.  (In an $(r+1)$-ary partition, all parts are
powers of $r+1$.) In Section~\ref{sec:results} we state our results.
In Section~\ref{sec:complete} we consider a characterization of
minimal $r$-partitions, and in Section~\ref{sec:gen} we prove our main
result using (truncated) polynomials and formal power series.

\section{Statement of Results} \label{sec:results}
Let $f(k)$ be the $(r+1)$-ary partition function, that is, the number
of partitions of $k$ into powers of $r+1$. For the generating function
$F(x)$ we have
\[
F(x)=\sum_{k=0}^\infty
f(k)x^k=\prod_{i=0}^\infty\frac{1}{1-x^{(r+1)^i}}.
\]
We also define the auxiliary arithmetic function $g(k)$ as follows:
\[
  G(x)=\sum_{k=0}^\infty
  g(k)x^k=\sum_{j=0}^\infty\frac{x^{{(r+1)^j}-1}}
{1-x^{2(r+1)^j}} F(x^{(2r+1)(r+1)^j}) \prod_{i=0}^j\frac{1}{1-x^{(r+1)^i}}.
\]
A straightforward verification shows that the following functional
equations hold:
\begin{align}
F(x)&=\frac{1}{1-x}F(x^{r+1}), \label{F}\\
G(x)&=\frac{x^r}{1-x}G(x^{r+1})+\frac{1}{(1-x)(1-x^2)}F(x^{2r+1}).
\label{G}
\end{align}
These functional equations give simple recurring relations for fast
computation of $f(k)$ and $g(k)$. We adopt the convention that
$g(k)=0$ if $k$ is not a non-negative integer.
\begin{theorem} \label{res} Let $r\geq2$, and let $a_r(m)$ be the
  number of minimal $r$-complete partitions of $m$. Then
\[
a_r(m)=f\left(\frac{1}{r}\left((r+1)^{n+1}-1\right)-m\right)
-g\left(\frac{1}{r}\left((2r+1)(r+1)^{n-1}-1\right)-1-m\right),  
\]
where $n=\lfloor\log_{r+1}(rm)\rfloor$.
\end{theorem}
\begin{corollary} \label{cor}
We have
\[
a_r(m)=f\left(\frac{1}{r}\left((r+1)^{n+1}-1\right)-m\right)
\]
if $\frac{1}{r}((2r+1)(r+1)^{n-1}-1)\leq m
\leq\frac{1}{r}((r+1)^{n+1}-1)$.
\end{corollary} 
The case $r=1$ is not covered by Theorem \ref{res}. This case is
slightly different from $r\geq2$, as an additional arithmetic function
is required in the description of $a_1(m)$; see \cite[Theorem~2]{rdz}.
The expression for $a_r(m)$ in Theorem~\ref{res} is, however, valid
for $r=1$ if $2^n+2^{n-3}-4\leq m\leq 2^{n+1}-1$. In particular,
Corollary \ref{cor} remains valid if $r=1$, a result due to O'Shea
\cite{oshea}.

Some of the sequences appearing above can be found in Sloane's
{\em On-Line Encyclopedia of Integer Sequences} \cite{sloane}. For
perfect partitions, see sequence \seqnum{A002033}; for $a_1(m)$, see
\seqnum{A100529}. The sequences \seqnum{A000123}, \seqnum{A018819},
\seqnum{A0005704}, \seqnum{A0005705}, \seqnum{A0005706} give the
first several values of $f(k)$ for $r=1,1,2,3$, and $4$, respectively.
In addition, sequence \seqnum{A117115} gives the $53$ first values of
$g(k)$ for $r=1$, and \seqnum{A117117} gives the $53$ first values of
the additional arithmetic function required in the description of $a_1(m)$.

\section{Completeness} \label{sec:complete} 
The following lemma is due to Park \cite{park2}, with partial results
by Brown \cite{brown} and Park \cite{park1}.
\begin{lemma} \label{l1}
  The partition $\lambda=(\lambda_0,\ldots,\lambda_n)$ is $r$-complete
  if and only if $\lambda_0=1$ and
\begin{equation} \label{eqlem1}
\lambda_i\leq1+r(\lambda_0+\cdots+\lambda_{i-1})\quad\mbox{for}\quad
i=1,2,\ldots,n.
\end{equation}
\end{lemma}

The necessity of the conditions $\lambda_0=1$ and \eqref{eqlem1} is
clear, and the sufficiency follows by induction on $n$; see the proof
of Theorem 2.2 in \cite{park2}.

\bigskip 
Suppose that $\lambda=(\lambda_0,\dots,\lambda_n)$ is an $r$-complete
partition of $m$. Then \eqref{w} must be solvable for $rm+1$ values of
$w$. Since the right hand side attains at most $(r+1)^{n+1}$ distinct
values, we have $rm+1\leq(r+1)^{n+1}$.  Alternatively, by Lemma
\ref{l1}, $\lambda_i\leq(r+1)^i$ for $i=0,1,\dots,n$, so that
$rm\leq(r+1)^{n+1}-1$. In any case, we have
$\lfloor\log_{r+1}(rm)\rfloor\leq n$, cf.
\cite[Proposition~2.4]{park2}.

On the other hand, for a given $m$, let
$n=\lfloor\log_{r+1}(rm)\rfloor$.  Order the $n+1$ positive integers
$1,r+1,(r+1)^2,\ldots,(r+1)^{n-1}, k=m-\frac{1}{r}((r+1)^n-1)$ in
increasing order $1=\lambda_0\leq\lambda_1\leq\cdots\leq\lambda_n$. We
have $1\leq k\leq(r+1)^n$, and it follows that $\lambda$ is a minimal
$r$-complete partition of $m$.

\begin{lemma} \label{lem2} 
  Let $\lambda$ be an $r$-complete partition of weight $m$ and length
  $n+1$. Then $\lambda$ is minimal if and only if
\begin{equation} \label{min}
n=\lfloor\log_{r+1}(rm)\rfloor.
\end{equation}
\end{lemma}

We have shown that if $\lambda=(\lambda_0,\dots,\lambda_n)$ is a
partition of weight $m$ with $\lambda_0=1$, then $\lambda$ is a
minimal $r$-complete partition if and only if \eqref{eqlem1} and
\eqref{min} hold.

\section{Generating functions} \label{sec:gen}
In order to determine the number $a_r(m)$ of minimal $r$-complete
partitions of weight $m$, we first consider the number $q_n(m)$ of
$r$-complete partitions of weight $m$ and length $n+1$. By Lemma
\ref{lem2}, we know that such an $r$-complete partition is minimal if
and only if $\frac{1}{r}((r+1)^n-1)+1\leq m
\leq\frac{1}{r}((r+1)^{n+1}-1)$. Thus
\begin{equation} \label{am}
a_r(m)=q_n(m)\quad\text{if}\quad \frac{1}{r}\left((r+1)^n-1\right)+1 \leq
  m\leq\frac{1}{r}\left((r+1)^{n+1}-1\right).
\end{equation}
For the generating function $Q_n(x)$ of $q_n(m)$, we have
\begin{equation} \label{Q}
  Q_n(x)=\sum_{m=n+1}^{(1/r)((r+1)^{n+1}-1)}
  q_n(m)x^m =\sum_{\lambda}x^{|\lambda|},
\end{equation}
where we sum over the $\lambda$ satisfying
$1=\lambda_0\leq\lambda_1\leq\cdots\leq\lambda_n$ and \eqref{eqlem1}.
  
We change parameters by setting $\mu_i=(r+1)^i-\lambda_i$ for
$i=0,1,\ldots,n$. Then the constraints, necessary for $\lambda$ being
$r$-complete, become $\mu_0=0$, and
\begin{equation} \label{mu}
r(\mu_0+\cdots+\mu_{i-1})\leq\mu_i\leq r(r+1)^{i-1}+\mu_{i-1}
 \quad\mbox{for $i=1,\ldots,n$}.
\end{equation}
Moreover,
\begin{equation} \label{lambdamu}
|\lambda|=\frac{1}{r}((r+1)^{n+1}-1)-|\mu|,
\end{equation}
for $|\mu|=\mu_0+\cdots+\mu_n$. For a fixed $n$, we are interested in
the number of solutions $\lambda$ of $|\lambda|=m$ for each $m$ in the
interval $\frac{1}{r}((r+1)^n-1)+1 \leq
m\leq\frac{1}{r}((r+1)^{n+1}-1)$, that is, the number of solutions
$\mu$ of $|\mu|=k$ for each $k$ in the interval $0\leq
k\leq(r+1)^n-1$.

We write
\begin{equation} \label{R}
R_n(x)=\sum_{k\geq0} r_n(k)x^k=\sum_{\mu}x^{|\mu|},
\end{equation}
where we sum over the $\mu$ satisfying $\mu_0=0$ and \eqref{mu}.  We
are interested in the coefficients $r_n(k)$ for $k<(r+1)^n$.
Therefore we shall on some occasions truncate polynomials and formal
power series under consideration. We shall use the order symbol
$O(x^N)$ for truncation of order $N$. Thus, if we write
\[
\sum_k b(k)x^k=\sum_k c(k)x^k+O(x^N),
\]
then $b(k)=c(k)$ for all $k<N$.

Let $n\geq2$. It simplifies notations to ``sum'' over $\mu_0=0$. We
have
\[
R_n(x)=\sum_{\mu_0}\cdots\sum_{\mu_n} x^{\mu_0+\cdots+\mu_n},
\]
where the innermost sum is
\[
\sum_{\mu_n=r(\mu_0+\cdots+\mu_{n-1})}^{r(r+1)^{n-1}
    +\mu_{n-1}} x^{\mu_0+\cdots+\mu_n}
=x^{(r+1)(\mu_0+\cdots+\mu_{n-1})}\frac{1
    -x^{r(r+1)^{n-1}+1-r(\mu_0+\cdots+\mu_{n-1})+\mu_{n-1}}}{1-x}.
\]
Now, we have
\[
R_n(x)=\frac{1}{1-x}R_{n-1}(x^{r+1})
-\frac{x^{r(r+1)^{n-1}+1}}{1-x}\sum_{\mu_0}\cdots
 \sum_{\mu_{n-1}} x^{\mu_0+\cdots+\mu_{n-2}+2\mu_{n-1}}.
\]

We repeat this process once, and obtain
\begin{multline*}
R_n(x)=\frac{1}{1-x}R_{n-1}(x^{r+1})
-\frac{x^{r(r+1)^{n-1}+1}}{(1-x)(1-x^2)}R_{n-2}(x^{2r+1})\\
+\frac{x^{r(r+3)(r+1)^{n-2}+3}}{(1-x)(1-x^2)}
  \sum_{\mu_0}\cdots\sum_{\mu_{n-2}}
  x^{\mu_0+\cdots+\mu_{n-3}+3\mu_{n-2}},
\end{multline*}
so that
\begin{equation} \label{RecR}
R_n(x)=\frac{1}{1-x}R_{n-1}(x^{r+1})
-\frac{x^{r(r+1)^{n-1}+1}}{(1-x)(1-x^2)}R_{n-2}(x^{2r+1})
+O(x^{(r+1)^n})
\end{equation}
for $n\geq2$.

By \eqref{F} and \eqref{G}, we have
\begin{align}
F(x)&=\frac{1}{1-x}+O(x^{r+1}),\notag\\
G(x)&=\frac{1}{(1-x)(1-x^2)}+O(x^r).\label{Gx}
\end{align}
Moreover, $R_0(x)=1$, and
\[
R_1(x)=1+x+\dots+x^r=\frac{1-x^{r+1}}{1-x}=F(x)+O(x^{r+1}),
\]
so we may write
\begin{equation} \label{R1}
R_1(x)=F(x)-x^{r+1}G(x)+O(x^{r+1}).
\end{equation}

Putting $n=2$ in \eqref{RecR}, we get
\[
R_2(x)=\frac{1}{1-x}R_1(x^{r+1})
-\frac{x^{r(r+1)+1}}{(1-x)(1-x^2)}R_0(x^{2r+1}) +O(x^{(r+1)^2}),
\]
and using \eqref{R1}, we obtain
\begin{align*}
R_2(x)&=\frac{1}{1-x}F(x^{r+1})-\frac{x^{r(r+1)+1}}{(1-x)(1-x^2)}+O(x^{(r+1)^2}).
\end{align*}
Hence, by \eqref{F} and \eqref{Gx}, we have
\[
R_2(x)=F(x)-x^{r(r+1)+1}G(x)+O(x^{(r+1)^2}).
\]

We claim that if $r\geq2$ and $n\geq1$, then
\begin{equation} \label{id} 
R_n(x)=F(x)-x^{r(r+1)^{n-1}+1}G(x)+O(x^{(r+1)^n}). 
\end{equation}
To prove this, we use induction on $n$. We have just seen that the
claim is valid for $n=1$ and $n=2$. Suppose that \eqref{id} holds for
$n$ replaced by $n-1$ and by $n-2$ for some $n\geq3$. Using
\eqref{RecR} and the induction hypotheses, we obtain
\begin{align*}
R_n(x)&=\frac{1}{1-x}\left(F(x^{r+1})-x^{r(r+1)^{n-1}+r+1}G(x^{r+1})
  +O(x^{(r+1)^n})\right)\\
{}&-\frac{x^{r(r+1)^{n-1}+1}}{(1-x)(1-x^2)}
\left(F(x^{2r+1})-x^{(2r+1)(r(r+1)^{n-3}+1)}G(x^{2r+1})
+O(x^{(2r+1)(r+1)^{n-2}})\right)\\
{}&+O(x^{(r+1)^n}).
\end{align*}
We find that
\[
R_n(x)=\frac{1}{1-x}F(x^{r+1})-\frac{x^{r(r+1)^{n-1}+r+1}}{1-x}G(x^{r+1})
-\frac{x^{r(r+1)^{n-1}+1}}{(1-x)(1-x^2)}F(x^{2r+1})+O(x^{(r+1)^n}),
\]
and, using the functional equations \eqref{F} and \eqref{G}, \eqref{id} follows.

We are now ready to conclude the proof of Theorem~\ref{res}. By \eqref{R} and \eqref{lambdamu}, we have
\[
R_n(x)=\sum_\mu x^{|\mu|}=\sum_{\lambda}x^{(1/r)((r+1)^{n+1}-1)-|\lambda|}.
\]
Moreover, by \eqref{Q},
\[
R_n(x)=x^{(1/r)((r+1)^{n+1}-1)}Q_n(x^{-1})=\sum_{m=n+1}^{(1/r)((r+1)^{n+1}-1)}q_n(m)x^{(1/r)((r+1)^{n+1}-1)-m}.
\]
Hence,
\[
 R_n(x)=\sum_{k\geq0}r_n(k)x^k=\sum_{k=0}^{(1/r)((r+1)^{n+1}-1)-n-1}
q_n\left(\frac{1}{r}\left((r+1)^{n+1}-1\right)-k\right)x^k;
\]
that is,
\begin{equation} \label{rnk}
r_n(k)=q_n\left(\frac{1}{r}\left((r+1)^{n+1}-1\right)-k\right).
\end{equation}
For $n\geq1$, we have by \eqref{id},
\[
r_n(k)=f(k)-g(k-r(r+1)^{n-1}-1) \qquad\text{for}\quad 0\leq
k\leq(r+1)^n-1. 
\]
Setting $k=\frac{1}{r}\left((r+1)^{n+1}-1\right)-m$ and using
\eqref{rnk} and \eqref{am}, we get Theorem~\ref{res}. By inspection, the
theorem also holds for $n=0$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{99}
\bibitem{brown}
	 J. L. Brown, Note on complete sequences of integers,
	 {\em Amer. Math. Monthly} {\bf 68} (1961), 557--560.

\bibitem{h&k}
	V. E. Hoggatt and C. King, Problem E 1424,
	{\em Amer. Math. Monthly} {\bf 67} (1960), 593. 

\bibitem{mac1}
	P. A. MacMahon, The theory of perfect partitions and the
	compositions of multipartite numbers, {\em Messenger Math.}
	{\bf 20} (1891), 103--119.

\bibitem{mac2}
	P. A. MacMahon, {\em Combinatory Analysis}, vols. I and II,
	Cambridge University Press, 1915, 1916 (reprinted Chelsea 1960).

\bibitem{oshea}
	E. O'Shea, $M$-partitions: optimal partitions of
	weight for one scale pan, {\em Discrete Math.} {\bf 289} (2004), 81--93.

\bibitem{park1}
	S. K. Park, Complete partitions, {\em Fibonacci Quart.} {\bf 36}
	(1998), 354--360.

\bibitem{park2}
	S. K. Park, The $r$-complete partitions, {\em Discrete
	Math.} {\bf 183} (1998), 293--297.

\bibitem{rdz}
	\O. J. R\o dseth, Enumeration of M-partitions, {\em Discrete
	Math.} {\bf 306} (2006), 694--698.

\bibitem{sloane}
	N. J. A. Sloane, {\em The On-Line Encyclopedia of Integer
	Sequences}, published electronically at
	\href{http://www.research.att.com/~njas/sequences/}{http://www.research.att.com/\char'176njas/sequences/}, 2007.	

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\em Mathematics Subject Classification:} Primary 11P81; Secondary 05A17.

\noindent {\em Keywords:} complete partitions, M-partitions, $(r+1)$-ary partitions.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000123},
\seqnum{A002033},
\seqnum{A005704},
\seqnum{A005705},
\seqnum{A005706},
\seqnum{A018819},
\seqnum{A100529},
\seqnum{A117115}, and
\seqnum{A117117}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 14 2007; revised version received July 30 2007.
Published in {\it Journal of Integer Sequences}, August 3 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}