I'm wondering if there's a known asymptotic for an average number of terms for partitions of a given number? (I mean, given all the partitions of a given number, how many terms do they have on average?)


This was apparently answered in 1941 by Erdos and Lehner see here; however, I only have access to a 1995 paper by Fristedt, which cites the result as (2.2):

$$\lim_{n\to\infty} P_n \left(\frac{\pi}{\sqrt{6n}} Y_1 - \log \frac{\sqrt{6n}}{\pi}\le v\right)=e^{-e^{-v}}$$

Here, $P_n$ denotes probability measure, with all partitions of $n$ equiprobable. $Y_1$ denotes the size of the largest part of a partition. By considering conjugation, the average size of the largest part of a partition equals the average number of parts of a partition.

More details, by request. This formula gives more than just the average of $Y_1$, it gives a lot of information about the probability distribution of $Y_1$. For example, taking $v=0$, we get $Y_1 \le \frac{\sqrt{6n}}{\pi} \log \frac{\sqrt{6n}}{\pi}$ with limiting probability $e^{-1}\approx 0.37$. Taking instead $v=2$, we get $Y_1\le 2\frac{\sqrt{6n}}{\pi}+ \frac{\sqrt{6n}}{\pi}\log \frac{\sqrt{6n}}{\pi}$ with probability $e^{-e^{-2}}\approx 0.87$. Hence, subtracting, we get $$Y_1\in \left[\frac{\sqrt{6n}}{\pi}\log \frac{\sqrt{6n}}{\pi},2\frac{\sqrt{6n}}{\pi}+ \frac{\sqrt{6n}}{\pi}\log \frac{\sqrt{6n}}{\pi}\right]$$ with probability $e^{-e^{-2}}-e^{-e^{-0}}\approx 0.51$.

If you just want the answer to the original question, it is $$Y_1=O\left(\frac{\sqrt{6n}}{\pi}\log \frac{\sqrt{6n}}{\pi}\right)=O(\sqrt{n}\log n)$$

  • $\begingroup$ Could you please explain how this translates into asymptotics for $n\propto\ldots$? Should I solve the inequality for $Y_1$, replacing $v$ with $n/2$?.. $\endgroup$ – mavzolej Apr 7 at 12:55
  • $\begingroup$ Thank you so much!! $\endgroup$ – mavzolej Apr 7 at 20:13

Here is a graph of the average number of partitions as a function of the source number:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.