<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\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 On a Restricted $m$-Non-Squashing Partition \\
\vskip .05in
Function} \\
\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@mi.uib.no}{\tt rodseth@mi.uib.no}\\
\bigskip
James A. Sellers \\
Department of Mathematics \\
Penn State University \\
University Park, PA 16802 \\
USA \\
\href{mailto:sellersj@math.psu.edu}{\tt sellersj@math.psu.edu}\\
\end{center}

\vskip .2 in
\begin{abstract}
 For a fixed integer $m\geq2$, we say that a partition
  $n=p_1+p_2+\cdots+p_k$ of a natural number $n$ is $m$-non-squashing
  if $p_1\geq1$ and $(m-1)(p_1+\cdots+p_{j-1})\leq p_j$ for $2\leq
  j\leq k$. In this paper we give a new bijective proof that the
  number of $m$-non-squashing partitions of $n$ is equal to the number
  of $m$-ary partitions of $n$.  Moreover, we prove a similar result
  for a certain restricted $m$-non-squashing partition function
  $c(n)$ which is a natural generalization of the function which
  enumerates non-squashing partitions into distinct parts (originally
  introduced by Sloane and the second author). Finally, we prove that
  for each integer $r\geq2$,
  \[ c(m^{r+1}n)-c(m^r n)\equiv0\pmod{m^{r-1}/d^{r-2}}, \] where
  $d=\gcd(2,m)$.
\end{abstract}

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

\newcommand{\eqn}[1]{(\ref{#1})}
\newcommand{\hsp}{\hspace*{\parindent}}
\newcommand{\vsp}{\vspace{.1in}}
\newcommand{\pf}{\noindent{\bf Proof.~}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beql}[1]{\begin{equation}\label{#1}}
\newcommand{\bsq}{{\vrule height .9ex width .8ex depth -.1ex }}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\ZZ}{{\mathbb Z}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\makeatletter
% put a period after section or subsection number in header
\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2&gt;\c@secnumdepth
     \def\@svsec{}\else
     \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi
     \@tempskipa #5\relax
      \ifdim \@tempskipa&gt;\z@
        \begingroup #6\relax
          \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}%
        \endgroup
       \csname #1mark\endcsname{#7}\addcontentsline
         {toc}{#1}{\ifnum #2&gt;\c@secnumdepth \else
                      \protect\numberline{\csname the#1\endcsname}\fi
                    #7}\else
        \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname
                      {#7}\addcontentsline
                           {toc}{#1}{\ifnum #2&gt;\c@secnumdepth \else
                             \protect\numberline{\csname the#1\endcsname}\fi
                       #7}}\fi
     \@xsect{#5}}
% put a period after theorem and theorem-like numbers
\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}
\makeatother

\section{Introduction}
\hsp
We begin with the following motivation.  Suppose we have a number of
boxes each labeled by a positive integer.  A~box labeled $i$ weighs
$i$ pounds and can support a total weight of $\lfloor i/(m-1)\rfloor$
pounds where $m$ is some fixed integer greater than 1.  We wish to
build single stacks of boxes in such a way that no box will be
squashed by the weight of the boxes above it. Let $b_m(n)$ denote the
number of different ways to build such a single stack of boxes where
the total weight of all the boxes in the stack is exactly $n$ pounds.

For the sake of precision, let us say that a partition of a natural
number~$n$, 
\begin{equation} \label{1.1}
 n = p_1 + p_2 + \cdots + p_k,
\end{equation}
is $m$-non-squashing if 
\begin{equation} \label{1.2} 
p_1\geq1\quad\mbox{and}\quad
(m-1)(p_1+p_2+\cdots+p_{j-1})\leq p_j,\quad2\leq j\leq k. 
\end{equation}
If the boxes in a stack are labeled (from the top) $p_1, p_2, \ldots,
p_k$, the stack will not collapse if and only if the corresponding
partition is $m$-non-squashing.

Hirschhorn and Sellers \cite{h&amp;s} discovered the following connection
between $m$-non-squashing partitions of $n$ and $m$-ary partitions of $n$,
that is, partitions of $n$ into powers of $m$.
\begin{theorem} \label{th1}
The number $b_m(n)$ of $m$-non-squashing partitions of $n$ is equal to
the number of $m$-ary partitions of $n$.
\end{theorem}
An alternative proof of this result is given in \cite{s&amp;s}, and still
another proof is given in Section 2 below.
(See \seqnum{A000123}, \seqnum{A005704}, \seqnum{A005705},
\seqnum{A005706} and \seqnum{A018819} in Sloane's Online Encyclopedia
of Integer Sequences \cite{sloane} for sequences of values of $b_m(n)$
for $2\leq m\leq 5.$)


In this paper we shall study a restricted $m$-non-squashing partition
function $c_m(n)$, which is the number of $m$-non-squashing partitions
of $n$ such that a partition \eqn{1.1} satisfying \eqn{1.2} also
satisfies
\begin{equation} \label{1.3}
(m-1)p_1&lt;p_2\quad\mbox{if $k\geq2$}.
\end{equation}
(Note that, throughout this work, we will write $c(n)$ for $c_m(n)$
whenever the context is understood.) In particular, $c_2(n)=b(n)$, the
number of non-squashing partitions into distinct parts, recently
studied by Sloane and Sellers \cite{s&amp;s} in connection with a certain
box-stacking problem, and also studied subsequently by R\o dseth,
Sellers, and Courtright \cite{rsc}. (See \seqnum{A088567} for the
values of $c_2(n).$) 


As an example, we have $c_3(18)=9$ with the following stacks
being allowed:
\[
\boxed{18} \hspace{0.5cm} 
\stackrel{\boxed{1}}{\boxed{17}} \hspace{0.5cm} 
\stackrel{\boxed{2}}{\boxed{16}} \hspace{0.5cm}
\stackrel{\boxed{3}}{\boxed{15}} \hspace{0.5cm}
\stackrel{\boxed{4}}{\boxed{14}} \hspace{0.5cm}
\stackrel{\boxed{1}}{\stackrel{\boxed{3}}{\boxed{14}}} \hspace{0.5cm}
\stackrel{\boxed{5}}{\boxed{13}} \hspace{0.5cm}
\stackrel{\boxed{1}}{\stackrel{\boxed{4}}{\boxed{13}}} \hspace{0.5cm}
\stackrel{\boxed{1}}{\stackrel{\boxed{5}}{\boxed{12}}} 
\]
Corresponding to the stacks
\[
\stackrel{\boxed{1}}{\stackrel{\boxed{2}}{\boxed{15}}} \hspace{0.5cm}
\stackrel{\boxed{6}}{\boxed{12}} \hspace{0.5cm} 
\stackrel{\boxed{2}}{\stackrel{\boxed{4}}{\boxed{12}}}
\]
we have three more 3-non-squashing partitions of 18 which do not
satisfy the restriction $2p_1&lt;p_2$. Thus $b_3(18)=12$.

In Section 2 we give a bijective proof of the following result.
\begin{theorem} \label{th2}
  The number $c(n)$ of restricted $m$-non-squashing partitions of $n$
  is equal to the number of partitions of $n$ into powers of
  $m$ such that either all parts are equal to 1 or, if the largest
  part has size $m^i&gt;1$, then there is at least one part of size
  $m^{i-1}$ present in the partition.
\end{theorem}
Theorem \ref{th2} is a natural generalization of the $m=2$ result
which was proven by Sloane and Sellers \cite[Corollary 3]{s&amp;s}.
Indeed, our motivation in this paper began with the desire to
naturally generalize the work in \cite{s&amp;s} on a certain restricted
family of 2-non-squashing partitions of $n$.
(See \seqnum{A090678} for additional information on $c_2(n)$ modulo 2.)


An immediate consequence of Theorem \ref{th2} is that the generating
function $F(q)=\sum_{n=0}^\infty c(n)q^n$ is explicitly given by
\begin{equation}
F(q)=\frac{1}{1-q}+
\sum_{i=1}^\infty\frac{q^{(m+1)m^{i-1}}}{\prod_{j=0}^i (1-q^{m^j})} ;
\label{1.6}
\end{equation}
cf. Section 2. It follows that $F(q)$ satisfies the functional equation
\begin{equation}
F(q)=\frac{1}{1-q}F(q^m)-\frac{q^m}{1-q^m}.
\label{1.7}
\end{equation}

Since $c(n)$ can be viewed as a restricted $m$-ary partition
function, and since a number of congruence properties are well-known
for other restricted $m$-ary partition functions \cite{r&amp;s1}, we
decided to search for similar congruence properties satisfied by
$c(n)$.  This proved to be a fruitful endeavour as the following result
was discovered.
\begin{theorem} \label{th3}
For each integer $r\geq2$ and all $n\geq1$, 
\[
c(m^{r+1}n)-c(m^r n)\equiv0\pmod{m^{r-1}/d^{r-2}},   
\]
where $d=\gcd(2,m)$.
\end{theorem}
Theorem~\ref{th3} is an immediate consequence of the much more precise
Theorem~\ref{thV} in Section~\ref{sec:ap}, where we study 
arithmetic properties of $c(n)$ by exploiting the functional equation
\eqn{1.7} and by adapting tools developed in \cite{r&amp;s1, rsc}.

\section{A bijection}
\hsp
Let $\mathcal A_k(n)$ denote the set of $m$-non-squashing partitions
$(p_1,\ldots,p_k)$ of $n$ into exactly $k$ parts $p_i$ satisfying (\ref{1.1})
and (\ref{1.2}), and let $\mathcal B_k(n)$ denote the set of $m$-ary
partitions $(\varepsilon_1,\ldots,\varepsilon_k)$ of $n$ with largest
part $m^{k-1}$, that is
\begin{equation} \label{2.1}
n=\varepsilon_1m^{k-1}+\varepsilon_2m^{k-2}+\cdots+\varepsilon_k
\end{equation}
with
\begin{equation} \label{2.2}
\varepsilon_1\geq1\quad\mbox{and}\quad\varepsilon_2,\ldots,\varepsilon_k\geq0.
\end{equation}

For $(p_1,\dots,p_k)\in\mathbb Z^k$, let
$\psi(p_1,\dots,p_k)=(\varepsilon_1,\ldots,\varepsilon_k)$, 
where 
\begin{equation} \label{2.3}
\varepsilon_j=p_j-(m-1)\sum_{i=1}^{j-1}p_i, \qquad j=1,2,\ldots,k, 
\end{equation}
and where, as usual, an empty sum is taken as zero. We may
alternatively write \eqn{2.3} as
\[
M\left(\begin{array}{c}p_1\\ \vdots\\ p_k
\end{array} \right)
=\left( \begin{array}{c}\varepsilon_1\\ \vdots\\ \varepsilon_k
\end{array} \right),
\]
where
\[
M=\left( \begin{array}{ccccc}1&amp;0&amp;\ldots&amp;0&amp;0\\
                              1-m&amp;1&amp;\ldots&amp;0&amp;0\\
                              1-m&amp;1-m&amp;\ldots&amp;0&amp;0\\
                              \vdots&amp;\vdots&amp;&amp;\vdots&amp;\vdots\\
                              1-m&amp;1-m&amp;\ldots&amp;1-m&amp;1
           \end{array} \right).
\]
We see that $M\in\mathrm{SL}_k(\mathbb Z)$, the multiplicative group
of $k\times k$ matrices with entries in $\mathbb Z$ and determinant
$+1$.

We have
\begin{eqnarray*}
\sum_{j=1}^k\varepsilon_j m^{k-j}&amp;=&amp;(m^{k-1},m^{k-2},\ldots,1)
\left( \begin{array}{c}\varepsilon_1\\ \vdots\\ \varepsilon_k
\end{array} \right)\\
&amp;=&amp;(m^{k-1},m^{k-2},\ldots,1)M\left(\begin{array}{c}p_1\\ \vdots\\ p_k
\end{array} \right)\\
&amp;=&amp;(1,1,\ldots,1)\left(\begin{array}{c}p_1\\ \vdots\\ p_k
\end{array} \right)\\
&amp;=&amp;p_1+p_2+\cdots+p_k,
\end{eqnarray*}
so that (\ref{1.1}) is satisfied if and only if (\ref{2.1}) is true.
By (\ref{2.3}), we have that (\ref{1.2}) holds if and only if
(\ref{2.2}) holds. Hence $(p_1,\ldots,p_k)\in\mathcal A_k(n)$ if and
only if $(\varepsilon_1,\ldots,\varepsilon_k)\in\mathcal B_k(n)$.
Since $M$ is invertible, it follows (with a slight abuse of
notation) that
\begin{equation} \label{2.7}
\psi:\mathcal A_k(n)\longrightarrow\mathcal B_k(n)
\end{equation}
is invertible and, therefore, is a \emph{bijection}.

In particular, we have
\[
|\mathcal A_k(n)|=|\mathcal B_k(n)|,
\]
which may be stated as follows.
\begin{theorem} \label{th4}
The number of $m$-non-squashing partitions of $n$ into exactly $k$ parts is
equal to the number of $m$-ary partitions of $n$ with largest part
$m^{k-1}$.~~~$\bsq$
\end{theorem}

Moreover, 
\[
\left|\bigcup_{i=1}^k\mathcal A_i(n)\right| 
=\left|\bigcup_{i=1}^k\mathcal B_i(n)\right|,
\]
that is, the number of $m$-non-squashing partitions of $n$ in at most
$k$ parts is equal to the number $b_{m,k}(n)$ of $m$-ary partitions of
$n$ where the largest part is at most $m^{k-1}$.

We also have
\[
\left|\bigcup_{k\geq1}\mathcal A_k(n)\right| 
=\left|\bigcup_{k\geq1}\mathcal B_k(n)\right|,
\]
which proves Theorem \ref{th1}.

Furthermore, when $(p_1,\ldots,p_k)$ and
$(\varepsilon_1,\ldots,\varepsilon_k)$ are related by
\eqn{2.3}, then \eqn{1.3} is satisfied if and only if
$\varepsilon_2\geq1$, and Theorem \ref{th2} follows.

Using the interpretation of $c(n)$ as the number of restricted
$m$-ary partitions of $n$, we have, putting $c(0)=1$,
\begin{align*}
F(q)&amp;=\sum_{n=0}^\infty c(n)q^n\\
&amp;=1+\sum_{\varepsilon_1\geq1} q^{\varepsilon_1}+
\sum_{k=2}^\infty\sum_{\stackrel{\varepsilon_1,\varepsilon_2\geq1}
{\varepsilon_3,\ldots,\varepsilon_k\geq0}}
q^{\varepsilon_1m^{k-1}+\varepsilon_2m^{k-2}+\cdots+\varepsilon_k}\\
&amp;=\frac{1}{1-q}+\sum_{k=2}^\infty\frac{q^{m^{k-1}}}{1-q^{m^{k-1}}}
\cdot\frac{q^{m^{k-2}}}{1-q^{m^{k-2}}}
\cdot\frac{1}{1-q^{m^{k-3}}}\cdots\frac{1}{1-q},
\end{align*}
and \eqn{1.6} follows.

\section{Arithmetic properties of $c(n)$} \label{sec:ap}
\hsp
In this section we use properties of the generating function
\[
F(q)=\sum_{n=0}^\infty c(n)q^n
\]
to study $c(n)$. The closed form \eqn{1.6} for $F(q)$ will
not be of any direct use to us. Our method is strongly
dependent upon the generating function having a reasonably simple
functional equation. In the present case we have the nice functional
equation \eqn{1.7}, which we shall repeatedly use in the form
\begin{equation} \label{funceq}
F(q)-1=\frac{1}{1-q}F(q^m)-\frac{1}{1-q^m}.
\end{equation}

\subsection{Statement of main result}
\hsp
We shall prove the following theorem from which Theorem \ref{th3}
immediately follows.
\begin{theorem} \label{thV}
We have
\begin{align}
\sum_{n=1}^\infty\left(c(mn)-c(n)\right)q^n
&amp;=\frac{q}{1-q}\left(F(q)-1\right), \label{V1}\\
\sum_{n=1}^\infty\left(c(m^2 n)-c(mn)\right)q^n
&amp;=\frac{mq}{(1-q)^2}\left(F(q)-1\right) +\frac{(m-1)q}{(1-q)^2}, \label{V2}\\
\sum_{n=1}^\infty\left(c(m^3 n)-c(m^2 n)\right)q^n
&amp;=\left(-\frac{\frac{1}{2}(m^3-m^2)q}{(1-q)^2}+\frac{m^3q}{(1-q)^3}\right)
\left(F(q)-1\right) \label{V3}\\ 
&amp;\quad+\left(-\frac{\frac{1}{2}(m^3-3m^2+2m)q}{(1-q)^2}+
  \frac{(m^3-m^2)q}{(1-q)^3}  
  \right), \notag
\end{align}
and more generally for $r\geq3$,
\begin{align}
&amp;2^{r-2}\sum_{n=1}^\infty \left(c(m^{r+1} n)-c(m^r n)\right)q^n \label{V4}\\
&amp;\qquad\qquad=\left(\sum_{i=1}^r \frac{\mu_{r,i}q}{(1-q)^{i+1}}\right) \left(
    F(q)-1\right)+\left(\sum_{i=1}^r\frac{\lambda_{r,i}q}
    {(1-q)^{i+1}}\right), \notag  
\end{align}
where $\mu_{r,i}$ and $\lambda_{r,i}$ are integers satisfying
\begin{equation}  \label{V5}
\mu_{r,i}\equiv\lambda_{r,i}\equiv0\pmod{m^{r-1+(i^2-i)/2}}.
\end{equation}
\end{theorem}

In Section \ref{sec:aux} we state the necessary auxiliaries for the
proof of Theorem \ref{thV}, but postpone the technical details. In
Section \ref{sec:proof} we prove Theorem \ref{thV}. In Section
\ref{sec:details} we demonstrate the technical details necessary to
prove the auxiliary results in Section \ref{sec:aux}.

\subsection{Auxiliaries} \label{sec:aux}
\hsp
The power series in this paper are elements of $\mathbb Z[[q]]$,
the ring of formal power series in $q$ with coefficients in $\mathbb
Z$. We define a $\mathbb Z$-linear operator
$$U:\mathbb Z[[q]]\longrightarrow\mathbb Z[[q]]$$
by
\[
U\sum_n a(n)q^n =\sum_n a(mn)q^n .
\]
Notice that if $f(q), g(q)\in\mathbb Z[[q]]$, then
\begin{equation}
U\left(f(q)g(q^m)\right)=\left(Uf(q)\right)g(q) .
\label{3.3}
\end{equation}

Let
\begin{equation} \label{3.7}
h_i=h_i(q)=\frac{q}{(1-q)^{i+1}}\qquad\mbox{for $i\geq0$}.
\end{equation}
Then
\begin{equation}
h_i =\sum_{n=1}^\infty {n+i-1\choose i}q^n,
\label{3.8}
\end{equation}
so that
\begin{equation} \label{3.8a}
Uh_r=\sum_{n=1}^\infty {mn+r-1\choose r}q^n.
\end{equation}
Simple calculations show that
\begin{align}
Uh_0 &amp;= h_0, \label{3.12a}\\
Uh_1 &amp;= mh_1, \label{3.12}\\
Uh_2 &amp;= \textstyle -\frac{1}{2}m(m-1)h_1+m^2h_2. \notag
\end{align}

We shall recursively define functions $H_r$ and $L_r$. The motivation
for these definitions will become clear in the following section. First, let 
\begin{equation}
H_0=h_0 \quad \textrm{and} \quad
H_{i+1}=U\Big(\frac{1}{1-q}H_i\Big),\quad i\geq 0.
\label{3.14}
\end{equation}
We find
\begin{align}
H_1&amp;=mh_1, \label{3.15}\\
H_2&amp;=\textstyle -\frac{1}{2}m^2(m-1)h_1+m^3h_2. \notag
\end{align}
We have similar results for each $r\geq2$, as shown by the following
lemma.
\begin{lemma} \label{leV1}
For $r\geq2$ there exist integers $\mu_{r,i}$ such that
\begin{equation}
2^{r-2}H_r=\sum_{i=1}^r\mu_{r,i}h_i ,
\label{V3.17}
\end{equation}
where
\begin{equation}
\mu_{r,i}\equiv 0\pmod{m^{r-1+(i^2-i)/2}}\quad\mbox{for $1\leq i\leq r$}.
\label{V3.18}
\end{equation}
\end{lemma}

\bigskip
Second, we define
\begin{equation} \label{3.35}
L_0=0\quad\mbox{and}\quad L_{i+1}=H_{i+1}-(UH_i)\frac{1}{1-q}+UL_i,
\quad i\geq0.
\end{equation}
Then
\begin{align}
L_1&amp;=(m-1)h_1, \notag\\
L_2&amp;=\textstyle-\frac{1}{2}m(m-1)(m-2)h_1+m^2(m-1)h_2. \label{L2}
\end{align}
\begin{lemma} \label{leV2}
For $r\geq2$ there exist integers $\lambda_{r,i}$ such that
\begin{equation} \label{3.38}
2^{r-2}L_r=\sum_{i=1}^r\lambda_{r,i}h_i,
\end{equation}
where
\[
\lambda_{r,i}\equiv0\pmod{m^{r-1+(i^2-i)/2}} \text{\ \ for}
\quad1\leq i\leq r.
\]
\end{lemma}


\subsection{Proof of Theorem \ref{thV}} \label{sec:proof}
\hsp
With the results of the previous section in hand, it is straightforward to
prove Theorem~\ref{thV}. We start by applying the operator $U$ to the
functional equation \eqn{funceq}. Using \eqn{3.3} we get
\[
UF(q)-1=\frac{1}{1-q}F(q)-\frac{1}{1-q},
\]
so that
\[
UF(q)-F(q)=\frac{q}{1-q}\left(F(q)-1\right),
\]
which is \eqn{V1}.

Using \eqn{funceq} we further obtain  
\begin{align*}
UF(q)-F(q)&amp;=\frac{q}{1-q}\left(\frac{1}{1-q}F(q^m)-\frac{1}{1-q^m}\right)\\
&amp;=h_1F(q^m)-h_0\frac{1}{1-q^m}.
\end{align*}
Application of $U$ gives, by \eqn{3.12a} and \eqn{3.12},
\begin{align*}
U^2 F(q)-UF(q)&amp;=mh_1F(q)-h_0\frac{1}{1-q}\\
&amp;=mh_1\left(F(q)-1\right)+(m-1)h_1,
\end{align*}
which proves \eqn{V2}. Repeating this process once more, we get
\eqn{V3}. 

More generally, we claim that
\begin{equation} \label{3.51}
U^{r+1}F(q)-U^r F(q)=H_r\left(F(q)-1\right)+L_r \quad\mbox{for $r\geq0$}.
\end{equation}
This follows by induction on $r$. The identity is true for
$r=0$. Suppose that it holds for some $r\geq0$. Then, by \eqn{funceq},
\begin{align*}
  U^{r+1}F(q)-U^r F(q)&amp;=H_r\left(\frac{1}{1-q}F(q^m)
    -\frac{1}{1-q^m}\right)+L_r\\ 
  &amp;=\left(\frac{1}{1-q}H_r\right)F(q^m)-H_r\frac{1}{1-q^m}+L_r.
\end{align*}
Application of $U$ now gives, using \eqn{3.14}, \eqn{3.3}, and \eqn{3.35},
\begin{align*}
U^{r+2}F(q)-U^{r+1}F(q)&amp;=H_{r+1}F(q)-(UH_r)\frac{1}{1-q}+UL_r\\
&amp;=H_{r+1}\left(F(q)-1\right)+L_{r+1}.
\end{align*}
This proves our claim.

For $r\geq2$, we multiply \eqn{3.51} by $2^{r-2}$, and apply
Lemma \ref{leV1} to $2^{r-2}H_r$ and Lemma \ref{leV2} to
$2^{r-2}L_r$. Then we get \eqn{V4} with the congruences \eqn{V5}
satisfied. This completes the proof of Theorem \ref{thV}.

\subsection{Technical details} \label{sec:details}
\hsp
In this section we prove Lemmas \ref{leV1} and \ref{leV2}. For this, we
shall need a few properties of binomial coefficients. It is well known
that the abelian group of all polynomials of degree at most $r$ in $n$
with complex coefficients, and which map integers to integers, is free
with basis $\{ {n+i-1\choose i}\mid i=0,1,\ldots,r\}$.  Moreover, the
subgroup consisting of those polynomials which also map 0 to 0, is
free with basis $\{ {n+i-1\choose i}\mid i=1,\ldots,r\}$.  In
particular, the following lemma holds.
\begin{lemma}
\label{le1}
For each positive integer $r$ there exist unique integers
$\alpha_{r,i}$, such that for all $n$,
\begin{equation} \label{3.4}
{mn+r-1\choose r} =\sum_{i=1}^r \alpha_{r,i}{n+i-1\choose i}.~~~\bsq
\end{equation}
\end{lemma}

\bigskip
Comparing the coefficients of $n^r$ in \eqn{3.4}, we get
\begin{equation} \label{3.5}
\alpha_{r,r}=m^r,
\end{equation}
and comparing the coefficients of $n^{r-1}$, we get
\begin{equation} \label{3.6}
\alpha_{r,r-1}=\textstyle -\frac{1}{2}(r-1)(m-1)m^{r-1}.
\end{equation}
It follows from Lemma \ref{le1}, \eqn{3.8}, and \eqn{3.8a} that
\begin{equation}
Uh_r =\sum_{i=1}^r \alpha_{r,i}h_i\qquad\mbox{for $r\geq1$.}
\label{3.10}
\end{equation}

We now turn to Lemma \ref{leV1}. We prove a slightly more precise
result, which we shall need in our proof of Lemma~\ref{leV2}. Notice
that the set $\{h_0,h_1,\ldots\}$ is linearly independent over
$\mathbb Z$ (and over $\mathbb C$), so the integers $\kappa_{r,i}$ in
Lemma~\ref{le2} below are \emph{uniquely} determined by $r$ and $i$
(and $m$). The same remark applies, of course, to other linear
combinations of the~$h_i$.  
\begin{lemma} \label{le2}
For $1\leq i\leq r$ there exist integers $\kappa_{r,i}$ such that
\begin{equation}
H_r=\sum_{i=1}^r \kappa_{r,i}h_i ,
\label{3.17}
\end{equation}
where
\begin{equation}
2^{r-i}\kappa_{r,i}\equiv 0\pmod{m^{r+(i^2-i)/2}}.
\label{3.18}
\end{equation}
\end{lemma}

\paragraph{Remark.}
Let $r\geq2$. Notice that \eqn{3.18} for $i=1$
implies $2^{r-2}\kappa_{r,1}\equiv0$ (mod $m^{r-1}$). Thus, by setting
$\mu_{r,i}=2^{r-2}\kappa_{r,i}$, Lemma \ref{le2} gives us Lemma
\ref{leV1}. 

\paragraph{Note.}
In the following we set $\kappa_{r,i}=0$ if $i=0$ or if
$i&gt;r$. These values of $\kappa$ trivially satisfy~(\ref{3.18}).  

\paragraph{Proof.}
We use induction on $r$. By \eqn{3.15}, the lemma is true for
$r=1$. Suppose that for some $r&gt;1$, we have
\begin{equation}
H_{r-1}=\sum_{i=1}^{r-1}\kappa_{r-1,i}h_i , 
\label{3.19}
\end{equation}
where the $\kappa_{r-1,i}$ are integers satisfying
\begin{equation}
2^{r-1-i}\kappa_{r-1,i}\equiv 0 \pmod{m^{r-1+(i^2-i)/2}}, \qquad
i=1,2,\ldots,r-1. 
\label{3.20}
\end{equation}
Then, by \eqn{3.14}, \eqn{3.19}, and \eqn{3.7},
\[
H_r=U\left(\frac{1}{1-q}H_{r-1}\right)
=U\sum_{i=1}^{r-1}\kappa_{r-1,i}h_{i+1} 
=\sum_{j=1}^r \kappa_{r-1,j-1}Uh_j,
\]
and, by \eqn{3.10},
\[
H_r=\sum_{j=1}^{r}\kappa_{r-1,j-1}\sum_{i=1}^j\alpha_{j,i}h_i 
=\sum_{i=1}^r\sum_{j=i}^r\alpha_{j,i}\kappa_{r-1,j-1}h_i,
\]
so that \eqref{3.17} holds with
\[
\kappa_{r,i}=\sum_{j=i}^r\alpha_{j,i}\kappa_{r-1,j-1},
\]
and all the $\kappa_{r,i}$ are integers.

Moreover, for $1\leq i\leq r$ we have
\begin{equation} \label{3.23}
2^{r-i}\kappa_{r,i}=\sum_{j=i}^r 2^{j-i}\alpha_{j,i} \cdot
2^{r-j}\kappa_{r-1,j-1}. 
\end{equation}
By \eqn{3.20},
\[
2^{r-j}\kappa_{r-1,j-1}\equiv0\pmod{m^{r+(i^2-i)/2}}\quad\mbox{for $j\geq
  i+2$}, 
\]
so that, by \eqn{3.23}, \eqn{3.5}, \eqn{3.6}, and \eqn{3.20},
\begin{align*}
2^{r-i}\kappa_{r,i}&amp;\equiv\alpha_{i,i}\cdot2^{r-i}\kappa_{r-1,i-1}
+2\alpha_{i+1,i}\cdot2^{r-1-i}\kappa_{r-1,i}\\
&amp;\equiv m^i\cdot2^{r-i}\kappa_{r-1,i-1}-i(m-1)m^i\cdot2^{r-1-i}\kappa_{r-1,i}\\
&amp;\equiv0\pmod{m^{r+(i^2-i)/2}}. ~~~\bsq
\end{align*}
Incidentally, we have $\kappa_{r,r}=m^{(r^2+r)/2}$.

Next we consider the term $UH_r$ appearing in the definition
\eqref{3.35}. We have, by (\ref{3.15}) and (\ref{3.12}),  
\[
UH_1=m^2h_1.
\]
Similarly we find
\[
UH_2=\textstyle-\frac{1}{2}m^3(m-1)(m+1)h_1+m^5 h_2.
\]

\begin{lemma} \label{leV3}
For $1\leq i\leq r$ there exist integers $\nu_{r,i}$ such that
\begin{equation}
2^{r-1}UH_r=\sum_{i=1}^r\nu_{r,i}h_i ,
\label{3.30}
\end{equation}
where
\begin{equation}
\nu_{r,i}\equiv 0\pmod{m^{r+(i^2+i)/2}}.
\label{3.31}
\end{equation}
\end{lemma}

\paragraph{\bf Proof.}
For $r\geq1$, we have by Lemma \ref{le2} and (\ref{3.10}), 
\begin{align*}
2^{r-1}UH_r&amp;=2^{r-1}\sum_{j=1}^r\kappa_{r,j}Uh_j
=2^{r-1}\sum_{j=1}^r\kappa_{r,j}\sum_{i=1}^j\alpha_{j,i}h_i\\
&amp;\quad=2^{r-1}\sum_{i=1}^r\sum_{j=i}^r\alpha_{j,i}\kappa_{r,j}h_i,
\end{align*}
so that \eqn{3.30} is satisfied by setting
\[
\nu_{r,i}=2^{r-1}\sum_{j=i}^r\alpha_{j,i}\kappa_{r,j}.
\]
Then all the $\nu_{r,i}$ are integers.

Moreover, by \eqn{3.18},
\[
2^{r-1}\kappa_{r,j}\equiv0\pmod{m^{r+(i^2+i)/2}}\quad\mbox{for $j\geq i+1$}.
\]
Hence, using \eqn{3.5} and \eqn{3.18},
\[
\nu_{r,i}\equiv2^{r-1}\alpha_{i,i}\kappa_{r,i}
\equiv m^i\cdot2^{r-1}\kappa_{r,i}\equiv0\pmod{m^{r+(i^2+i)/2}}.~~~\bsq
\]

\bigskip
Finally, we prove Lemma \ref{leV2}. Again we use induction on $r$. By
\eqn{L2}, the lemma is true for $r=2$. Suppose that for some $r\geq3$
there are integers $\lambda_{r-1,j}$ such that 
\[
2^{r-3}L_{r-1}=\sum_{j=1}^{r-1}\lambda_{r-1,j}h_j,
\]
where
\begin{equation} \label{3.43}
\lambda_{r-1,j}\equiv0\pmod{m^{r-2+(j^2-j)/2}}.
\end{equation}
Then
\begin{align*}
U\left(2^{r-3}L_{r-1}\right)&amp;=\sum_{j=1}^{r-1}\lambda_{r-1,j}Uh_j
=\sum_{j=1}^{r-1}\lambda_{r-1,j}\sum_{i=1}^j\alpha_{j,i}h_i\\
&amp;=\sum_{i=1}^{r-1}\sum_{j=i}^{r-1}\alpha_{j,i}\lambda_{r-1,j}h_i.
\end{align*}
Hence,
\begin{align*}
2^{r-2}L_r&amp;=2^{r-2}H_r-2^{r-2}(UH_{r-1})\frac{1}{1-q}+
2^{r-2}UL_{r-1}\qquad\mbox{by \eqn{3.35}}\\ 
&amp;=\sum_{i=1}^r\mu_{r,i}h_i-\sum_{j=1}^{r-1}\nu_{r-1,j}h_{j+1}+2^{r-2}UL_{r-1}
\qquad\mbox{by \eqn{V3.17} and \eqn{3.30}}\\
&amp;=\sum_{i=1}^r\mu_{r,i}h_i -\sum_{i=2}^r\nu_{r-1,i-1}h_i
+2\sum_{i=1}^{r-1}\sum_{j=i}^{r-1}\alpha_{j,i}\lambda_{r-1,j}h_i.
\end{align*}
Thus, \eqn{3.38} holds with
\begin{equation} \label{3.46}
\lambda_{r,i}=\mu_{r,i}
-\nu_{r-1,i-1}+2\sum_{j=i}^{r-1}\alpha_{j,i}\lambda_{r-1,j}, 
\end{equation}
where $\nu_{r-1,0}=0$. In particular we have, by \eqn{V3.18} and
\eqn{3.31}, 
\[
\lambda_{r,r}=\mu_{r,r}-\nu_{r-1,r-1}
\equiv0\pmod{m^{r-1+(r^2-r)/2}},
\]
and, for $1\leq i\leq r-1$,
\[
\lambda_{r-1,j}\equiv0\pmod{m^{r-1+(i^2-i)/2}} \quad\mbox{for $j\geq
  i+1$}.
\]
Hence, using \eqn{3.46}, \eqn{V3.18}, \eqn{3.31}, \eqn{3.5}, and
\eqn{3.43}, we have 
\[
\lambda_{r,i}=\mu_{r,i}-\nu_{r-1,i-1}+2\alpha_{i,i}\lambda_{r-1,i}
\equiv0\pmod{m^{r-1+(i^2-i)/2}}.
\]
This completes the proof of Lemma \ref{leV2}.

\medskip
As in the case of Lemma~\ref{leV1} and Lemma~\ref{le2}, we can state a more
precise form of Lemma~\ref{leV2}. While we used the more precise
Lemma~\ref{le2} in the proof of Lemma~\ref{leV3} on our way towards
the proof of Lemma~\ref{leV2}, there is no such reason to sharpen
Lemma~\ref{leV2}. 

\section{Closing remarks}
\hsp
It is interesting to note that the results above provide a general
framework for proving a number of similar identities.  Indeed, thanks
to the bijection given in \eqn{2.7}, we now have the means to prove
an infinite family of similar partition results.  For, if instead of
\eqref{1.3} we restrict \eqn{1.2} in another way, we get a different
type of restricted $m$-non-squashing partition. Then, by \eqn{2.7},
we can prove that the number of such partitions of $n$ is equal to the
number of suitably restricted $m$-ary partitions of $n$.

Once we have established that a certain restricted $m$-non-squashing
partition function is equal to a suitably restricted $m$-ary partition
function, it will most likely be straightforward to find a closed form
for the corresponding generating function $G(q)$ (similar to
\eqn{1.6} above). If a functional equation relating $G(q)$ and
$G(q^m)$ (similar to \eqn{1.7} above) can then be found, then one
can use the method utilized in this paper to prove arithmetic
properties for the restricted $m$-non-squashing partition function in
question.

\section{Acknowledgments}

The authors express their gratitude to the referee for providing
several interesting comments and suggestions. 

\begin{thebibliography}{5}

\bibitem{h&amp;s} 
M. D. Hirschhorn and J. A. Sellers, A different view of
$m$-ary partitions, \textsl{Australas. J. Combin.} \textbf{30}
(2004), 193--196.

\bibitem{r&amp;s1} 
\O. J. R\o dseth and J. A. Sellers, On $m$-ary partition
function congruences: A fresh look at a past problem,
\textsl{J. Number Theory} \textbf{87} (2001), 270--281.

\bibitem{rsc} 
\O. J. R\o dseth, J. A. Sellers, and K. M. Courtright,
  Arithmetic properties of non-squashing partitions into distinct
  parts, \textsl{Ann. Comb.} \textbf{8} (2004), 347--353.

\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/}{\tt
  http://www.research.att.com/$\sim$njas/sequences/}, 2005. 

\bibitem{s&amp;s} N. J. A. Sloane and J. A. Sellers, On non-squashing
  partitions, \textsl{Discrete Math}. \textbf{294} (2005), 259--274.

\end{thebibliography}



\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:} partitions, $m$-non-squashing partitions, $m$-ary
partitions, stacking boxes, congruences

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000123}
\seqnum{A005704} \seqnum{A005705} \seqnum{A005706}
\seqnum{A018819} \seqnum{A088567} and \seqnum{A090678}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 20 2005;
revised version received  October 23 2005.
Published in {\it Journal of Integer Sequences}, October 24 2005.

\bigskip
\hrule
\bigskip

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



\end{document}





\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary ; Secondary .

\noindent \emph{Keywords: } xxx

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A0xxxxx}.)

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>