EXTENDING A RECENT RESULT OF SANTOS ON PARTITIONS INTO ODD PARTS

James A. Sellers

Department of Mathematics, The Pennsylvania State University, University Park, PA 16802, USA

                          sellersj@math.psu.edu

Received:8/27/02, Accepted: 4/7/03, Published: 4/9/03

Abstract

In a recent note, Santos proved that the number of partitions of n using only odd parts equals the number of partitions of n of the form p_{1} + p_{2} + p_{3} + p_{4} + … such that p_{1} ≥ p_{2} ≥ p_{3} ≥ p_{4} ≥ ⋯ ≥ 0 and p_{1} ≥ 2p_{2} + p_{3} + p_{4} + …. Via partition analysis, we extend this result by replacing the last inequality with p_{1} ≥ k_{2}p_{2}+k_{3}p_{3}+k_{4}p_{4}+…, where k_{2}, k_{3}, k_{4}, … are nonnegative integers. Several applications of this result are mentioned in closing.

1 Background

One of the most celebrated identities in the theory of partitions is attributed to Leonhard Euler and reads as follows:

Theorem 1.1. Let d(n) be the number of partitions of n into distinct parts and let o(n) be the number of partitions of n into odd parts. Then, for all n ≥ 0, d(n) = o(n).

In a recent paper, Santos [12] proved via a bijection that o(n) also equals the number of partitions of n of the form p_{1} +p_{2} +p_{3} +p_{4} +… such that p_{1} ≥ p_{2} ≥ p_{3} ≥ p_{4} ≥ ⋯ ≥ 0 and p_{1} ≥ 2p_{2} + p_{3} + p_{4} + ….

Our goal in this note is to prove Santos’ result via generating functions. Actually, we will prove a much more general result using the technique of partitions analysis, introduced by Percy MacMahon [11, Vol. II, Section VIII] and heavily utilized recently by G. Andrews, P. Paule, A. Riese and others [1, 2, 3, 4, 5, 6, 7, 8, 9].

Our main theorem is as follows:

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A04 2

Theorem 1.2. Let K = (k_{2}, k_{3}, k_{4}, …) be an infinite vector of nonnegative integers. Define p(n; K) as the number of partitions of n of the form p_{1} + p_{2} + p_{3} + p_{4} + … with p_{1} ≥ p_{2} ≥ p_{3} ≥ p_{4} ⋯ ≥ 0 and p_{1} ≥ k_{2}p_{2} + k_{3}p_{3} + k_{4}p_{4} + …. Then, for all n ≥ 0, p(n; K) equals the number of partitions of n whose parts must be 1’s or of the form (∑_{i=2}^{m} k_{i}) + (m − 1) for some integer m ≥ 2.

Before turning to the proof of Theorem 1.2, we briefly mention a few key items from partition analysis. First, we define the Omega operator Ω_{≧}.

Definition 1.3. The operator Ω_{≧} is given by

Ω_{≧} ∑_{s_{1}=−∞}^{∞} ⋯ ∑_{s_{j}=−∞}^{∞} A_{s_{1},...,s_{j}}λ_{1}^{s_{1}} … λ_{j}^{s_{j}} := ∑_{s_{1}=0}^{∞} ⋯ ∑_{s_{j}=0}^{∞} A_{s_{1},...,s_{j}},

where the domain of the A_{s_{1},...,s_{j}} is the field of rational functions over ℂ in several complex variables and the λ_{i} are restricted to annuli of the form 1 − ε < |λ_{i}| < 1 + ε.

In the work below, we will also use the symbol μ as a parameter like λ_{j} for some j. Finally, we need the following lemma involving the Omega operator.

Lemma 1.4.

Ω_{≧} \frac{1}{(1 − λx) (1 − \frac{y}{λ})} = \frac{1}{(1 − x)(1 − xy)}.

A proof of this result can be found in [3, Lemma 1.1].

2 Main Result

Now we are in position to prove Theorem 1.2 via generating function manipulations.

Proof. Note that

∑_{n=0}^{∞} p(n; K)q^{n} = ∑_{\begin{matrix}p_{1} ≥ p_{2} ≥ p_{3} ≥ ⋯ ≥ 0 \\ p_{1} ≥ k_{2}p_{2} + k_{3}p_{3} + … \end{matrix}} q^{p_{1}+p_{2}+p_{3}+...}

= Ω_{≧} ∑_{p_{1}, p_{2}, p_{3}, ⋯ ≥ 0} q^{p_{1}+p_{2}+p_{3}+...} (λ_{1}^{p_{1}−p_{2}}λ_{2}^{p_{2}−p_{3}}λ_{3}^{p_{3}−p_{4}} …) μ^{p_{1}−k_{2}p_{2}−k_{3}p_{3}−...}

by the definition of the Omega operator. Hence, after rewriting the above and applying Lemma 1.4 multiple times, we find that

∑_{n=0}^{∞} p(n; K)q^{n} = Ω_{≧} \frac{1}{(1 − qλ_{1}μ) (1 − \frac{qλ_{2}}{λ_{1}μ^{k_{2}}} ) (1 − \frac{qλ_{3}}{λ_{2}μ^{k_{3}}} ) …}

= Ω_{≧} \frac{1}{(1 − qμ) (1 − \frac{q^{2}λ_{2}}{μ^{k_{2}−1}} ) (1 − \frac{qλ_{3}}{λ_{2}μ^{k_{3}}} ) …}

= Ω_{≧} \frac{1}{(1 − qμ) (1 − \frac{q^{2}}{μ^{k_{2}−1}} ) (1 − \frac{q^{3}λ_{3}}{μ^{k_{3}+k_{2}−1}} ) …}

We continue to apply Lemma 1.4 to eliminate all parameters λ_{j} to obtain

∑_{n=0}^{∞} p(n; K)q^{n} = Ω_{≧}(\frac{1}{1 − qμ}) (\frac{1}{1 − \frac{q^{2}}{μ^{k_{2}−1}}} ) (\frac{1}{1 − \frac{q^{3}}{μ^{k_{2}+k_{3}−1}}} ) …

At this point, the only parameter to eliminate is μ. We now rewrite the generating function above in terms of geometric series and annilihate μ based on the definition of the Omega operator. Thus,

∑_{n=0}^{∞} p(n; K)q^{n} = Ω_{≧} ∑_{a_{1}≥0}(qμ)^{a_{1}} ∑_{a_{2}≥0}(q^{2}μ^{−k_{2}+1})^{a_{2}} ∑_{a_{3}≥0}(q^{3}μ^{−k_{3}−k_{2}+1})^{a_{3}} …
= Ω_{≧} ∑_{a_{1},a_{2},a_{3},···≥0} q^{a_{1}+2a_{2}+3a_{3}+...}μ^{a_{1}+(−k_{2}+1)a_{2}+(−k_{3}−k_{2}+1)a_{3}+...}
= Ω_{≧} ∑_{\begin{matrix}a_{2}, a_{3}, ⋯ ≥ 0 \\ a_{1} ≥ (k_{2} − 1)a_{2} + (k_{3} + k_{2} − 1)a_{3} + … \end{matrix}} q^{a_{1}+2a_{2}+3a_{3}+...}μ^{a_{1}−[(k_{2}−1)a_{2}+(k_{3}+k_{2}−1)a_{3}+...]}

= ∑_{a_{2}≥0} q^{2a_{2}} × ∑_{a_{3}≥0} q^{3a_{3}} × ⋯ × ∑_{a_{1}≥(k_{2}−1)a_{2}+(k_{3}+k_{2}−1)a_{3}+...} q^{a_{1}}

= ∑_{a_{2}≥0} q^{2a_{2}} × ∑_{a_{3}≥0} q^{3a_{3}} × ⋯ × \frac{q^{(k_{2}−1)a_{2}+(k_{3}+k_{2}−1)a_{3}+...}}{1 − q}
= \frac{1}{(1 − q)(1 − q^{k_{2}+1})(1 − q^{k_{3}+k_{2}+2})(1 − q^{k_{4}+k_{3}+k_{2}+3}) …}.

The result follows.

3 Applications

We close with several comments related to Theorem 1.2. First off, Santos’ result is clearly proven via Theorem 1.2 using the vector K = (2, 1, 1, 1, …). Next, note that the vector K = (1, 0, 0, 0, …) also yields an obvious result. Namely, the number of partitions of n of the form p_{1} + p_{2} + p_{3} + … with p_{1} ≥ p_{2} ≥ p_{3} ≥ ⋯ ≥ 0 and p_{1} ≥ p_{2} is simply p(n), whose generating function is

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

which is what we obtain in Theorem 1.2 with K = (1, 0, 0, 0, …).

A third example of Theorem 1.2 arises in connection with the vector K = (1, 1, 1, 1, …). From Theorem 1.2 we find that the number of partitions of n with p_{1} ≥ p_{2} + p_{3} + p_{4} + … equals the number of partitions of n using 1’s and even integers as parts. This means

∑_{n=0}^{∞} p(n; (1, 1, 1, 1, …))q^{n} = \frac{1}{(1 − q)(1 − q^{2})(1 − q^{4})(1 − q^{6}) …}.

Note that, by generating function dissection, we have

∑_{n=0}^{∞} p(2n; (1, 1, 1, 1, …))q^{2n}

= \frac{1}{2} [∑_{n=0}^{∞} p(n; (1, 1, 1, 1, …))q^{n} + ∑_{n=0}^{∞} p(n; (1, 1, 1, 1, …))(−q)^{n}]
= \frac{1}{2} (\frac{1}{(1 − q^{2})(1 − q^{4})(1 − q^{6}) …}) (\frac{1}{1 − q} + \frac{1}{1 + q} )
= \frac{1}{2} (\frac{1}{(1 − q^{2})(1 − q^{4})(1 − q^{6}) …}) (\frac{2}{(1 − q)(1 + q)})
= \frac{1}{(1 − q^{2})^{2}(1 − q^{4})(1 − q^{6}) …}.

Thus,

∑_{n=0}^{∞} p(2n; (1, 1, 1, 1, …))q^{n} = \frac{1}{(1 − q)^{2}(1 − q^{2})(1 − q^{3}) …}.

Similar analysis shows that p(2n + 1; (1, 1, 1, 1, …)) has the same generating function. A variant of this generating function recently arose in the context of graphical forest partitions [10]. Namely, let gf(2k) be the number of partitions of 2k such that each partition, when viewed as the degree sequence of a graph, has a graphical representation which is a tree or union of trees (forest). Since the generating function for gf(2n), as shown in [10], is

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

we now know that

p(2n − 2; (1, 1, 1, 1, …)) = gf(2n)

for all n ≥ 1.

We close with one last well-known partition function which is related to the Rogers-Ramanujan identities. Namely, let p_{5}^{∗}(n) be the number of partitions of n into parts congruent to ±1 (mod 5). Then it is clear that p_{5}^{∗}(n) = p(n; (3, 1, 2, 1, 2, 1, 2, …)) for all n. By way of generalization, let p_{m}^{∗}(n) be the number of partitions of n into parts congruent to ±1 (mod m) (for m ≥ 3). Then, for all n ≥ 0,

p_{m}^{∗}(n) = p(n; (m − 2, 1, m − 3, 1, m − 3, 1, m − 3, …)).

Of course, the case m = 4 returns us to Santos’ result, the original motivation for this note.

References

[1] G. Andrews, MacMahon’s partition analysis: I. The lecture hall partition theorem, in Mathematical Essays in Honor of Gian-Carlo Rota, B.E. Sagan and R.P. Stanley, eds, pp. 1-22. Boston, Birkhuser, 1998.

[2] G. Andrews, MacMahon’s partition analysis: II. Basic theorems, Ann. Comb. 4 (2000), 327-338.

[3] G. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis: The omega package, Europ J. Combinatorics 22, no. 7 (2001), 887-904.

[4] G. Andrews and P. Paule, MacMahon’s partition analysis IV: Hypergeometric multisums, Paper B42i, Issue 42, Séminaire Lotharingien de Combinatoire (electronic journal).

[5] G. Andrews, P. Paule, A. Riese and V. Strehl, MacMahon’s partition analysis V: Bijections, recursions and magic squares, Algebraic Combinatorics and Applications, proccedings of Euroconference Alcoma99, September 12-19, 1999, Goessweistein, Germany, A. Betten, A. Kohnert, R. Laue and A. Wassermann, eds., pp. 1-39. Berlin, Springer, 2001.

[6] G. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis VI: A new reduction algorithm, Ann. Comb. 5, no. 3-4 (2001), 251–270.

[7] G. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis VII: Constrained compositions, AMS Contemporary Mathematics 291 (2001), 11-27.

[8] G. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis VIII: Plane partition diamonds, Advances in Appl. Math. 27 (2001), 231-242.

[9] G. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis IX: k-gon partitions, Bull. Austral. Math. Soc. 64 (2001), 321-329.

[10] D. Frank, C. Savage and J. Sellers, On the number of graphical forest partitions, to appear in Ars Comb.

[11] P. MacMahon, Combinatory Analysis, 2 Volumes, Cambridge University Press, Cambridge, 1915-1916 (Reprinted: Chelsea, New York, 1960).

[12] J. P. De O. Santos, On a new combinatorial interpretation for a theorem of Euler, Adv. Stud. Contemp. Math. (Pusan) 3, no. 2 (2001), 31-38.