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

combinatoricsdiscrete mathematicsinteger-partitionsnumber theoryprobability theory

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)$.

Best Answer

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 ([1]) which states that ([2], 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

Related Question