Expected maximum number of "prank cigarettes" in an average pack "Real-life" motivation. The German satirical magazine Der Postillon suggested a few measures for deterring smokers from their bad habit. I especially liked the idea of inserting one "prank cigarette" per pack, giving the smoker a reminder in form of a (mild) explosion after lighting it. This motivated the following problem.
Problem statement. Suppose we are given $n$ empty packs of cigarettes, each to be filled with $n$ cigarettes. Amongst the $n^2$ cigarettes in total to be distributed to the $n$ empty packs, there are $n$ "prank cigarettes" to be distributed in a uniform manner into the $n$ packs.
Questions.

*

*Let $M_n$ be the expected value of the maximum number of prank cigarettes any pack receives. Is there an explicit formula for $M_n$? If not, do we have $\lim\sup_{n\to\infty}M_n/n > 0$ or  $\lim\sup_{n\to\infty}M_n/\log(n) > 0$?


*Let $E_n$ be the expected value of packs without any prank cigarettes. Is there an explicit formula for $E_n$? If not, do we have $\lim\sup_{n\to\infty}E_n/n > 0$ or  $\lim\sup_{n\to\infty}E_n/\log(n) > 0$?
 A: Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is
$$E_n = n \left( 1 - \frac{1}{n} \right)^n = e^{-1} n - O(1).$$
This gives
$$\lim_{n \to \infty} \frac{E_n}{n} = e^{-1}$$
and the other limit diverges.
The first question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer. This gives, heuristically,
$$\lim_{n \to \infty} \frac{M_n}{\frac{\log n}{\log \log n}} \stackrel{?}{=} 1$$
but quite slowly, so e.g. numerical calculations may not show this. The $W$ function estimate should be testable numerically, though.
A: $\newcommand{\Si}{\Sigma}$Let $X_n$ be the maximum number of prank cigarettes any pack receives, so that $M_n=EX_n$. Note that $X_n=\max(N_1,\dots,N_n)$, where $(N_1,\dots,N_n)$ has the multinomial distribution with parameters $n;\frac1n,\dots,\frac1n$. So, by Theorem 1 or formula (6) of Raab and Steger,
\begin{equation*}
    X_n\sim r_n:=\frac{\ln n}{\ln\ln n} \tag{1}\label{1}
\end{equation*}
in probability (as $n\to\infty$).
We will also prove

Proposition 1:
\begin{equation*}
    EX_n^2\ll r_n^2. 
\end{equation*}

(As usual, we write $A\ll B$ to mean $A=O(B)$.)
By Proposition 1 and the de la Vallée-Poussin theorem, $X_n/r_n$ is uniformly integrable, which implies

\begin{equation*}
M_n=EX_n\sim r_n  
\end{equation*}

(which agrees with Qiaochu Yuan's heuristics/conjecture).
Proof of Proposition 1:
Let $[n]:=\{1,\dots,n\}$. Note that
\begin{equation*}
    EX_n^2\ll\sum_{m\in[n]}mP(X_n\ge m)
=\Si_1+\Si_2, \tag{3}\label{3}
\end{equation*}
where
\begin{equation*}
    \Si_1:=\sum_{1\le m\le 4r_n}mP(X_n\ge m),\quad \Si_2:=\sum_{4r_n<m\le n}mP(X_n\ge m). 
\tag{4}\label{4}
\end{equation*}
It is easy to bound $\Si_1$:
\begin{equation}
        \Si_1\le\sum_{1\le m\le 4r_n}m\ll r_n^2. \tag{5}\label{5}
\end{equation}
Let us now bound $\Si_2$.
Recall that $X_n=\max(N_1,\dots,N_n)$, where $(N_1,\dots,N_n)$ has the multinomial distribution with parameters $n;\frac1n,\dots,\frac1n$. Note that for each $m\in[n]$
\begin{equation*}
    P(X_n\ge m)\le\sum_{i\in[n]}P(N_i\ge m)
    =nP(N_1\ge m).  \tag{7}\label{7}
\end{equation*}
Next, $N_1$ has the binomial distribution with parameters $n$ and $\frac1n$, and hence
\begin{equation*}
\begin{aligned}
    P(N_1\ge m)&=\sum_{k=m}^n\binom nk\frac1{n^k}\Big(1-\frac1n\Big)^{n-k} \\ 
    &\le\sum_{k=m}^n\binom nk\frac1{n^k}\le\sum_{k=m}^n\frac1{k!}\ll\frac1{m!}. 
\end{aligned}
\tag{11}\label{11}
\end{equation*}
Further, for $m>4r_n$, eventually (that is, for all large enough $n$),
\begin{equation*}
    m!\ge(m/e)^m=\exp(m\ln(m/e)) \\ 
    \ge\exp\Big(4\frac{\ln n}{\ln\ln n}\,\ln\frac{\ln n}{\ln\ln n}\Big)\ge n^3. \tag{13}\label{13}
\end{equation*}
So, by \eqref{4}, \eqref{7}, \eqref{11}, and \eqref{13},
\begin{equation*}
    \Si_2\le\sum_{4r_n<m\le n}mnP(N_1\ge m) \\ 
    \ll\sum_{4r_n<m\le n}mn\frac1{n^3}\le1\ll r_n^2. \tag{15}\label{15}
\end{equation*}
Now Proposition 1 follows immediately from \eqref{3}, \eqref{5}, and \eqref{15}. $\quad\Box$

Quite similarly one can show that
\begin{equation*}
EX_n^p\sim r_n^p    
\end{equation*}
for each real $p>0$.
