Formulae for the Number of Partitions of n into at most m parts(Using the Quasi-Polynomial Ansatz)

By Andrew V. Sills and Doron Zeilberger


.pdf   LaTex source  
[Appeared in Advances in Applied Mathematics v.48 (2012), 640-645]
First Written: Aug. 21, 2011.

Last update (of this webpage, not of article: May 14, 2016).


I once said that extreme ugliness is beautiful. Analogously, extreme naiveté is sophisticated! The present approach uses VERY NAIVE guessing to discover, and PROVE (rigorously!), formulas (or as Cayley and Sylvester would say, formulae) for the number of (integer) partitions of n into at most 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 second-semester calculus student: partial fractions! But dear Arthur could only go so far, so his good buddy, James Joseph Sylvester, designed a sophisticated theory of "waves" that facilitated hand-calculations.

But, with modern computer algebra systems (Maple and Mathematica in our case) one can go much further just using Cayley's original ideas. One should also mention the recent beautiful algorithm of Augustine Munagi, but our approach is even simpler.


Added Sept. 17, 2011: Watch the lecture:Part 1, Part 2

Maple Package


Sample Input and Output for PARTITIONS

  • If you want to see EXPLICIT expressions, in n, for the number of partitions of an integer n into at most m parts, with m between 1 and 60, in terms of QUASI-POLYNOMIALS,

    the input gives you the output web-book.

  • If you dislike quasi-polynomials, but, like guru George Andrews, love the "integer-part" function (called "trunc" in Maple), and want to see EXPLICIT Andrews-style expressions in n, for the number of partitions of an integer n into at most m parts, with m between 1 and 60, in terms of the four basic operations and "trunc",

    the input gives you the output web-book.

  • If you want to see EXPLICIT expressions, in n, for the number of partitions of an integer n whose Durfee square (alias H-index) is k, for 1 ≤ k ≤ 40, in terms of QUASI-POLYNOMIALS,

    the input gives you the output web-book.

  • If you want to see the first 100 (YES, one hundred!) terms in the asymptotic expansion of pm(n) for SYMBOLIC m (i.e. valid for every m, as n goes to infinity)

    the input gives you the output.

  • If you want to see the first 80 (YES, eighty!) terms in the asymptotic expansion of Dk(n) the number of partitions of n whose size-of-side-of-Durfee square (alias H-index) is k, for SYMBOLIC k (i.e. valid for every k, as n goes to infinity)

    the input gives you the output.

  • If you want to see the first 50000 (YES, fifty thousand!) values of p(n), the number of (integer) partitions of n,

    the input gives you the output.

    Note: the output file was slightly edited so that it can be used for computer-experiments, the list of size 50000 is called pnTable. You can download oPARTITIONS9, go into Maple, "read oPARTITIONS9: " (without the quotes), and to get, for example, p(10001) you type:
    pnTable[10001];

  • If you want to see the first 500000 (YES, half million!) values of p(n), the number of (integer) partitions of n,

    the input gives you the output. (Warning: 237MB)

    Note: the output file was slightly edited so that it can be used for computer-experiments, the list of size 500000 is called L. You can download oPARTITIONS9a, go into Maple, read oPARTITIONS9a:, and to get, for example, p(100001) you type:
    L[100001];

  • If you want to see a web-book with 36 theorems about Ramanujan-style congruences for pm(n)

    the input gives you the output.

Added May 14, 2016: If you want to see the first 29 terms of the sequence

p(11^3*13*k+237)/13

that was proved by A.O. Atkin to be integers, (see the wikipedia article on partitions), look here.


Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page