# Expected Value for the Number of Parts of a Random Partition (Considering Only a Portion of the Partition Spectrum)

Let $$n$$ be a positive integer. If we take the set of all partitions of $$n$$ and choose a random partition from it (uniformly), then the expected value of the number of parts of this partition is a known result. The highest order term of the expected value is $$\sqrt{n}\operatorname{Log}(n)$$ (Kessler & Livingston, 1976).

Instead of the set of all partitions of $$n$$, I only want to consider $$k \%$$ of the total spectrum of partitions. Let $$P^k(n)$$ denote the set which contains $$k \%$$ of the total partitions of $$n$$. The partitions in $$P^k(n)$$ are chosen as follows. We begin with the empty set and add partitions one by one. At every step we choose to add a partition that has the smallest number of parts. We stop adding partitions once the set $$P^k(n)$$ contains the required $$k \%$$ of the total number of partitions.

I am interested in the partition in $$P^k(n)$$ that has the highest number of parts, call this $$max\left(P^k(n)\right)$$. Numerical experiment has shown that for large $$n$$, $$\operatorname{max}\left(P^k(n)\right) \approx k \sqrt{n}\operatorname{Log}(nk)$$. So for fixed $$k$$ and increasing $$n$$ we get $$\operatorname{max}\left(P^k(n)\right) = \mathcal{O}(\sqrt{n}\operatorname{Log}(n))$$.

Is there a way to apply Kessler and Livingston's result to the set $$P^k(n)$$, so that we get the expected value for the number of parts of partitions in that set? This would be incredibly helpful as it would be a lower bound for $$\operatorname{max}\left(P^k(n)\right)$$.

• You can get the proper font and spacing for $\max$ and $\log$ using \max and \log. For operators that don't have a command of their own, you can use \operatorname{name}. – joriki Apr 24 at 2:12
• Apparently you mean the 1976 paper "The Expected Number of Parts of a Partition of $n$"? This is available online here. – joriki Apr 24 at 2:19
• Excuse me if this is a silly question -- I am new to this. :) Let $X =$ the number of parts in a random partition. Then 1976 result is about the mean $E[X]$, while you're asking about the $k$-th percentile for a fixed $k$, am I right? The 1976 paper (which I only vaguely understand) seems to use a standard technique of differentiating a generating function to find the mean. Is there a similar technique for percentile statistics? Nothing comes to my mind but I'm a newbie at generating functions. – antkam Apr 28 at 17:45
• [cont'd] Alternatively, are there known theories about families of distributions (indexed by $n$ here) s.t. the growth (w.r.t. $n$) of the mean is similar to the growth of the $k$th percentile? E.g. consider the family $Binomial(n,p)$ - because of CLT, the leading terms are both linear. – antkam Apr 28 at 17:51
• If the bounty expires without a good answer, let me suggest posting the question to mathoverflow.net – Gerry Myerson May 5 at 3:46

It is known that the number of partitions of $$n$$ with largest part $$k$$ is the same as the number of partitions into $$k$$ parts (see e.g. here). Thus we can translate your question into asking about the size of the largest part of a (uniform) random partition. The asymptotic distribution of the largest part is given by the Erdős Lehner theorem () which states that (, equation 2.2)

$$\begin{equation} \lim_{n\rightarrow\infty}P_n(\lambda \in \mathcal{P}_n : \frac{c}{\sqrt{n}}\lambda_1 − \log \frac{\sqrt{n}}{c}\leq x) = e^{−e^{−x}} \end{equation}$$, where $$c=\frac{\pi}{\sqrt{6}}$$.

Here $$\mathcal{P}_n$$ is the set of partitions of $$n$$, $$P_n$$ the uniform measure on $$\mathcal{P}_n$$, elements (partitions) of $$\mathcal{P}_n$$ are denoted by $$\lambda$$ ,and $$\lambda_1$$ denotes the largest part of $$\lambda$$. As an aside, this limiting distribution is known as the Gumbel distribution.

In particular, if we let $$\lambda_1^{(k)}$$ denote the largest part of the $$k$$th percentile partition (ordered in increasing order of largest part), set $$e^{-e^{-x}} = k$$, solve for $$x$$ and then for $$\lambda_1$$ using $$\frac{c}{\sqrt{n}}\lambda_1 − \log \frac{\sqrt{n}}{c} = x$$, we get $$x = \log (\frac{1}{\log (1/k)})$$ and $$\lambda_1^{(k)} = \frac{\sqrt{n}}{c}\log (\frac{\sqrt{n}}{c\log (1/k)})$$.

References:

1. P. Erdős, J. Lehner: The distribution of the number of summands in the partition of a positive integer. Duke Math. J. Vol. 8 (1941)

2. Zhonggen Su: Asymptotic analysis of random partitions