A Note on the

Andrews-Ericksson-Petrov-Romick Bijection for MacMahon’s Partition Theorem

Beaullah Mugwangwavari and Darlison Nyirenda School of Mathematics University of the Witwatersrand P. O. Wits 2050 Johannesburg South Africa

                  712040@students.wits.ac.za
                 darlison.nyirenda@wits.ac.za

Abstract Andrews’ generalization of MacMahon’s partition theorem states that the number of partitions of n in which odd multiplicities are at least 2r + 1 is equal to the number of partitions in which odd parts are congruent to 2r + 1 (mod 4r + 2). In this note, we give a bijective proof of this generalization. Our result naturally extends the bijection of Andrews, Ericksson, Petrov, and Romik for MacMahon’s partition theorem.

1 Introduction

Let n ∈ ℤ_{≥1}. A partition of n is a sequence of positive integers (λ_{1}, λ_{2}, …) where λ_{1} ≥ λ_{2} ≥ ⋯ and ∑_{j≥1} λ_{j} = n. The components λ_{i} are called parts of a partition. If further restrictions are imposed on the parts, one gets some interesting partition functions. One such example is the number of partitions of n into distinct parts. This is interesting because it relates to the number of partitions of n into odd parts, a case of Euler’s partition identity [5]. A partition identity relates two partition functions. One of the partition identities of interest in this paper is Theorem 1, which is due to MacMahon.

Theorem 1 (MacMahon, [4]). The number of partitions of n wherein no part appears with multiplicity one is equal to the number of partitions of n where parts are even or congruent to 3 (mod 6).

Andrews, Ericksson, Petrov, and Romik [2] gave the first bijective proof of Theorem 1 which we describe in the sequel.

Let C_{n} denote the set of partitions of n wherein no part appears with multiplicity one and let D_{n} denote the set of partitions of n wherein parts are even or congruent to 3 (mod 6). The bijection goes as follows: let λ = (l^{h_{l}}, (l − 1)^{h_{l−1}}, …, 3^{h_{3}}, 2^{h_{2}}, 1^{h_{1}}) ∈ C_{n} where h_{i} is the multiplicity of i. Since no part appears exactly once, it follows that h_{i} ∈ {0, 2, 3, 4, …}. Uniquely decompose h_{i} as

h_{i} = k_{i} + g_{i}, where k_{i} ∈ {0, 3}, g_{i} ∈ {0, 2, 4, 6, 8, …}.

For j ≥ 1, define d_{j} as follows:

d_{6t+1} = d_{6t+5} = 0,
d_{6t+2} = \frac{1}{2}g_{3t+1},
d_{6t+4} = \frac{1}{2}g_{3t+2},
d_{6t+3} = \frac{1}{3}k_{2t+1} + g_{6t+3},
d_{6t+6} = \frac{1}{3}k_{2t+2} + g_{6t+6},

where t = 0, 1, 2, …

The partition (f^{d_{f}} , (f − 1)^{d_{f−1}}, …, 2^{d_{2}}, 1^{d_{1}}) is in D_{n}. We shall call the above mapping the Andrews-Ericksson-Petrov-Romik bijection.

Andrews later gave a generalization for Theorem 1 which we recall below.

Theorem 2 (Andrews, [1]). Let A_{r}(n) denote the set of partitions of n wherein parts appearing an odd number of times actually appear at least 2r + 1 times and let B_{r}(n) denote the set of partitions of n wherein odd parts are congruent to 2r + 1 (mod 4r + 2). Then

|A_{r}(n)| = |B_{r}(n)|.

However, there is no bijective proof that naturally extends Andrews-Ericksson-Petrov-Romik bijection to prove Theorem 2. For this, you may consult [3] and the references therein. Our aim in this short note is to supply a bijection for Theorem 2, which naturally generalizes Andrews-Ericksson-Petrov-Romik bijection and is different from the ones given in the literature.

2 The bijection

We now describe our bijection for Theorem 2. We need to establish the one-to-one correspondence between the sets A_{r}(n) and B_{r}(n).

Let (l^{h_{l}}, (l − 1)^{h_{l−1}}, …, 3^{h_{3}}, 2^{h_{2}}, 1^{h_{1}}) ∈ A_{r}(n). In this notation, h_{i} is the multiplicity of i. Note that h_{i} can be zero for some i. Clearly, h_{i} ∈ {0, 2, 4, …, 2r, 2r + 1, 2r + 2, …}.

Write h_{i} as

h_{i} = k_{i} + g_{i} where k_{i} ∈ {0, 2r + 1} and g_{i} ∈ {0, 2, 4, 6, 8, 10, …}

This decomposition is unique since k_{i} and g_{i} can be made explicit, i.e.,

k_{i} = (2r + 1) (\frac{1 − (−1)^{h_{i}}}{2} ) and g_{i} = h_{i} − (2r + 1) (\frac{1 − (−1)^{h_{i}}}{2} ) .

For j ≥ 1, define d_{j} as follows:

d_{(4r+2)t+2j−1} = 0 for j ∈ {1, 2, …, 2r + 1} \ {r + 1},
d_{(4r+2)t+2j} = \frac{1}{2}g_{(2r+1)t+j} for j ∈ \{1, 2, …, 2r\},
d_{(4r+2)t+(2r+1)j} = \frac{1}{2r + 1}k_{2t+j} + g_{(4r+2)t+(2r+1)j} for j ∈ \{1, 2\},

where t = 0, 1, 2, . . ..

The image is thus given by

(…, f^{d_{f}} , (f − 1)^{d_{f−1}}, …, 2^{d_{2}}, 1^{d_{1}}).

We claim that (…, f^{d_{f}} , (f − 1)^{d_{f−1}}, …, 2^{d_{2}}, 1^{d_{1}}) ∈ B_{r}(n). In order to show that

(l^{h_{l}}, (l − 1)^{h_{l−1}}, …, 3^{h_{3}}, 2^{h_{2}}, 1^{h_{1}}) ↦ (…, f^{d_{f}} , (f − 1)^{d_{f−1}}, …, 2^{d_{2}}, 1^{d_{1}})

defines a bijection from A_{r}(n) onto B_{r}(n), it suffices to show that ∑_{i≥1} id_{i} = n.

Thus

∑_{i≥1} id_{i} = ∑_{j=1}^{r} ∑_{t=0}^{∞}((4r + 2)t + 2j − 1)d_{(4r+2)t+2j−1} + ∑_{j=r+2}^{2r+1} ∑_{t=0}^{∞}((4r + 2)t + 2j − 1)d_{(4r+2)t+2j−1}

+ ∑_{j=1}^{2r} ∑_{t=0}^{∞}((4r + 2)t + 2j)d_{(4r+2)t+2j} + ∑_{j=1}^{2} ∑_{t=0}^{∞}((4r + 2)t + (2r + 1)j)d_{(4r+2)t+(2r+1)j}

= ∑_{j=1}^{2r} ∑_{t=0}^{∞}((2r + 1)t + j)g_{(2r+1)t+j} + ∑_{j=1}^{2} ∑_{t=0}^{∞}((4r + 2)t + (2r + 1)j)g_{(4r+2)t+(2r+1)j}

+ ∑_{j=1}^{2} ∑_{t=0}^{∞}(2t + j)k_{2t+j}.

Using the notation

S(a, b) = ∑_{t=0}^{∞}(at + b)g_{at+b} and T (a, b) = ∑_{t=0}^{∞}(at + b)k_{at+b},

observe that

∑_{t=0}^{∞}((2r + 1)t + j)g_{(2r+1)t+j} = ∑_{ℓ=0,2r+1} ∑_{t=0}^{∞}((4r + 2)t + j + ℓ)g_{(4r+2)t+j+ℓ}
= S(4r + 2, j) + S(4r + 2, 2r + 1)

and

∑_{t=0}^{∞}(2t + j)k_{2t+j} = ∑_{t=0}^{∞} ∑_{ℓ=0}^{2r}((4r + 2)t + j + 2ℓ)k_{(4r+2)t+j+2ℓ}

= ∑_{ℓ=0}^{2r} T (4r + 2, j + 2ℓ).

Hence

∑_{i≥1} id_{i} = ∑_{j=1}^{2r} S(4r + 2, j) + ∑_{j=1}^{2r} S(4r + 2, j + 2r + 1) + ∑_{j=1}^{2} S(4r + 2, (2r + 1)j)

+ ∑_{ℓ=0}^{2r} T (4r + 2, 1 + 2ℓ) + ∑_{ℓ=0}^{2r} T (4r + 2, 2 + 2ℓ)

= ∑_{j=1}^{2r}(S(4r + 2, j) + S(4r + 2, j + 2r + 1) + T (4r + 2, 1 + 2j) + T (4r + 2, 2 + 2j))

+ ∑_{j=1}^{2} S(4r + 2, (2r + 1)j) + T (4r + 2, 1) + T (4r + 2, 2)

= ∑_{j=1}^{2r+1}(S(4r + 2, j) + S(4r + 2, j + 2r + 1)) + ∑_{j=0}^{2r}(T (4r + 2, 1 + 2j) + T (4r + 2, 2 + 2j))

= ∑_{j=1}^{2r+1}(S(4r + 2, j) + S(4r + 2, j + 2r + 1)) + ∑_{j=1}^{2r+1}(T (4r + 2, 2j − 1) + T (4r + 2, 2j))

= ∑_{j=1}^{4r+2} S(4r + 2, j) + ∑_{j=1}^{4r+2} T (4r + 2, j)

= ∑_{j=1}^{4r+2}(S(4r + 2, j) + T (4r + 2, j))

= ∑_{j=1}^{4r+2} ∑_{t=0}^{∞}((4r + 2)t + j)(g_{(4r+2)t+j} + k_{(4r+2)t+j})

= ∑_{t=0}^{∞} ∑_{j=1}^{4r+2}((4r + 2)t + j)h_{(4r+2)t+j}

= ∑_{i=1}^{∞} ih_{i}

= n.

Remark 3. Setting r = 1 in the bijection yields the bijection given by Andrews et al. [2].

For example, consider n = 15 and r = 2. Table 1 demonstrates the correspondence. The inverse of our map is described in the following section.

\begin{matrix}A_{2}(15) & ⟶ & B_{2}(15) \\ (2,2,2,2,2,1,1,1,1,1) & ↦ & (10,5) \\ (4,4,1,1,1,1,1,1,1) & ↦ & (8,5,2) \\ (3,3,2,2,1,1,1,1,1) & ↦ & (6,5,4) \\ (3,3,1,1,1,1,1,1,1,1,1) & ↦ & (6,5,2,2) \\ (2,2,2,2,1,1,1,1,1,1,1) & ↦ & (5,4,4,2) \\ (2,2,1,1,1,1,1,1,1,1,1,1,1) & ↦ & (5,4,2,2,2) \\ (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1) & ↦ & (5,2,2,2,2,2) \end{matrix}

Table 1: The map A_{r}(n) → B_{r}(n) for r = 2, n = 15.

3 The inverse mapping

We now describe the inverse to our bijection.

Given that (…, f^{d_{f}} , (f − 1)^{d_{f−1}}, …, 2^{d_{2}}, 1^{d_{1}}) ∈ B_{r}(n). Define g_{i} and k_{i} as

g_{(2r+1)t+j} = 2d_{(4r+2)t+2j}, j = 1, 2, … 2r, t = 0, 1, 2, …

For the remaining cases, we have, for t = 0, 1, 2, …,

g_{(4r+2)t+(2r+1)j} = \begin{cases}d_{(4r+2)t+(2r+1)j}, & if d_{(4r+2)t+(2r+1)j} ≡ 0 (mod 2), j = 1, 2; \\ d_{(4r+2)t+(2r+1)j} − 1, & if d_{(4r+2)t+(2r+1)j} ≡ 1 (mod 2), j = 1, 2, \end{cases}

and

k_{2t+j} = \begin{cases}0, & if d_{(4r+2)t+(2r+1)j} ≡ 0 (mod 2), j = 1, 2; \\ 2r + 1, & if d_{(4r+2)t+(2r+1)j} ≡ 1 (mod 2), j = 1, 2. \end{cases}

Then the partition (…, 3^{g_{3}+k_{3}}, 2^{g_{2}+k_{2}}, 1^{g_{1}+k_{1}}) is in A_{r}(n).

For example, Table 2 demonstrates the inverse mapping when n = 15.

\begin{matrix}B_{2}(15) & ⟶ & A_{2}(15) \\ (10,5) & ↦ & (2,2,2,2,2,1,1,1,1,1) \\ (8,5,2) & ↦ & (4,4,1,1,1,1,1,1,1) \\ (6,5,4) & ↦ & (3,3,2,2,1,1,1,1,1) \\ (6,5,2,2) & ↦ & (3,3,1,1,1,1,1,1,1,1,1) \\ (5,4,4,2) & ↦ & (2,2,2,2,1,1,1,1,1,1,1) \\ (5,4,2,2,2) & ↦ & (2,2,1,1,1,1,1,1,1,1,1,1,1) \\ (5,2,2,2,2,2) & ↦ & (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1) \end{matrix}

Table 2: The inverse map B_{r}(n) → A_{r}(n) for n = 15, r = 2.

References

[1] G. E. Andrews, A generalization of a partition theorem of MacMahon, J. Combin. Theory 3 (1967), 100–101.

[2] G. E. Andrews, H. Eriksson, F. Petrov, and D. Romik, Integrals, partitions and MacMahon’s theorem, J. Combin. Theory Ser. A 114 (2007), 545–554.

[3] S. Fu and J. A. Sellers, Bijective proofs of partition identities of MacMahon, Andrews, and Subbarao, Electron. J. Combin. 21 (2014), P2.41.

[4] P. A. MacMahon, Combinatory Analysis, Vol. 2, Cambridge University Press, 1916.

[5] D. Nyirenda, A note on a finite version of Euler’s partition identity, Australas. J. Combin. 71 (2018), 241–245.

2010 Mathematics Subject Classification: Primary 11P81; Secondary 11P83, 05A15. Keywords: partition, bijection.

Received June 27 2020; revised versions received August 25 2020; April 25 2021. Published in Journal of Integer Sequences, April 25 2021.

Return to Journal of Integer Sequences home page.