Page 24 -

II
The Partition Function

One of the simplest, most natural, questions one can ask in arithmetic
is how to determine the number of ways of breaking up a given inte-
ger. That is, we ask about a positive integer n: In how many ways can
it be written as a + b + c + ··· where a,b,c,... are positive inte-
gers? It turns out that there are two distinct questions here, depending
on whether we elect to count the order of the summands. If we do
choose to let the order count, then the problem becomes too simple.
The answer is just 2 n−1 and the proof is just induction. Things are
incredibly different and more complicated if order is not counted!
In this case the number of breakups or “partitions” is 1 for n 1,
2 for n 2, 3 for n 3, 5 for n 4, 7 for n 5, e.g., 5 has the
representations 1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 3 + 1 + 1, 4 + 1,
5, 3 + 2, 2 + 2 + 1, and no others. Remember such expressions
as 1 + 1 + 2 + 1 are not considered different. The table can be
extended further of course but no apparent pattern emerges. There
is a famous story concerning the search for some kind of pattern in
this table. This is told of Major MacMahon who kept a list of these
partition numbers arranged one under another up into the hundreds.
It suddenly occurred to him that, viewed from a distance, the outline
of the digits seemed to form a parabola! Thus the number of digits
√
in p(n), the number of partitions of n, is around C n,or p(n) itself
√
is very roughly e α n . The first crude assessment of p(n)!
Among other things, however, this does tell us not to expect any
simpleanswers.Indeedlaterresearchshowedthatthetrueasymptotic
√ 2n/3
π
formula for p(n) is e √ , certainly not a formula to be guessed!
4 3n

17