\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>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\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>\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&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&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_11$, 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&s}. Indeed, our motivation in this paper began with the desire to naturally generalize the work in \cite{s&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&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&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&0&\ldots&0&0\\ 1-m&1&\ldots&0&0\\ 1-m&1-m&\ldots&0&0\\ \vdots&\vdots&&\vdots&\vdots\\ 1-m&1-m&\ldots&1-m&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}&=&(m^{k-1},m^{k-2},\ldots,1) \left( \begin{array}{c}\varepsilon_1\\ \vdots\\ \varepsilon_k \end{array} \right)\\ &=&(m^{k-1},m^{k-2},\ldots,1)M\left(\begin{array}{c}p_1\\ \vdots\\ p_k \end{array} \right)\\ &=&(1,1,\ldots,1)\left(\begin{array}{c}p_1\\ \vdots\\ p_k \end{array} \right)\\ &=&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)&=\sum_{n=0}^\infty c(n)q^n\\ &=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}\\ &=\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 &=\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 &=\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 &=\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}\\ &\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} &2^{r-2}\sum_{n=1}^\infty \left(c(m^{r+1} n)-c(m^r n)\right)q^n \label{V4}\\ &\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 &= h_0, \label{3.12a}\\ Uh_1 &= mh_1, \label{3.12}\\ Uh_2 &= \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&=mh_1, \label{3.15}\\ H_2&=\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&=(m-1)h_1, \notag\\ L_2&=\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)&=\frac{q}{1-q}\left(\frac{1}{1-q}F(q^m)-\frac{1}{1-q^m}\right)\\ &=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)&=mh_1F(q)-h_0\frac{1}{1-q}\\ &=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)&=H_r\left(\frac{1}{1-q}F(q^m) -\frac{1}{1-q^m}\right)+L_r\\ &=\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)&=H_{r+1}F(q)-(UH_r)\frac{1}{1-q}+UL_r\\ &=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>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>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}&\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}\\ &\equiv m^i\cdot2^{r-i}\kappa_{r-1,i-1}-i(m-1)m^i\cdot2^{r-1-i}\kappa_{r-1,i}\\ &\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&=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\\ &\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)&=\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\\ &=\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&=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}}\\ &=\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}}\\ &=\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&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&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&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}