On the maximal multiplicity of block sizes in a random set partition

Abstract

We study the asymptotic behavior of the maximal multiplicity $M_n=M_n(\sigma )$ of the blocks in a set partition of $[n]=\{1,2,...,n\}$, assuming that $\sigma$ is chosen uniformly at random from the set of all such partitions. Let $W=W(n)$ be the unique positive root of the equation $W{e}^W=n$ and let $f_n$ be the fractional part of $W(n)$. Furthermore, let $R_n=W^{\lfloor W\rfloor }/\lfloor W\rfloor !$ and let ${\vartheta }_n=\min \{f_n,1-f_n\}$. We show that, over a subsequence $\{n_k{\}}_{k\ge 1}$, $(M_{n_k}-R_{n_k})/\sqrt{R_{n_k}}$ converges weakly, as $k\to \infty$, to $\max \{Z_1,Z_2-u\}$, where $Z_1$ and $Z_2$ are two independent copies of a standard normal random variable and either $u={\left(\frac{1}{2\pi }\right)}^{1/4}{\lim }_{k\to \infty }{\vartheta }_{n_k}\frac{\sqrt{n_k}}{{\log }^{7/4}{n}_k}\in [0,\infty )$ or $u=\infty$. The proof uses the saddle point method. A comparison with the similar statistic for random integer partitions of $n$ is also given.

27 pages