Partitions Excluding Specific Polygonal Numbers As Parts

James A. Sellers Department of Mathematics The Pennsylvania State University University Park, PA 16802

                     sellersj@math.psu.edu

Abstract

Many results appear in the literature involving partitions of an integer n into parts which are certain polygonal numbers (such as triangular numbers or squares). However, few results appear which deal with partition functions that exclude specific polygonal numbers as parts. We consider such functions in this note, and prove two families of partition identities.

1 Introduction

A partition λ of the nonnegative integer n is a sequence of nonnegative integers λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} with λ_{1} + λ_{2} + ⋯ + λ_{r} = n. Each value λ_{i}, 1 ≤ i ≤ r, is called a part of the partition. In this note, we consider partitions of n with parts related to k-gonal numbers for some fixed integer k ≥ 3.

Various works have appeared involving partitions into polygonal parts. For example, M. D. Hirschhorn and the author have written a number of papers on partitions into a specified number of triangular numbers or squares [3]–[5]. Also, Andrews [2, Theorem 4.1] considers partitions into an unlimited number of triangular numbers. (Several sequences related to such partitions appear in Sloane’s Online Encyclopedia of Integer Sequences [6], including \underline{A001156}, \underline{A002635}, \underline{A002636}, and \underline{A007294}.)

In contrast, few results appear in the literature in which polygonal numbers are excluded as parts. Andrews [1, Corollary 8.5] highlights one such instance when he considers the number of partitions of n with no square parts. Interestingly enough, Sloane [6] recently published this sequence of values (\underline{A087153}) in August 2003.

Our goal here is two-fold. First, we consider Andrews’ result above and extend it to all 2k-gons for k ≥ 2. Afterwards, we prove a similar result for 2k + 1-gons.

Some brief comments on polygonal numbers, or k-gons, are in order. For a fixed integer k ≥ 3, the n^{th} k-gonal number is given by

(\frac{k − 2}{2}) n^{2} − (\frac{k − 4}{2}) n.

So, for example, the 3-gonal numbers, or triangular numbers (\underline{A000217}), are given by

(\frac{3 − 2}{2}) n^{2} − (\frac{3 − 4}{2}) n = \frac{n^{2}}{2} + \frac{n}{2}

while the 4-gons, or squares (\underline{A000290}), are given by

(\frac{4 − 2}{2}) n^{2} − (\frac{4 − 4}{2}) n = n^{2}.

2 Partitions Excluding 2k–gons as Parts

We now state Andrews’ result [1, Corollary 8.5].

Theorem 2.1. Let p_{1}(n) be the number of partitions of n wherein each part i appears at most i − 1 times and let p_{2}(n) be the number of partitions of n with no square parts. Then, for all nonnegative integers n, p_{1}(n) = p_{2}(n).

Before proving this result, which involves a straightforward generating function argument, we consider one example to confirm our result. The partitions of the integer 6 (with no restrictions on the parts) are given by

6, 5 + 1, 4 + 2, 4 + 1 + 1, 3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1, 2 + 2 + 2,
2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1, and 1 + 1 + 1 + 1 + 1 + 1.

Note that those partitions above with no square parts are

6, 3 + 3, and 2 + 2 + 2,

while those wherein each part i appears at most i − 1 times are

6, 4 + 2, and 3 + 3.

Thus, p_{1}(6) = p_{2}(6) = 3.

We now turn to a generating function proof of Theorem 2.1.

Proof. First, it is clear that

∑_{n=0}^{∞} p_{2}(n)q^{n} = ∏_{i=1}^{∞} \frac{1 − q^{i^{2}}}{1 − q^{i}}

= \frac{1 − q^{1}}{1 − q^{1}} · \frac{1 − q^{4}}{1 − q^{2}} · \frac{1 − q^{9}}{1 − q^{3}} · \frac{1 − q^{16}}{1 − q^{4}} ⋯

Next, we note that each of the ratios in the product above can be rewritten as a finite geometric series thanks to the following fact:

\frac{1 − x^{aj}}{1 − x^{a}} = 1 + x^{a} + x^{2a} + ⋯ + x^{(j−1)a}  (1)

Hence, we see that ∑_{n=0}^{∞} p_{2}(n)q^{n} can be written as

(1)(1 + q^{2})(1 + q^{3} + q^{6})(1 + q^{4} + q^{8} + q^{12})(1 + q^{5} + q^{10} + q^{15} + q^{20}) ⋯

or

∏_{i=1}^{∞}(1 + q^{i} + q^{2i} + ⋯ + q^{i(i−1)}).

This is the generating function for p_{1}(n), which yields the result.

What fundamentally drives the proof above is the fact that i | i^{2} for each positive integer i, as this allows for the use of (1) in our proof. This insight allows us to extend Theorem 2.1 in a natural fashion.

Theorem 2.2. Let k ≥ 2 be a fixed integer. Let p_{3}(n, k) be the number of partitions of n wherein each part i appears at most (k − 1)(i − 1) times and let p_{4}(n, k) be the number of partitions of n wherein no 2k–gons can be used as parts. Then, for all nonnegative integers n, p_{3}(n, k) = p_{4}(n, k).

Note that Theorem 2.1 is just a corollary of Theorem 2.2 upon setting k = 2.

Proof. As above, the proof we provide here is simply a generating function manipulation. From (1) we see that

\frac{1 − q^{(^{\frac{2k−2}{2}})i^{2}−(\frac{2k−4}{2})i}}{1 − q^{i}} = 1 + q^{i} + q^{2i} + ⋯ + q^{i[(k−1)i−(k−2)−1]}.

Hence,

∑_{n=0}^{∞} p_{4}(n, k)q^{n} = ∏_{i=1}^{∞} \frac{1 − q^{(^{\frac{2k−2}{2}})i^{2}−(\frac{2k−4}{2})i}}{1 − q^{i}}

= ∏_{i=1}^{∞} (1 + q^{i} + q^{2i} + ⋯ + q^{i[(k−1)i−(k−2)−1]})

= ∏_{i=1}^{∞} (1 + q^{i} + q^{2i} + ⋯ + q^{i(k−1)(i−1)}) after simplification.

This last infinite product is, by definition, the generating function for p_{3}(n, k), which proves the theorem.

3 Partitions Excluding 2k + 1–gons as Parts

One may naturally ask whether a similar result exists for partitions of n which contain no 2k + 1–gons as parts. Unfortunately, a perfect analogue does not exist, because it is not the case that i divides

(\frac{2k + 1 − 2}{2}) i^{2} − (\frac{2k + 1 − 4}{2}) i

for all positive integers i. However, it is the case that such divisibility occurs when i is odd. Indeed,

(\frac{2k + 1 − 2}{2}) (2j − 1)^{2} − (\frac{2k + 1 − 4}{2}) (2j − 1)

= (2j − 1) [(\frac{2k − 1}{2}) (2j − 1) − (\frac{2k − 3}{2})]
= (2j − 1)(j(2k − 1) − (2k − 2))

so that 2j − 1 divides the (2j − 1)st 2k + 1–gon. This observation leads to the following result.

Theorem 3.1. Let p_{5}(n, k) be the number of partitions of n wherein the part 2i − 1 (i ≥ 1) appears at most (2k − 1)(i − 1) times (and the frequency of the even parts is unbounded). Let p_{6}(n, k) be the number of partitions of n wherein no odd–subscripted 2k + 1–gons can be used as parts. Then, for all nonnegative integers n, p_{5}(n, k) = p_{6}(n, k).

An example may be beneficial before proving Theorem 3.1. We consider the case where n = 10 and k = 1. The partitions enumerated by p_{5}(10, 1) are those wherein no 1s and at most one 3, two 5s, and three 7s can appear as parts (and even parts can appear with no restrictions on their number of occurrences). These partitions are as follows:

10, 8 + 2, 7 + 3, 6 + 4, 6 + 2 + 2, 5 + 5,
5 + 3 + 2, 4 + 4 + 2, 4 + 2 + 2 + 2, and 2 + 2 + 2 + 2 + 2

On the other hand, those partitions enumerated by p_{6}(10, 1) are those in which odd–subscripted triangular numbers are not allowed as parts. (These unallowed parts would be 1, 6, 15, ….) These partitions are as follows:

10, 8 + 2, 7 + 3, 5 + 5, 5 + 3 + 2, 4 + 4 + 2,
4 + 3 + 3, 4 + 2 + 2 + 2, 3 + 3 + 2 + 2, and 2 + 2 + 2 + 2 + 2

Hence, p_{5}(10, 1) = p_{6}(10, 1).

Proof. It is clear that

∑_{n=0}^{∞} p_{6}(n, k)q^{n} = ∏_{i=1}^{∞} (\frac{1 − q^{(^{\frac{2k+1−2}{2}})(2i−1)^{2}−(\frac{2k+1−4}{2})(2i−1)}}{1 − q^{i}} ) .

This can be manipulated to yield

∏_{i=1}^{∞} (\frac{1 − q^{(2i−1)[(\frac{2k+1−2}{2})(2i−1)−(\frac{2k+1−4}{2})]}}{(1 − q^{2i−1})(1 − q^{2i})} )

= ∏_{i=1}^{∞} \frac{1}{(1 − q^{2i})} · (1 + q^{2i−1} + q^{(2i−1)2} + ⋯ + q^{(2i−1)(2ik−i−2k+2−1)})

= ∏_{i=1}^{∞} \frac{1}{(1 − q^{2i})} · (1 + q^{2i−1} + q^{(2i−1)2} + ⋯ + q^{(2i−1)(2k−1)(i−1))}) .

This last infinite product is the generating function for p_{5}(n, k), which completes the proof of Theorem 3.1.

4 Closing Thoughts

Several thoughts are fitting as we close. First, for those dissatisfied with the concise generating function proofs given above for Theorems 2.1, 2.2, and 3.1, we offer a combinatorial proof of Theorem 2.1 which is generalizable to proofs of Theorems 2.2 and 3.1.

Combinatorial Proof of Theorem 2.1. We provide a bijection between the partitions counted by p_{1}(n) and those counted by p_{2}(n). The bijection is described as follows. Let λ be a partition counted by p_{2}(n), and assume that the part λ_{i} appears in λ exactly ℓ_{i} times. If ℓ_{i} < λ_{i}, then we map these ℓ_{i} occurrences of λ_{i} to themselves. Next, we consider those parts λ_{i} such that ℓ_{i} ≥ λ_{i}. This means that we can sum many of these copies of λ_{i} to obtain at least one copy of λ_{i}^{2}. We build as many copies of λ_{i}^{2} as possible in this fashion. If there are some “leftover” copies of λ_{i} which could not be used to build an additional copy of λ_{i}^{2}, then these copies of λ_{i} are simply mapped to themselves. Now we iterate the process. If there are fewer than λ_{i}^{2} copies of λ_{i}^{2} at this stage, then we map them to themselves. However, if there are at least λ_{i}^{2} copies of λ_{i}^{2}, then we sum them to obtain as many copies of λ_{i}^{4} as possible. We continue in this iterative fashion until it is no longer possible to create additional squares of the form λ_{i}^{2^{j}}. The result is the corresponding partition counted by p_{1}(n).

The inverse of this function is straightforward. Namely, the nonsquare parts in the partition λ^{∗} counted by p_{1}(n) are mapped to themselves. Then each of the square parts in λ^{∗} are reduced (via square roots) in an iterative fashion until no squares are present. The result is the original partition counted by p_{2}(n).

An example of this bijection may prove useful. First, note the following partitions of the integer 36:

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3

6 + 6 + 6 + 6 + 6 + 6

All three of these partitions are counted by p_{2}(36). Their corresponding partitions via the above bijection are

16 + 16 + 4, 9 + 9 + 9 + 9, and 36

respectively. Moreover, it is clear from the proof given above that these three partitions counted by p_{1}(36) are mapped back to the appropriate partitions via the inverse map described.

As a more complete example, we provide a list of some of the partitions counted by p_{1}(18) and p_{2}(18). Note that those partitions counted by p_{1}(18) which do not contain any square parts are simply mapped to themselves, so these partitions have been omitted from this table. In the left–hand column below, we present the 22 partitions counted by p_{1}(18) which contain at least one square part, and we write these in lexicographical order. In the right–hand column we present the corresponding partitions counted by p_{2}(18) as generated by the bijection described above.

16 + 2 ⟷ 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
14 + 4 ⟷ 14 + 2 + 2
12 + 4 + 2 ⟷ 12 + 2 + 2 + 2
11 + 4 + 3 ⟷ 11 + 3 + 2 + 2
10 + 4 + 4 ⟷ 10 + 2 + 2 + 2 + 2
9 + 9 ⟷ 3 + 3 + 3 + 3 + 3 + 3
9 + 7 + 2 ⟷ 7 + 3 + 3 + 3 + 2
9 + 6 + 3 ⟷ 6 + 3 + 3 + 3 + 3
9 + 5 + 4 ⟷ 5 + 3 + 3 + 3 + 2 + 2
9 + 4 + 3 + 2 ⟷ 3 + 3 + 3 + 3 + 2 + 2 + 2
8 + 6 + 4 ⟷ 8 + 6 + 2 + 2
8 + 4 + 4 + 2 ⟷ 8 + 2 + 2 + 2 + 2 + 2
8 + 4 + 3 + 3 ⟷ 8 + 3 + 3 + 2 + 2
7 + 7 + 4 ⟷ 7 + 7 + 2 + 2
7 + 5 + 4 + 2 ⟷ 7 + 5 + 2 + 2 + 2
7 + 4 + 4 + 3 ⟷ 7 + 3 + 2 + 2 + 2 + 2
6 + 6 + 4 + 2 ⟷ 6 + 6 + 2 + 2 + 2
6 + 5 + 4 + 3 ⟷ 6 + 5 + 3 + 2 + 2
6 + 4 + 4 + 4 ⟷ 6 + 2 + 2 + 2 + 2 + 2 + 2
6 + 4 + 3 + 3 + 2 ⟷ 6 + 3 + 3 + 2 + 2 + 2
5 + 5 + 4 + 4 ⟷ 5 + 5 + 2 + 2 + 2 + 2
5 + 4 + 4 + 3 + 2 ⟷ 5 + 3 + 2 + 2 + 2 + 2 + 2

We close by noting that Andrews treats Theorem 2.1 as a special case of a broader theorem on partition ideals of order one. Indeed, all the theorems in this paper fall into this genre, so that they can be proven with his technique as well.

5 Acknowledgements

The author gratefully acknowledges the referee’s insightful comments with regard to the combinatorial proof of Theorem 2.1.

References

[1] G.E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.

[2] G. E. Andrews, MacMahon’s partition analysis. II. Fundamental theorems, Ann. Comb. 4 (2000), no. 3-4, 327–338.

[3] M. D. Hirschhorn and J. A. Sellers, Some relations for partitions into four squares, in Proceedings of the International Workshop on Special Functions, Asymptotics, Harmonic Analysis, and Mathematical Physics, World Scientific, 2000, pp. 118-124.

[4] M. D. Hirschhorn and J. A. Sellers, On a problem of Lehmer on partitions into squares, to appear in Ramanujan J.

[5] M. D. Hirschhorn and J. A. Sellers, Partitions into three triangular numbers, to appear in Australas. J. Combin.

[6] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: 05A17 Keywords: partition, polygonal number, generating function, geometric series.

(Concerned with sequences \underline{A000217}, \underline{A000290}, \underline{A001156}, \underline{A002635}, \underline{A002636}, \underline{A007294}, and \underline{A087153}.)

Received September 13 2003; revised version received May 10 2004. Published in Journal of Integer Sequences June 8 2004.

Return to Journal of Integer Sequences home page.