On a Restricted m-Non-Squashing Partition Function

Øystein J. Rødseth Department of Mathematics University of Bergen Johs. Brunsgt. 12 N–5008 Bergen NORWAY

                   rodseth@mi.uib.no

James A. Sellers Department of Mathematics Penn State University University Park, PA 16802 USA

                 sellersj@math.psu.edu

Abstract

For a fixed integer m ≥ 2, we say that a partition n = p_{1} + p_{2} + ⋯ + p_{k} of a natural number n is m-non-squashing if p_{1} ≥ 1 and (m − 1)(p_{1} + ⋯ + p_{j−1}) ≤ p_{j} for 2 ≤ j ≤ 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 ≥ 2,

c(m^{r+1}n) − c(m^{r}n) ≡ 0 (mod m^{r−1}/d^{r−2}),

where d = gcd(2, m).

1. Introduction

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 ⌊i/(m − 1)⌋ 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,

n = p_{1} + p_{2} + ⋯ + p_{k},  (1)

is m-non-squashing if

p_{1} ≥ 1 and (m − 1)(p_{1} + p_{2} + ⋯ + p_{j−1}) ≤ p_{j}, 2 ≤ j ≤ k.  (2)

If the boxes in a stack are labeled (from the top) p_{1}, p_{2}, …, p_{k}, the stack will not collapse if and only if the corresponding partition is m-non-squashing.

Hirschhorn and Sellers [1] 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.

Theorem 1.1. The number b_{m}(n) of m-non-squashing partitions of n is equal to the number of m-ary partitions of n.

An alternative proof of this result is given in [5], and still another proof is given in Section 2 below. (See \underline{A000123}, \underline{A005704}, \underline{A005705}, \underline{A005706} and \underline{A018819} in Sloane’s Online Encyclopedia of Integer Sequences [4] for sequences of values of b_{m}(n) for 2 ≤ m ≤ 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 (1) satisfying (2) also satisfies

(m − 1)p_{1} < p_{2} if k ≥ 2.  (3)

(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 [5] in connection with a certain box-stacking problem, and also studied subsequently by Rødseth, Sellers, and Courtright [3]. (See \underline{A088567} for the values of c_{2}(n).)

As an example, we have c_{3}(18) = 9 with the following stacks being allowed:

18  1 17 2 16 3 15 4 14 1 3 14 5 13 1 4 13 1 5 12

Corresponding to the stacks

1 2 15 6 12 2 4 12

we have three more 3-non-squashing partitions of 18 which do not satisfy the restriction 2p_{1} < p_{2}. Thus b_{3}(18) = 12.

In Section 2 we give a bijective proof of the following result.

Theorem 1.2. 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} > 1, then there is at least one part of size m^{i−1} present in the partition.

Theorem 1.2 is a natural generalization of the m = 2 result which was proven by Sloane and Sellers [5, Corollary 3]. Indeed, our motivation in this paper began with the desire to naturally generalize the work in [5] on a certain restricted family of 2-non-squashing partitions of n. (See \underline{A090678} for additional information on c_{2}(n) modulo 2.)

An immediate consequence of Theorem 1.2 is that the generating function F (q) = ∑_{n=0}^{∞} c(n)q^{n} is explicitly given by

F (q) = \frac{1}{1 − q} + ∑_{i=1}^{∞} \frac{q^{(m+1)m^{i−1}}}{∏_{j=0}^{i}(1 − q^{m^{j}})};  (4)

cf. Section 2. It follows that F (q) satisfies the functional equation

F (q) = \frac{1}{1 − q} F (q^{m}) − \frac{q^{m}}{1 − q^{m}} .  (5)

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 [2], 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.

Theorem 1.3. For each integer r ≥ 2 and all n ≥ 1,

c(m^{r+1}n) − c(m^{r}n) ≡ 0 (mod m^{r−1}/d^{r−2}),

where d = gcd(2, m).

Theorem 1.3 is an immediate consequence of the much more precise Theorem 3.1 in Section 3, where we study arithmetic properties of c(n) by exploiting the functional equation (5) and by adapting tools developed in [2, 3].

2. A bijection

Let A_{k}(n) denote the set of m-non-squashing partitions (p_{1}, …, p_{k}) of n into exactly k parts p_{i} satisfying (1) and (2), and let B_{k}(n) denote the set of m-ary partitions (ε_{1}, …, ε_{k}) of n with largest part m^{k−1}, that is

n = ε_{1}m^{k−1} + ε_{2}m^{k−2} + ⋯ + ε_{k}  (6)

with

ε_{1} ≥ 1 and ε_{2}, …, ε_{k} ≥ 0.  (7)

For (p_{1}, …, p_{k}) ∈ ℤ^{k}, let ψ(p_{1}, …, p_{k}) = (ε_{1}, …, ε_{k}), where

ε_{j} = p_{j} − (m − 1) ∑_{i=1}^{j−1} p_{i},  j = 1, 2, …, k,  (8)

and where, as usual, an empty sum is taken as zero. We may alternatively write (8) as

M ( p_{1} ; ⋮ ; p_{k} ) = ( ε_{1} ; ⋮ ; ε_{k} ) ,

where

M = ( \begin{matrix}1 & 0 & … & 0 & 0 \\ 1 − m & 1 & … & 0 & 0 \\ 1 − m & 1 − m & … & 0 & 0 \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ 1 − m & 1 − m & … & 1 − m & 1 \end{matrix} ) .

We see that M ∈ SL_{k}(ℤ), the multiplicative group of k × k matrices with entries in ℤ and determinant +1.

We have

∑_{j=1}^{k} ε_{j}m^{k−j} = (m^{k−1}, m^{k−2}, …, 1) ( ε_{1} ; ⋮ ; ε_{k} )

= (m^{k−1}, m^{k−2}, …, 1)M ( p_{1} ; ⋮ ; p_{k} )

= (1, 1, …, 1) ( p_{1} ; ⋮ ; p_{k} )
= p_{1} + p_{2} + ⋯ + p_{k},

so that (1) is satisfied if and only if (6) is true. By (8), we have that (2) holds if and only if (7) holds. Hence (p_{1}, …, p_{k}) ∈ A_{k}(n) if and only if (ε_{1}, …, ε_{k}) ∈ B_{k}(n). Since M is invertible, it follows (with a slight abuse of notation) that

ψ : A_{k}(n) ⟶ B_{k}(n)  (9)

is invertible and, therefore, is a bijection.

In particular, we have

|A_{k}(n)| = |B_{k}(n)|,

which may be stated as follows.

Theorem 2.1. 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}.

Moreover,

|⋃_{i=1}^{k} A_{i}(n)| = |⋃_{i=1}^{k} B_{i}(n)| ,

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

|⋃_{k≥1} A_{k}(n)| = |⋃_{k≥1} B_{k}(n)| ,

which proves Theorem 1.1.

Furthermore, when (p_{1}, …, p_{k}) and (ε_{1}, …, ε_{k}) are related by (8), then (3) is satisfied if and only if ε_{2} ≥ 1, and Theorem 1.2 follows.

Using the interpretation of c(n) as the number of restricted m-ary partitions of n, we have, putting c(0) = 1,

F (q) = ∑_{n=0}^{∞} c(n)q^{n}

= 1 + ∑_{ε_{1}≥1} q^{ε_{1}} + ∑_{k=2}^{∞} ∑_{ε_{3},...,ε_{k}≥0^{ε_{1},ε_{2}≥1}} q^{ε_{1}m^{k−1}+ε_{2}m^{k−2}+···+ε_{k}}

= \frac{1}{1 − q} + ∑_{k=2}^{∞} \frac{q^{m^{k−1}}}{1 − q^{m^{k−1}}} · \frac{q^{m^{k−2}}}{1 − q^{m^{k−2}}} · \frac{1}{1 − q^{m^{k−3}}} ⋯ \frac{1}{1 − q} ,

and (4) follows.

3. Arithmetic properties of c(n)

In this section we use properties of the generating function

F (q) = ∑_{n=0}^{∞} c(n)q^{n}

to study c(n). The closed form (4) 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 (5), which we shall repeatedly use in the form

F (q) − 1 = \frac{1}{1 − q} F (q^{m}) − \frac{1}{1 − q^{m}} .  (10)

3.1. Statement of main result

We shall prove the following theorem from which Theorem 1.3 immediately follows.

Theorem 3.1. We have

∑_{n=1}^{∞} (c(mn) − c(n)) q^{n} = \frac{q}{1 − q} (F (q) − 1) ,  (11)

∑_{n=1}^{∞} (c(m^{2}n) − c(mn)) q^{n} = \frac{mq}{(1 − q)^{2}} (F (q) − 1) + \frac{(m − 1)q}{(1 − q)^{2}} ,  (12)

∑_{n=1}^{∞} (c(m^{3}n) − c(m^{2}n)) q^{n} = (− \frac{\frac{1}{2}(m^{3} − m^{2})q}{(1 − q)^{2}} + \frac{m^{3}q}{(1 − q)^{3}} ) (F (q) − 1)  (13)

+ (− \frac{\frac{1}{2}(m^{3} − 3m^{2} + 2m)q}{(1 − q)^{2}} + \frac{(m^{3} − m^{2})q}{(1 − q)^{3}} ) ,

and more generally for r ≥ 3,

2^{r−2} ∑_{n=1}^{∞} (c(m^{r+1}n) − c(m^{r}n)) q^{n}  (14)

= (∑_{i=1}^{r} \frac{μ_{r,i}q}{(1 − q)^{i+1}} ) (F (q) − 1) + (∑_{i=1}^{r} \frac{λ_{r,i}q}{(1 − q)^{i+1}} ) ,

where μ_{r,i} and λ_{r,i} are integers satisfying

μ_{r,i} ≡ λ_{r,i} ≡ 0 (mod m^{r−1+(i^{2}−i)/2}).  (15)

In Section 3.2 we state the necessary auxiliaries for the proof of Theorem 3.1, but postpone the technical details. In Section 3.3 we prove Theorem 3.1. In Section 3.4 we demonstrate the technical details necessary to prove the auxiliary results in Section 3.2.

3.2. Auxiliaries

The power series in this paper are elements of ℤ[[q]], the ring of formal power series in q with coefficients in ℤ. We define a ℤ-linear operator

U : ℤ[[q]] ⟶ ℤ[[q]]

by

U ∑_{n} a(n)q^{n} = ∑_{n} a(mn)q^{n}.

Notice that if f(q), g(q) ∈ ℤ[[q]], then

U (f(q)g(q^{m})) = (Uf(q)) g(q).  (16)

Let

h_{i} = h_{i}(q) = \frac{q}{(1 − q)^{i+1}}  for i ≥ 0.  (17)

Then

h_{i} = ∑_{n=1}^{∞} \binom{n + i − 1}{i}q^{n},  (18)

so that

Uh_{r} = ∑_{n=1}^{∞} \binom{mn + r − 1}{r}q^{n}.  (19)

Simple calculations show that

Uh_{0} = h_{0},  (20)
Uh_{1} = mh_{1},  (21)
Uh_{2} = −\frac{1}{2}m(m − 1)h_{1} + m^{2}h_{2}.

We shall recursively define functions H_{r} and L_{r}. The motivation for these definitions will become clear in the following section. First, let

H_{0} = h_{0} and H_{i+1} = U(\frac{1}{1 − q} H_{i}), i ≥ 0.  (22)

We find

H_{1} = mh_{1},  (23)
H_{2} = −\frac{1}{2}m^{2}(m − 1)h_{1} + m^{3}h_{2}.

We have similar results for each r ≥ 2, as shown by the following lemma.

Lemma 3.1. For r ≥ 2 there exist integers μ_{r,i} such that

2^{r−2}H_{r} = ∑_{i=1}^{r} μ_{r,i}h_{i},  (24)

where

μ_{r,i} ≡ 0 (mod m^{r−1+(i^{2}−i)/2}) for 1 ≤ i ≤ r.  (25)

Second, we define

L_{0} = 0 and L_{i+1} = H_{i+1} − (UH_{i})\frac{1}{1 − q} + UL_{i}, i ≥ 0.  (26)

Then

L_{1} = (m − 1)h_{1},
L_{2} = −\frac{1}{2}m(m − 1)(m − 2)h_{1} + m^{2}(m − 1)h_{2}.  (27)

Lemma 3.2. For r ≥ 2 there exist integers λ_{r,i} such that

2^{r−2}L_{r} = ∑_{i=1}^{r} λ_{r,i}h_{i},  (28)

where

λ_{r,i} ≡ 0 (mod m^{r−1+(i^{2}−i)/2}) for 1 ≤ i ≤ r.

3.3. Proof of Theorem 3.1

With the results of the previous section in hand, it is straightforward to prove Theorem 3.1. We start by applying the operator U to the functional equation (10). Using (16) 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} (F (q) − 1) ,

which is (11).

Using (10) we further obtain

UF (q) − F (q) = \frac{q}{1 − q} (\frac{1}{1 − q} F (q^{m}) − \frac{1}{1 − q^{m}} )

= h_{1}F (q^{m}) − h_{0} \frac{1}{1 − q^{m}} .

Application of U gives, by (20) and (21),

U^{2}F (q) − UF (q) = mh_{1}F (q) − h_{0} \frac{1}{1 − q}
= mh_{1} (F (q) − 1) + (m − 1)h_{1},

which proves (12). Repeating this process once more, we get (13).

More generally, we claim that

U^{r+1}F (q) − U^{r}F (q) = H_{r} (F (q) − 1) + L_{r} for r ≥ 0.  (29)

This follows by induction on r. The identity is true for r = 0. Suppose that it holds for some r ≥ 0. Then, by (10),

U^{r+1}F (q) − U^{r}F (q) = H_{r} (\frac{1}{1 − q} F (q^{m}) − \frac{1}{1 − q^{m}} ) + L_{r}

= (\frac{1}{1 − q} H_{r}) F (q^{m}) − H_{r} \frac{1}{1 − q^{m}} + L_{r}.

Application of U now gives, using (22), (16), and (26),

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} (F (q) − 1) + L_{r+1}.

This proves our claim.

For r ≥ 2, we multiply (29) by 2^{r−2}, and apply Lemma 3.1 to 2^{r−2}H_{r} and Lemma 3.2 to 2^{r−2}L_{r}. Then we get (14) with the congruences (15) satisfied. This completes the proof of Theorem 3.1.

3.4. Technical details

In this section we prove Lemmas 3.1 and 3.2. 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 \{\binom{n+i−1}{i} | i = 0, 1, …, r\}. Moreover, the subgroup consisting of those polynomials which also map 0 to 0, is free with basis \{\binom{n+i−1}{i} | i = 1, …, r\}. In particular, the following lemma holds.

Lemma 3.3. For each positive integer r there exist unique integers α_{r,i}, such that for all n,

\binom{mn + r − 1}{r} = ∑_{i=1}^{r} α_{r,i}\binom{n + i − 1}{i}.  (30)

Comparing the coefficients of n^{r} in (30), we get

α_{r,r} = m^{r},  (31)

and comparing the coefficients of n^{r−1}, we get

α_{r,r−1} = −\frac{1}{2}(r − 1)(m − 1)m^{r−1}.  (32)

It follows from Lemma 3.3, (18), and (19) that

Uh_{r} = ∑_{i=1}^{r} α_{r,i}h_{i} for r ≥ 1.  (33)

We now turn to Lemma 3.1. We prove a slightly more precise result, which we shall need in our proof of Lemma 3.2. Notice that the set {h_{0}, h_{1}, …} is linearly independent over ℤ (and over ℂ), so the integers κ_{r,i} in Lemma 3.4 below are uniquely determined by r and i (and m). The same remark applies, of course, to other linear combinations of the h_{i}.

Lemma 3.4. For 1 ≤ i ≤ r there exist integers κ_{r,i} such that

H_{r} = ∑_{i=1}^{r} κ_{r,i}h_{i},  (34)

where

2^{r−i}κ_{r,i} ≡ 0 (mod m^{r+(i^{2}−i)/2}).  (35)

Remark. Let r ≥ 2. Notice that (35) for i = 1 implies 2^{r−2}κ_{r,1} ≡ 0 (mod m^{r−1}). Thus, by setting μ_{r,i} = 2^{r−2}κ_{r,i}, Lemma 3.4 gives us Lemma 3.1.

Note. In the following we set κ_{r,i} = 0 if i = 0 or if i > r. These values of κ trivially satisfy (35).

Proof. We use induction on r. By (23), the lemma is true for r = 1. Suppose that for some r > 1, we have

H_{r−1} = ∑_{i=1}^{r−1} κ_{r−1,i}h_{i},  (36)

where the κ_{r−1,i} are integers satisfying

2^{r−1−i}κ_{r−1,i} ≡ 0 (mod m^{r−1+(i^{2}−i)/2}),  i = 1, 2, …, r − 1.  (37)

Then, by (22), (36), and (17),

H_{r} = U (\frac{1}{1 − q} H_{r−1}) = U ∑_{i=1}^{r−1} κ_{r−1,i}h_{i+1} = ∑_{j=1}^{r} κ_{r−1,j−1}Uh_{j},

and, by (33),

H_{r} = ∑_{j=1}^{r} κ_{r−1,j−1} ∑_{i=1}^{j} α_{j,i}h_{i} = ∑_{i=1}^{r} ∑_{j=i}^{r} α_{j,i}κ_{r−1,j−1}h_{i},

so that (34) holds with

κ_{r,i} = ∑_{j=i}^{r} α_{j,i}κ_{r−1,j−1},

and all the κ_{r,i} are integers.

Moreover, for 1 ≤ i ≤ r we have

2^{r−i}κ_{r,i} = ∑_{j=i}^{r} 2^{j−i}α_{j,i} · 2^{r−j}κ_{r−1,j−1}.  (38)

By (37),

2^{r−j}κ_{r−1,j−1} ≡ 0 (mod m^{r+(i^{2}−i)/2}) for j ≥ i + 2,

so that, by (38), (31), (32), and (37),

2^{r−i}κ_{r,i} ≡ α_{i,i} · 2^{r−i}κ_{r−1,i−1} + 2α_{i+1,i} · 2^{r−1−i}κ_{r−1,i}
≡ m^{i} · 2^{r−i}κ_{r−1,i−1} − i(m − 1)m^{i} · 2^{r−1−i}κ_{r−1,i}
≡ 0 (mod m^{r+(i^{2}−i)/2}).

Incidentally, we have κ_{r,r} = m^{(r^{2}+r)/2}.

Next we consider the term UH_{r} appearing in the definition (26). We have, by (23) and (21),

UH_{1} = m^{2}h_{1}.

Similarly we find

UH_{2} = −\frac{1}{2}m^{3}(m − 1)(m + 1)h_{1} + m^{5}h_{2}.

Lemma 3.5. For 1 ≤ i ≤ r there exist integers ν_{r,i} such that

2^{r−1}UH_{r} = ∑_{i=1}^{r} ν_{r,i}h_{i},  (39)

where

ν_{r,i} ≡ 0 (mod m^{r+(i^{2}+i)/2}).  (40)

Proof. For r ≥ 1, we have by Lemma 3.4 and (33),

2^{r−1}UH_{r} = 2^{r−1} ∑_{j=1}^{r} κ_{r,j}Uh_{j} = 2^{r−1} ∑_{j=1}^{r} κ_{r,j} ∑_{i=1}^{j} α_{j,i}h_{i}

= 2^{r−1} ∑_{i=1}^{r} ∑_{j=i}^{r} α_{j,i}κ_{r,j}h_{i},

so that (39) is satisfied by setting

ν_{r,i} = 2^{r−1} ∑_{j=i}^{r} α_{j,i}κ_{r,j}.

Then all the ν_{r,i} are integers.

Moreover, by (35),

2^{r−1}κ_{r,j} ≡ 0 (mod m^{r+(i^{2}+i)/2}) for j ≥ i + 1.

Hence, using (31) and (35),

ν_{r,i} ≡ 2^{r−1}α_{i,i}κ_{r,i} ≡ m^{i} · 2^{r−1}κ_{r,i} ≡ 0 (mod m^{r+(i^{2}+i)/2}).

Finally, we prove Lemma 3.2. Again we use induction on r. By (27), the lemma is true for r = 2. Suppose that for some r ≥ 3 there are integers λ_{r−1,j} such that

2^{r−3}L_{r−1} = ∑_{j=1}^{r−1} λ_{r−1,j}h_{j},

where

λ_{r−1,j} ≡ 0 (mod m^{r−2+(j^{2}−j)/2}).  (41)

Then

U (2^{r−3}L_{r−1}) = ∑_{j=1}^{r−1} λ_{r−1,j}Uh_{j} = ∑_{j=1}^{r−1} λ_{r−1,j} ∑_{i=1}^{j} α_{j,i}h_{i}

= ∑_{i=1}^{r−1} ∑_{j=i}^{r−1} α_{j,i}λ_{r−1,j}h_{i}.

Hence,

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} by (26)

= ∑_{i=1}^{r} μ_{r,i}h_{i} − ∑_{j=1}^{r−1} ν_{r−1,j}h_{j+1} + 2^{r−2}UL_{r−1} by (24) and (39)

= ∑_{i=1}^{r} μ_{r,i}h_{i} − ∑_{i=2}^{r} ν_{r−1,i−1}h_{i} + 2 ∑_{i=1}^{r−1} ∑_{j=i}^{r−1} α_{j,i}λ_{r−1,j}h_{i}.

Thus, (28) holds with

λ_{r,i} = μ_{r,i} − ν_{r−1,i−1} + 2 ∑_{j=i}^{r−1} α_{j,i}λ_{r−1,j},  (42)

where ν_{r−1,0} = 0. In particular we have, by (25) and (40),

λ_{r,r} = μ_{r,r} − ν_{r−1,r−1} ≡ 0 (mod m^{r−1+(r^{2}−r)/2}),

and, for 1 ≤ i ≤ r − 1,

λ_{r−1,j} ≡ 0 (mod m^{r−1+(i^{2}−i)/2}) for j ≥ i + 1.

Hence, using (42), (25), (40), (31), and (41), we have

λ_{r,i} = μ_{r,i} − ν_{r−1,i−1} + 2α_{i,i}λ_{r−1,i} ≡ 0 (mod m^{r−1+(i^{2}−i)/2}).

This completes the proof of Lemma 3.2.

As in the case of Lemma 3.1 and Lemma 3.4, we can state a more precise form of Lemma 3.2. While we used the more precise Lemma 3.4 in the proof of Lemma 3.5 on our way towards the proof of Lemma 3.2, there is no such reason to sharpen Lemma 3.2.

4. Closing remarks

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 (9), we now have the means to prove an infinite family of similar partition results. For, if instead of (3) we restrict (2) in another way, we get a different type of restricted m-non-squashing partition.

Then, by (9), 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 (4) above). If a functional equation relating G(q) and G(q^{m}) (similar to (5) 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.

5. Acknowledgments

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

References

[1] M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australas. J. Combin. 30 (2004), 193–196.

[2] Ø. J. Rødseth and J. A. Sellers, On m-ary partition function congruences: A fresh look at a past problem, J. Number Theory 87 (2001), 270–281.

[3] Ø. J. Rødseth, J. A. Sellers, and K. M. Courtright, Arithmetic properties of nonsquashing partitions into distinct parts, Ann. Comb. 8 (2004), 347–353.

[4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

   at http://www.research.att.com/∼njas/sequences/, 2005.

[5] N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math. 294 (2005), 259–274.

2000 Mathematics Subject Classification: Primary 11P83; Secondary 05A17, 11P81. Keywords: partitions, m-non-squashing partitions, m-ary partitions, stacking boxes, congruences

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

Received April 20 2005; revised version received October 23 2005. Published in Journal of Integer Sequences, October 24 2005.

Return to Journal of Integer Sequences home page.