Partition numbers and Ramanujan’s approximation
The partition function p(n) counts the number of ways n unlabeled things can be partitioned into non-empty sets. (Contrast with Bell numbers that count partitions of labeled things.)
There's no simple expression for p(n), but Ramanujan discovered a fairly simple asymptotic approximation:
How accurate is this approximation? Here's a little Matheamtica code to see.
p[n_] := PartitionsP[n]approx[n_] := Exp[ Pi Sqrt[2 n/3]] / (4 n Sqrt[3])relativeError[n_] := Abs[p[n] - approx[n]]/p[n]ListLinePlot[Table[relativeError[n], {n, 100}]]
So for values of n around 100, the approximation is off by about 5%.
Since it's an asymptotic approximation, the relative error decreases (albeit slowly, apparently) as n increases. The relative error for n = 1,000 is about 1.4% and the relative error for n = 1,000,000 is about 0.044%.
Update: After John Baez commented on the oscillation in the relative error I decided to go back and look at it more carefully. Do the oscillations end or do they just become too small to see?
To answer this, let's plot the difference in consecutive terms.
relerr[a_, b_] := Abs[a - b]/bt = Table[relerr[p[n], approx[n]], {n, 300}];ListLinePlot[Table[ t[[n + 1]] - t[[n]], {n, 60}]]
The plot crosses back and forth across the zero line, indicating that the relative error alternately increases and decreases, but only up to a point. Past n = 25 the plot stays below the zero line; the sign changes in the first differences stop.
But now we see that the first differences themselves alternate! We can investigate the alternation in first differences by plotting second differences [1].
ListLinePlot[ Table[ t[[n + 2]] - 2 t[[n + 1]] + t[[n]], {n, 25, 120}]]
So it appears that the second differences keep crossing the zero line for a lot longer, so far out that it's hard to see. In fact the second differences become positive and stay positive after n = 120. But the second differences keep alternating, so you could look at third differences "
Related posts: Special numbers
[1] The code does a small algebraic simplification that might make some people scratch their heads. All it does is simplify
(tn+2 - tn+1) - (tn+1 - tn).