# Bijective Proofs of Partition Identities of MacMahon, Andrews, and Subbarao

Shishuo Fu<fnref n="1" />*† and James A. Sellers<fnref n="2" />‡

**Abstract.** We revisit a classic partition theorem due to MacMahon that relates partitions with all parts repeated at least once and partitions with parts congruent to 2, 3, 4, 6 (mod 6), together with a generalization by Andrews and two others by Subbarao. Then we develop a unified bijective proof for all four theorems involved, and obtain a natural further generalization as a result.

**Résumé.** Nous revisitons un théorème de partitions d'entiers dû à MacMahon, qui relie les partitions dont chaque part est répétée au moins une fois et celles dont les parts sont congrues à 2, 3, 4, 6 (mod 6), ainsi qu'une généralisation par Andrews et deux autres par Subbarao. Ensuite nous construisons une preuve bijective unifiée pour tous les quatre théorèmes ci-dessus, et obtenons de plus une généralisation naturelle.

**Keywords:** partition, residue classes, bijection, generating function

## 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$).

<footnote n="1">¹Chongqing University, P.R. China</footnote>

<footnote n="2">²Penn State University, University Park, USA</footnote>

<footnote>*Email: fsshuo@cqu.edu.cn</footnote>

<footnote>†Research supported by Chongqing University startup fund #0208001104411</footnote>

<footnote>‡Email: sellersj@psu.edu.cn</footnote>
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 \ge 2$ be an integer and let $\ell$ 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 $\ell$ and congruent to $\ell$ (mod $k$) equals the number of partitions of $n$ where all parts must be congruent to 0 (mod $k$) or congruent to $\ell$ (mod $2\ell$).

Subbarao goes on to say, “Andrews’ result corresponds to the choice $k = 2$, $\ell = 2r + 1$. The proof of this is analogous to that of Andrews’ and is therefore omitted.” Interesting enough, for many choices of $k$ and $\ell$, 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 $\ell$ 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 \ge 0$ be integers, and let $C_{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_{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_{m,r}(n) = D_{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

$$ \underbrace{p_1 + p_1 + \cdots + p_1}_{m_1 \text{ times}} + \underbrace{p_2 + p_2 + \cdots + p_2}_{m_2 \text{ times}} + \cdots + \underbrace{p_t + p_t + \cdots + p_t}_{m_t \text{ times}} $$
be a partition of $n$ counted by the left-hand side of Theorem 1.1. Thus, we know that each $m_i$, the multiplicity of the part $p_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_i$ for each $i$, in order to define our bijection.

• $m_i$ is even: In this case, we simply map the parts

$$ \underbrace{p_i + p_i + \cdots + p_i}_{m_i \text{ times}} $$

to the parts

$$ \underbrace{2p_i + 2p_i + \cdots + 2p_i}_{m_i/2 \text{ times}} $$

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

• $m_i$ is odd: Given that $m_i$ is odd, we know that $m_i \ge 3$. Thus, we split off three copies of the part $p_i$ and combine any of the remaining pairs of occurrences of $p_i$ (if $m_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_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. $\square$ 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.

We now transition to Theorem 1.3 as published by Subbarao.

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 $\ell$ (mod $2\ell$). (This may happen if no further restrictions are placed on $k$ and $\ell$.) 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 \ge 2$ be an integer and let $\ell$ 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 $\ell$ and congruent to $\ell$ (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 $\ell$ (mod $2\ell$).

**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

$$ \underbrace{p_1 + p_1 + \cdots + p_1}_{m_1 \text{ times}} + \underbrace{p_2 + p_2 + \cdots + p_2}_{m_2 \text{ times}} + \cdots + \underbrace{p_t + p_t + \cdots + p_t}_{m_t \text{ times}} $$

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

* $m_i$ is divisible by $k$: In this case, we simply map the parts

$$ \underbrace{p_i + p_i + \cdots + p_i}_{m_i \text{ times}} $$

to the parts

$$ \underbrace{kp_i + kp_i + \cdots + kp_i}_{m_i/k \text{ times}} $$

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_i$ is not divisible by $k$: Given that $m_i$ is not divisible by $k$, we know that $m_i \ge \ell$ and $m_i \equiv \ell \pmod k$. Thus, we split off $\ell$ copies of the part $p_i$ and combine any of the remaining $k$-tuples of occurrences of $p_i$ (if $m_i > \ell$) as was done in the previous step of the algorithm, and we should also color them blue. This now leaves us with $\ell$ copies of each of the parts $p_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 $\ell$ and color them red. (Each of these red parts will then be congruent to $\ell$ modulo $2\ell$.)
□ 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_{m,r}(n)$. If the multiplicity of some part is odd, say $m_i$ for part $p_i$ is odd, then we know $m_i \ge 2r+1$. We peel off $2r+1$ copies of the part $p_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_j$ with $2 \le m_j \le 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

$$ \underbrace{p_j + p_j + \cdots + p_j}_{m_j \text{ times}} $$

to the parts

$$ \underbrace{\frac{2p_j}{m^{\alpha_j}} + \frac{2p_j}{m^{\alpha_j}} + \cdots + \frac{2p_j}{m^{\alpha_j}}}_{m_j m^{\alpha_j} / 2 \text{ times}} $$

where $\alpha_j = \text{ord}_m(p_j) := \max\{\alpha \in \mathbb{N} \mid m^\alpha | p_j\}$. Note that $1 \le m_j/2 \le 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_{3,2}(389)$:

$$ \begin{aligned} & 20 + 20 + 20 + 20 + 20 + 20 + 20 + 16 + 16 + \\ & \qquad 15 + 15 + 15 + 15 + 15 + 15 + 15 + 15 + 15 + \\ & \qquad 7 + 7 + 7 + 7 + 7 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 3 + 3 + 3 + 3 \end{aligned} $$

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-partition $20+15+7+5$, and trigger the A-E conversion to get

$$ 20 + 15 + 7 + 5 \rightarrow 15 + 10 + 10 + 7 + 5 \rightarrow 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. \qquad (1) $$

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

$$ \begin{aligned} & 20 + 20 \rightarrow 40; \quad 16 + 16 \rightarrow 32; \quad 5 + 5 \rightarrow 10; \\ & 15 + 15 + 15 + 15 \rightarrow 10 + 10 + 10 + 10 + 10 + 10; \\ & 3 + 3 + 3 + 3 \rightarrow 2 + 2 + 2 + 2 + 2 + 2. \end{aligned} \qquad (2) $$
Note that the total multiplicity for 10 is $6 + 1 = 7$, where $6 + 1 = 2 \cdot 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_{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 \ge 2, m \ge 2$ be two integers and let $\ell$ be a positive integer which is not a multiple of $k$. Let $E_{m,\ell,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 $\ell$ (mod $k$) and at least $\ell$ and at most $\ell+k(m-1)$. Let $F_{m,\ell,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 $\ell$ (mod $2\ell$). Then $E_{m,\ell,k}(n) = F_{m,\ell,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