# Bijective proofs of partition identities of MacMahon, Andrews, and Subbarao.

1 Introduction

In his classic work Combinatory Analysis, MacMahon [8, page 54] proves the following theorem:

Theorem 1.1 The number of partitions of n wherein no part appears with multiplicity one equals the number of partitions of n where all parts must be even or congruent to 3 (mod 6).

MacMahon utilizes a generating function argument to prove Theorem 1.1. (Indeed, Berndt [4, page 5] mentions MacMahon's identity as a straightforward exercise in generating function manipulations.)

In 1967, half a century after MacMahon published this result, Andrews [1] stated and proved the following natural generalization of Theorem 1.1:

Theorem 1.2 Let r be a positive integer. The number of partitions of n in which any part with odd multiplicity must appear at least 2r +1 times equals the number of partitions of n where all parts must be even or congruent to 2r + 1 (mod 4r + 2).

As with MacMahon, Andrews' proof is a straightforward generating function argument. (We note in passing that MacMahon's result has been generalized in directions other than Theorem 1.2; in particular, see the works of Holroyd [6] and Yee [10].)

In 1971, Subbarao [9] stated that Andrews' theorem above "is itself a special case of the following result":

Theorem 1.3 Let k [greater than or equal to] 2 be an integer and let t be a positive integer which is not a multiple of k. The number of partitions of n in which the multiplicity of each part is either congruent to 0 (mod k) or else at least t and congruent to t (mod k) equals the number of partitions of n where all parts must be congruent to 0 (mod k) or congruent to t (mod 2t).

Subbarao goes on to say, "Andrews' result corresponds to the choice k = 2, t = 2r + 1. The proof of this is analogous to that of Andrews' and is therefore omitted." Interesting enough, for many choices of k and t, the right-hand side of Subbarao's result is not naturally interpreted as a statement about (ordinary) integer partitions. Rather, one must invoke the idea of colored partitions or something similar. We will discuss this further below.

Besides Theorem 1.3, Subbarao supplied another generalization in that same paper [9]. Instead of relaxing the constraints on the modulus (k and t in Theorem 1.3), he considered a "finite version" of Theorem 1.2. Namely, he gave the following:

Theorem 1.4 Let m > 1, r [greater than or equal to] 0 be integers, and let [C.sub.m,r] (n) be the number of partitions of n such that all even multiplicities of the parts are less than 2m, and all odd multiplicities are at least 2r +1 and at most 2(m + r) - 1. Let [D.sub.m,r] (n) be the number of partitions of n into parts which are either odd and congruent to 2r + 1 (mod 4r + 2), or even and not congruent to 0 (mod 2m). Then [C.sub.m,r] (n) = [D.sub.m,r] (n).

Note that when we choose m sufficiently large, say m = n, then the three conditions that involve m become redundant, and we are back to exactly Theorem 1.2.

While generating function proofs such as those supplied by MacMahon and Andrews are of great value, bijective proofs of such integer partition identities are also quite beneficial. In 2007, Andrews, Eriksson, Petrov, and Romik [3] appear to have provided the first bijective proof of MacMahon's Theorem (Theorem 1.1). However, their bijection is quite different in nature than the one we give below and, more importantly, does not seem to generalize naturally to a proof of either of Subbarao's Theorems given above. With this in mind, our first goal in this note is to provide transparent bijections between the partitions enumerated in Theorems 1.1 and 1.2. From there, we will discuss Subbarao's two results in more detail and then extend our bijective proof of Theorem 1.2 to obtain natural bijective proofs of Theorem 1.3 and Theorem 1.4.

2 A Unified Set of Bijective Proofs

We begin this section by proving Theorem 1.1 bijectively. We outline this proof in great detail because this bijection will serve as the foundation for the remaining bijections in the paper.

Proof (of Theorem 1.1): Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

be a partition of n counted by the left-hand side of Theorem 1.1. Thus, we know that each [m.sub.i], the multiplicity of the part [p.sub.i] in our given partition, is either even or is odd and at least three. We now consider two cases, depending on the parity of [m.sub.i] for each i, in order to define our bijection.

* [m.sub.i] is even: In this case, we simply map the parts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

to the parts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Each of these new parts is even as is necessary according to the right-hand side of Theorem 1.1.

* [m.sub.i] is odd: Given that [m.sub.i] is odd, we know that [m.sub.i] [greater than or equal to] 3. Thus, we split off three copies of the part [p.sub.i] and combine any of the remaining pairs of occurrences of [p.sub.i] (if [m.sub.i] > 3) as was done in the previous step of the algorithm. This now leaves us with three copies of each of the parts [p.sub.i] which had odd multiplicity in the original partition. We now take one copy of each such part and realize that these define a subpartition into distinct parts. We then use any of the well-known bijections for converting distinct-part partitions into odd-part partitions (thanks to Euler's classic result) to convert the parts of this distinct-part subpartition into a partition into odd parts. For example, following [2], we can take this subpartition into distinct parts, and keep splitting all the even parts (if any) into two equal halves until there are no more even parts left and we get a subpartition into purely odd parts. Finally, in order to get back to the weight of n which we need, we multiply each of the parts in this odd-part subpartition by 3. (Each of these parts will then be congruent to 3 modulo 6.)

The reverse map should be clear; one simply cuts each even part counted on the right-hand side into two parts of half the size, and reverses the map above for those parts which are congruent to 3 modulo 6. Via the forward map described above, if we begin with

5 + 5 + 5 + 5 + 5 + 5 + 5 + 4 + 4 + 4 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1

which is a partition of n = 60 counted by the left-hand side of Theorem 1.1. We will end up with the new partition

15 + 10 + 10 + 4 + 4 + 3 + 3 + 3 + 3 + 3 + 2.

This is our partition of n = 60 which is enumerated by the right-hand side of Theorem 1.1. The reverse map should send us back to the partition we begin with. A step by step breakdown of this example can be found at the full version of this note, and the readers are encouraged to work out their own examples as well.

For completeness' sake, we also provide the proof of Theorem 1.2 in the full version of this note. This is a very straightforward matter given the bijective proof of Theorem 1.1 provided above, so it has been omitted here.

First off, we take the liberty of restating Subbarao's Theorem with changes needed to clarify the case when a part is both congruent to 0 (mod k) and congruent to t (mod 2t). (This may happen if no further restrictions are placed on k and l.) We then provide a bijective proof that is quite similar to what we have seen in the previous two theorems.

Theorem 2.1 Let k [greater than or equal to] 2 be an integer and let t be a positive integer which is not a multiple of k. The number of partitions of n in which the multiplicity of each part is either congruent to 0 (mod k) or else at least l and congruent to l (mod k) equals the number of partitions of n into parts with two colors, say blue and red,, where all parts in blue must be congruent to 0 (mod k) while all parts in red must be congruent to l (mod 2t).

Proof: The bijection is essentially the same as we see in the proof of Theorems 1.1 and 1.2; we only need to specify when and how we should color the parts going from the left-hand side of Theorem 2.1 (uncolored parts) to the right-hand side (colored parts). Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

be a partition of n counted by the left-hand side of Theorem 2.1. Thus, we know that each [m.sub.i], the multiplicity of the part [p.sub.i] in our given partition, is either congruent to 0 (mod k) or else at least l and congruent to l (mod k). We now consider two cases, depending on the divisibility of [m.sub.i] by k for each i, in order to define our bijection.

* [m.sub.i] is divisible by k: In this case, we simply map the parts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

to the parts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

And we color these new parts blue. Each of these new blue parts is congruent to 0 (mod k) as is necessary according to the right-hand side of Theorem 2.1.

* [m.sub.i] is not divisible by k: Given that [m.sub.i] is not divisible by k, we know that [m.sub.i] [greater than or equal to] l and [m.sub.i] = t (mod k). Thus, we split off l copies of the part [p.sub.i] and combine any of the remaining k-tuples of occurrences of [p.sub.i] (if mi > t) as was done in the previous step of the algorithm, and we should also color them blue. This now leaves us with l copies of each of the parts [p.sub.i]. We now take one copy of each such part and realize that these define a subpartition into distinct parts. We then use A-E conversion as above to convert the parts of this distinct-part subpartition into a partition into odd parts. Finally, in order to get back to the weight of n which we need, we multiply each of the parts in this odd-part subpartition by l and color them red. (Each of these red parts will then be congruent to l modulo 2t.)

* We also provide an example in the full version to demonstrate the above. But we choose to omit it here in this extended abstract.

We close this section by explaining how to prove Theorem 1.4 by making some necessary changes to our original bijection.

We start with a partition enumerated by [C.sub.m,r] (n). If the multiplicity of some part is odd, say [m.sub.i] for part [p.sub.i] is odd, then we know [m.sub.i] [greater than or equal to] 2r +1. We peel off 2r + 1 copies of the part [p.sub.i], then we convert all these parts (each has 2r + 1 copies) into a subpartition with parts odd and congruent to 2r + 1 (mod 4r + 2), using A-E conversion we have seen in the proofs of the previous theorems. After that, the remaining parts in the original partition will have even multiplicity [m.sub.j] with 2 [less than or equal to] [m.sub.j] [less than or equal to] 2m - 2. Now we convert these parts into even parts not congruent to 0 (mod 2m), so besides pairing the parts to make the new parts even, we must also factor out all the powers of m which are present. Thus, we map the parts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

to the parts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [[alpha].sub.j] = [ord.sub.m] ([p.sub.j]) := max{[alpha] [member of] N [absolute value of [m.sup.[alpha]]] [p.sub.j]}. Note that 1 [less than or equal to] [m.sub.j]/2 [less than or equal to] m - 1, so the reverse map is well defined as a result of the uniqueness of the m-ary representation of an integer.

We illustrate this new bijection with an example for m = 3, r = 2. We consider the following partition enumerated by [C.sub.3,2] (389):

20 + 20 + 20 + 20 + 20 + 20 + 20 + 16 + 16 + 15 + 15 + 15 + 15 + 15 + 15 + 15 + 15 + 15 + 7 + 7 + 7 + 7 + 7 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 3 + 3 + 3 + 3

We first peel off 2r + 1 = 5 copies of parts with odd multiplicity, namely parts 20, 15, 7 and 5, take one copy of each to get the distinct-part partition 20 + 15 + 7 + 5, and trigger the A-E conversion to get

20 + 15 + 7 + 5 [right arrow] 15 + 10 + 10 + 7 + 5 [right arrow] 15 + 7 + 5 + 5 + 5 + 5 + 5.

We now multiply by 5 to get the subpartition with parts odd and congruent to 5 (mod 10):

75 + 35 + 25 + 25 + 25 + 25 + 25. (1)

Next we proceed to convert the remaining parts in the original partition:

20 + 20 [right arrow] 40; 16 + 16 [right arrow] 32; 5 + 5 [right arrow] 10; 15 + 15 + 15 + 15 [right arrow] 10 + 10 + 10 + 10 + 10 + 10; 3 + 3 + 3 + 3 [right arrow] 2 + 2 + 2 + 2 + 2 + 2. (2)

Note that the total multiplicity for 10 is 6 + 1 = 7, where 6 + 1 = 2 * 3+1 is the ternary representation of 7, so the reverse map is clear. The resulting partition is obtained by combining all the parts from (1) and (2):

75 + 40 + 35 + 32 + 25 + 25 + 25 + 25 + 25 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 2 + 2 + 2 + 2 + 2 + 2,

which is enumerated by [D.sub.3,2] (389).

3 Concluding Remarks

We close with two remarks. First, it is the case that three proofs of Theorem 1.4 exist in the literature: Subbarao's original generating function proof [9], Gupta's bijective proof [5], and another bijective proof published quite recently by Kanna, Dharmendra, Sridhara, and Kumar [7]. Even so, it is important to note that none of these authors treat all four of the theorems above uniformly as we have done using only splitting and pairing as the main conversion method. This much desired uniformity is also the main reason for our choice of A-E conversion to accomplish the distinct-odd transition over other options like Sylvester's bijection as seen in [5].

Second, with our method, at least one further generalization is easily within reach. In essence, this generalization is a fusion of Theorem 1.4 and Theorem 2.1. We state it here without proof.

Theorem 3.1 Let k [greater than or equal to] 2, m [greater than or equal to] 2 be two integers and let t be a positive integer which is not a multiple of k. Let [E.sub.m,l,k] (n) be the number of partitions of n such that the multiplicity of each part is either congruent to 0 (mod k) and less than km or else congruent to l (mod k) and at least l and at most l+k(m - 1). Let [F.sub.m,l,k(n)] be the number of partitions of n into parts with two colors, say blue and red, where all parts in blue must be congruent to 0 (mod k) but not congruent to 0 (mod km) while all parts in red must be congruent to l (mod 2l). Then [E.sub.m,l,k](n) = [F.sub.m,l,k](n).

Acknowledgements

The authors are grateful to George E. Andrews for providing helpful insights during this work and for directing us to [1] and [3].

References

[1] G. E. Andrews, A Generalization of a Partition Theorem of MacMahon, Journal of Combinatorial Theory, 3 (1967), 100-101

[2] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004

[3] G. E. Andrews, H. Eriksson, F. Petrov, and D. Romik, Integrals, partitions and MacMahon's theorem, Journal of Combinatorial Theory, Series A, 114, no. 3 (2007), 545-554

[4] B. C. Berndt, Number Theory in the Spirit of Ramanujan, American Mathematical Society, Providence, 2004

[5] H. Gupta, A partition theorem of Subbarao, Canadian Mathematical Bulletin, 17, no. 1 (1974), 121-123

[6] A. E. Holroyd, Partition identities and the coin exchange problem, Journal of Combinatorial Theory, Series A, 115, no. 6 (2008), 1096-1101

[7] M. R. Kanna, B. N. Dharmendra, G. Sridhara, and R. P. Kumar, Generalized Bijective Proof of the Partition Identity of MV Subbarao, International Mathematical Forum, 8, no. 5 (2013), 215-222

[8] P. A. MacMahon, Combinatory Analysis, Vol. 2, Cambridge, 1916 (reprinted by Chelsea, New York, 1960)

[9] M. V. Subbarao, On a Partition Theorem of MacMahon-Andrews, Proceedings of the American Mathematical Society 27, no. 3 (1971), 449-450

[10] A. J. Yee, MacMahon's partition identity and the coin exchange problem, Journal of Combinatorial Theory, Series A, 116, no. 7 (2009), 1228-1231

Shishuo Fu (1) * ([dagger]) and James A. Sellers (2) ([double dagger])

(1) Chongqing University, P.R. China

(2) Penn State University, University Park, USA

* Email: fsshuo@cqu.edu.cn

([dagger]) Research supported by Chongqing University startup fund #0208001104411

([double dagger]) Email: sellersj@psu.edu.cn