[figure: “pmn” — 2012/2/5 — 20:47 — page 1 — #1]

Formulæ for the Number of Partitions of n into at most m parts

(Using the Quasi-Polynomial Ansatz)

Andrew V. Sills*

Department of Mathematical Sciences, Georgia Southern University Statesboro, GA, 30458-8093

Doron Zeilberger^{∗}

Department of Mathematics, Hill Center- Busch Campus, Rutgers University, 110 Frelinghuysen Rd, Piscataway, NJ 08854-8019, USA

February 5, 2012

Key Words: integer partitions AMS Subject Classification: 05A17, 11P81.

Abstract

The purpose of this short article is to announce, and briefly describe, a Maple package, PARTITIONS, that (inter alia) completely automatically discovers, and then proves, explicit expressions (as sums of quasi-polynomials) for p_{m}(n) for any desired m. We do this to demonstrate the power of “rigorous guessing” as facilitated by the quasi-polynomial ansatz.

∗E-mail addresses: ASills@GeorgiaSouthern.edu, zeilberg@math.rutgers.edu

[figure: “pmn” — 2012/2/5 — 20:47 — page 2 — #2]

2  A. V. Sills and D. Zeilberger

1. Introduction

Recall that a partition of a non-negative integer n is a non-increasing sequence of positive integers λ_{1} … λ_{m} that sum to n. For example the integer 5 has the following seven partitions: {5, 41, 32, 311, 221, 2111, 11111}. The bible on partitions is George Andrews’ magnum opus [1].

We denote by p_{m}(n) the number of partitions of n into at most m parts. By a classic theorem [1, p. 8, Thm. 1.4], p_{m}(n) also equals the number of partitions of n into parts that are at most m. There is an extensive literature concerning formulæ for p_{m}(n), including contributions by Cayley, Sylvester, Glaisher, and Gupta. For additional references and historical notes, see George Andrews’ fascinating article [2, §3] and Gupta’s Tables [7, pp. i–xxxix]. For an exhaustive history through 1920, see Dickson [4, Ch. 3].

More recently, George Andrews’ student, Augustine O. Munagi, developed a beautiful theory of so-called q-partial fractions [9], where the denominators in the decomposition are always expressions of the form (1 − q^{r})^{s}, rather than powers of cyclotomic polynomials as is the case with the ordinary partial fraction decomposition. Accordingly, formulæ for p_{m}(n) derived from the q-partial fraction decomposition of the generating function are most naturally expressed in terms of binomial coefficients.

It is well-known and easy to see that for any m, p_{m}(n) is a sum of quasi-polynomials of periods 1, 2, 3, …, m. A quasi-polynomial of period r is a function f(n) on the integers such that there exist r polynomials P_{1}(n), P_{2}(n), …, P_{r}(n) such that f(n) = P_{i}(n) if n ≡ i (mod r). We represent such a quasi-polynomial as a list [P_{1}(n), …, P_{r}(n)].

2. The PARTITIONS Maple package

2.1. Overview

The purpose of this short article is to announce, and briefly describe, a Maple package, PARTITIONS, that completely automatically discovers, and then proves, explicit expressions (as sums of quasi-polynomials) for p_{m}(n) for any desired m. So far we only bothered to derive the formulæ for 1 ≤ m ≤ 70, but one can easily go far beyond.

Not only that, we can, more generally, derive (and prove!), completely automatically, expressions, as sums of quasi-polynomials, for the number of ways of making change for n cents in a country whose coins have denominations of any given set of positive integers.

Not only that, we can, derive (and prove!), completely automatically, expressions (as sums of quasi-polynomials) for D_{k}(n), the number of partitions of n whose Durfee square has size k, for any desired, (numeric) positive integer k. (Recall that the size of the Durfee square of a partition λ_{1} . . . ...λ_{m} is the largest k such that λ_{k} ≥ k.)

Not only that, we (or rather our computers (and of course yours, if it has Maple and is loaded with our package)) can derive asymptotic expressions, to any desired order, for both p_{m}(n) and D_{k}(n). As far we we know the formula for D_{k}(n) is brand-new, and the previous attempts for the asymptotic formula for p_{m}(n) by humans G.J. Rieger [12] and E.M. Wright [14] (of Hardy-and-Wright fame) only went as far as O(n^{−2}) and O(n^{−4}) respectively. We go all the way to O(n^{−100})! (and of course can easily go far beyond).

[figure: “pmn” — 2012/2/5 — 20:47 — page 3 — #3]

Formulæ for the number of partitions of n into at most m parts  3

Not only that, we implement George Andrews’ ingenious way ( [2, sec. 3]) to convert any quasi-polynomial to a polynomial expression where one is also allowed to use the integer-part function ⌊n⌋. This enabled our computers to find Andrews-style expressions for p_{m}(n) for 1 ≤ m ≤ 70.

All these feats (and more!) are achieved by the Maple package PARTITIONS.

2.2. Using the PARTITIONS package

In order to use PARTITIONS, you must have Maple^{T M} installed on your computer. Then download the file:

   http://www.math.rutgers.edu/~zeilberg/tokhniot/PARTITIONS

and save it as PARTITIONS. Then launch Maple, and at the prompt, enter:

   read PARTITIONS:

and follow the on-line instructions. Let’s just highlight the most important procedures. AS100(m,n): shows the pre-computed first 100 terms of the asymptotic expression,

in n, of p_{m}(n) for symbolic m.

ASD80(k,n): shows the pre-computed first 80 terms of the asymptotic expression, in n, of D_{k}(n) for symbolic k.

BuildDBpmn(n,M): inputs a symbol n and a positive integer M and outputs a list of size M whose i-th entry is an expression for p_{i}(n) as a sum of i quasi-polynomials

DiscoverAS(m,n,k): discovers the asymptotic expansion to order k of p_{m}(n) (the number of partitions of n into at most m parts) for large n and fixed, but symbolic, m.

DiscoverDAS(k,n,r): discovers the asymptotic expansion to order r of D_{k}(n) (the number of partitions of n whose Durfee square has size k) for large n and fixed, but symbolic k.

Durfee(k,n): discovers (rigorously!) the quasi-polynomial expression, in n, for D_{k}(n), for any desired positive integer k. It is extremely fast for small k, but of course gets slower as k gets larger.

DurfeePC(k,n): does the same thing (much faster, of course!) using the precomputed expressions of Durfee(k,n); for k ≤ 40.

EvalQPS(L,n,n0): evaluates the sum of the quasi-polynomials in the variable n given in the list L at n = n_{0}.

HRR(n,T): evaluates in floating point the sum of the first T terms of the Hardy-Ramanujan-Rademacher formula for p(n), the number of unrestricted partitions of n:

p(n) = \frac{1}{π\sqrt{2}} ∑_{k≥1} \sqrt{k} _{∑_{0≤h<k} ; gcd(h,k)=1}e^{πi(s(h,k)−2nh/k)} \frac{d}{dn} (\begin{matrix}sinh & (\frac{π}{k} \sqrt{\frac{2}{3} (n − \frac{1}{24})}) \\ √ & \overline{n − \frac{1}{24}} \end{matrix} ) ,

where s(h, k) = ∑_{j=1}^{k−1} (\frac{j}{k} − ⌊\frac{j}{k}⌋ − \frac{1}{2}) (\frac{hj}{k} − ⌊\frac{hj}{k} ⌋ − \frac{1}{2})is the Dedekind sum.

Please be warned that for larger n you need to increase Digits. In order to get reliable results you may want to use procedure HRRr(n,T,k).

pmn(m,n): discovers (rigorously!) the quasi-polynomial expression, in n, for p_{m}(n), for any desired positive integer m. It is extremely fast for small m, but of course gets slower as m gets larger.

[figure: “pmn” — 2012/2/5 — 20:47 — page 4 — #4]

4  A. V. Sills and D. Zeilberger

pmnPC(m,n): does the same thing (much faster, of course!) using the pre-computed expressions of pmn(m,n); for m ≤ 70.

pmnAndrews(m,n): discovers (rigorously!) the Andrews-style expression, in n, for p_{m}(n) for any desired positive integer m. Instead of using quasi-polynomials explicitly (that some humans find awkward), it uses the integer-part function ⌊n⌋, denoted by

trunc(n) in Maple.

pn(n): the number of partitions of n, p(n), using Euler’s recurrence. It is useful for checking, since p_{n}(n) = p(n).

pnSeq(N): the list of the first N values of p(n). The output of pnSeq(50000): can be gotten from

   http://www.math.rutgers.edu/~zeilberg/tokhniot/oPARTITIONS9

where this list of 50000 terms is called pnTable.

pSn(S,n,K): the more general problem where the parts are drawn from the list S of positive integers. It outputs an explicit expression, as a sum of quasi-polynomials, for p_{S}(n), the number of integer partitions of n whose parts are drawn from the finite list of positive integers S. K is a guessing parameter, that should be made higher if the procedure returns FAIL.

pmnNum(m,n0): like pmn(m,n); but for both numeric m and n0. The output is a number. For m ≤ 70 it is extremely fast, since it uses the pre-computed values of p_{m}(n) gotten from pmnPC(m,n);. For example to get the number of integer partitions of a googol (10^{100}) into at most 60 parts, you would get, in 0.02 seconds, the 5783-digit integer, by simply typing

   pmnNum(60,10**100); .

One of us (DZ) posed this as a 100-dollar challenge to the users of the very useful Mathoverflow forum. This was taken-up, successfully, by user joro [5], whose computer did it correctly in about 2 hours, using PARI. User joro generously suggested that instead of sending him a check, DZ should donate it in joro’s honor, to a charity of DZ’s choice, and the latter decided on the Wikipedia Foundation.

Sample input and output can be gotten from the “front” of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/
mamarimhtml/pmn.html .

3. Methodology: Rigorous Guessing

The idea of deriving formulæ for p_{m}(n) and p_{S}(n) with the aid of the partial fraction decomposition of the generating function dates back at least to Cayley [3]. We ask Maple to convert the generating function

∑_{n≥0} p_{m}(n)q^{n} = \frac{1}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{m})}

or in the case of p_{S}(n), where S = {s_{1}, s_{2}, …, s_{j}},

∑_{n=0}^{∞} p_{S}(n)q^{n} = \frac{1}{(1 − q^{s_{1}})(1 − q^{s_{2}}) ⋯ (1 − q^{s_{j}})}

into partial fractions. Then for each piece, Maple finds the first few terms of the Maclaurin expansion, and then fits the data with an appropriate quasi-polynomial using undetermined

[figure: “pmn” — 2012/2/5 — 20:47 — page 5 — #5]

Formulæ for the number of partitions of n into at most m parts  5

coefficients. The output is the sum of these quasi-polynomials. See the source-code for more details.

Example. Consider the case m = 4. We have Maple calculate that

∑_{n≥0} p_{4}(n)q^{n} = \frac{1}{(1 − q)(1 − q^{2})(1 − q^{3})(1 − q^{4})}

= \frac{17/72}{1 − q} + \frac{59/288}{(1 − q)^{2}} + \frac{1/8}{(1 − q)^{3}} + \frac{1/24}{(1 − q)^{4}} + \frac{1/8}{1 + q} + \frac{1/32}{(1 + q)^{2}} + \frac{(1 + q)/9}{1 + q + q^{2}} . (1)

At this point we could, as Cayley did, expand each term as a series in q, collect like terms, and then the coefficient of q^{n} will be a formula for p_{4}(n), but why bother? From Sylvester [13] and Glaisher [6], we know that

p_{4}(n) = ∑_{j=1}^{4} W_{j}(n),

where each W_{j}(n) is a quasi-polynomial [P_{j1}(n), P_{j2}(n), …, P_{jj}(n)] of period j. Further, W_{j}(n) is of degree ⌊\frac{m−j}{j} ⌋, and arises from those terms of (1) with denominator a power of the j-th cyclotomic polynomial. Instead, let us allow Maple to guess the correct quasipolynomials: We know a priori that W_{1}(n) is of the form [a_{0} + a_{1}n + a_{2}n^{2} + a_{3}n^{3}] and let Maple calculate the (beginning of the) Maclaurin series for the terms of (1) that contribute to W_{1}(n):

\frac{17/72}{1 − q} + \frac{59/288}{(1 − q)^{2}} + \frac{1/8}{(1 − q)^{3}} + \frac{1/24}{(1 − q)^{4}} = \frac{175}{288} + \frac{19}{16}q + \frac{581}{288}q^{2} + \frac{113}{36}q^{3} + O(q^{4}).

Thus,

[ \begin{matrix}1 & 0 & 0 & 0 \\ 1^{0} & 1^{1} & 1^{2} & 1^{3} \\ 2^{0} & 2^{1} & 2^{2} & 2^{3} \\ 3^{0} & 3^{1} & 3^{2} & 3^{3} \end{matrix} ] [ \begin{matrix}a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{matrix} ] = [ \begin{matrix}175/288 \\ 19/16 \\ 581/288 \\ 113/36 \end{matrix} ] ,

which immediately implies that

W_{1}(n) = [\frac{1}{144}n^{3} + \frac{5}{48}n^{2} + \frac{15}{32}n + \frac{175}{288}] .

Similarly, for W_{2}(n), which must be of the form

[a_{1} + a_{3}n, a_{0} + a_{2}n],

we find

\frac{1/8}{1 + q} + \frac{1/32}{(1 + q)^{2}} = \frac{5}{32} − \frac{3}{16}q + \frac{7}{32}q^{2} − \frac{1}{4}q^{3} + O(q^{4}),

so that

[ \begin{matrix}1 & 0 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}a_{0} \\ a_{2} \end{matrix} ] = [ \begin{matrix}5/32 \\ 7/32 \end{matrix} ]

[figure: “pmn” — 2012/2/5 — 20:47 — page 6 — #6]

6  A. V. Sills and D. Zeilberger

and

[ \begin{matrix}1 & 1 \\ 1 & 3 \end{matrix} ] [ \begin{matrix}a_{1} \\ a_{3} \end{matrix} ] = [ \begin{matrix}−3/16 \\ −1/4 \end{matrix} ] ,

and thus

W_{2}(n) = [−\frac{5}{32} − \frac{n}{32}, \frac{5}{32} + \frac{n}{32}] .

Analogous reasoning yields W_{3}(n) = [0, −\frac{1}{9}, \frac{1}{9}] and W_{4}(n) = [0, −\frac{1}{8}, 0, \frac{1}{8}].

4. Conclusion

The present approach uses very naïve guessing to discover, and prove (rigorously!), formulas (or as Cayley and Sylvester would say, formulæ) for the number of partitions of the integer n into at most parts m parts for m ≤ 70, and of course, one can easily go far beyond. The core of the idea goes back to Arthur Cayley, and is familiar to any secondsemester calculus student: partial fractions! But dear Arthur could only go so far, so his good buddy, James Joseph Sylvester, invented a sophisticated theory of “waves” [13] that facilitated hand calculations, which were later dutifully carried out by J. W. L. Glaisher in [6]. But, with modern computer algebra systems (Maple in our case), one can go much further by just using Cayley’s original ideas.

References

[1] G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976. Reprinted by Cambridge University Press, 1984. First paperback edition, 1998.

[2] G. E. Andrews, Partitions: at the interface of q-series and modular forms, Ramanujan J. 7 (2003), 384-400.

[3] A. Cayley, Researches on the partition of numbers, Phil. Trans. Royal Soc. of London, 146 (1856), 127–140.

[4] L. E. Dickson, History of the Theory of Numbers, vol. 2: Diophantine Analysis, Carnegie Institute, Washington, 1920. Reissued by AMS Chelsea and Dover.

[5] “joro”, answer to Doron Zeilberger’s 100-dollar challenge,

    http://mathoverflow.net/questions/71092/
    how-many-integer-partitions-of-a-googol-10100-into-at-most-60-parts

[6] J. W. L. Glaisher, Formulæ for partitions into given elements, derived from Sylvester’s theorem, Quart. J. Pure Appl. Math. 40 (1909), 275–348.

[7] H. Gupta, Tables of Partitions, Royal Society Mathematical Tables, vol. 4, Cambridge University Press, 1958.

[figure: “pmn” — 2012/2/5 — 20:47 — page 7 — #7]

Formulæ for the number of partitions of n into at most m parts  7

[8] G. H. Hardy and S. Ramanujan, Asymptotic formulæ in combinatory analysis, Proc. London Math. Soc. (2) 17 (1918), 75–115.

[9] A. O. Munagi, Computation of q-partial fractions, INTEGERS 7 (2007) #A25.

[10] H. Rademacher, On the partition function p(n), Proc. London Math. Soc. (2) 43 (1938) 241–254.

[11] H. Rademacher, On the expansion of the partition function in a series, Ann. Math. (2) 44 (1943) 416–422.

[12] G. J. Rieger, Über Partitionen, Math. Annalen 138 (1959), 356-362.

[13] J. J. Sylvester, On subinvariants, i.e. semi-invariants to binary quantics of an unlimited order. With an excursus on rational fractions and partitions, Quart. J. Math. (Oxford Series (2)) 2 (1882) 85–108.

[14] E.M. Wright, Partitions into k parts, Math. Annalen 142 (1961), 311-316.