Let $\mathcal{A}=\{A\_1, A\_2, \ldots, A\_m\}$ be a uniformly random set partition of $[n]$.


What can we say about $||\mathcal{A}||\_2 = \sqrt{\sum\_{i=1}^m |A\_i|^2}$? It is clearly upper bounded by $n$, but since the ``typical'' size of these $A\_i$ is more like $\log(n) - \log\log(n)$, it seems reasonable to expect that $||\mathcal{A}||\_2$ is actually more like $O\left(\sqrt{n\log(n)}\right)$, or something like that. What I really need is two things: a) whether $||\mathcal{A}||\_2$ concentrates around its expectation, and b) upper bounds on $\mathbb{E}\left[||\mathcal{A}||\_2\right]$ better than the trivial $n$ bound.


In my search for papers on this topic, I've found the following result: If $Z\_i = |\{j: |A\_j| = i\}|$ is the number of parts of size $i$, then the vector $(Z\_1, Z\_2, \ldots, Z\_n)$ is distributed as $Z\_i \sim \mathrm{Po}\left(\frac{r^i}{i}\right)$ (where $r=r(n)$ is defined by $re^r = n$), independent other than for conditioning on $\sum\_i iZ\_i = n$. So my question could equivalently be phrased as asking about
$$\mathbb{E}\left[\sqrt{\sum\_i i^2 Z\_i}\, \middle|\, \sum\_i i Z\_i = n \right]$$
but it's not clear to me if that is any easier than the original question.



"Shape"/"norm" of a uniformly random set partition
Since $E[\|\mathcal{A}\|\_{2}^{2}]$ has no square roots, a good strategy for this problem will be to first compute $E[\|\mathcal{A}\|\_{2}^{2}]$ and then deal with $E[\|\mathcal{A}\|\_{2}]$ only after we are comfortable with $E[\|\mathcal{A}\|\_{2}^{2}]$.


We compute $$E[\|\mathcal{A}\|\_{2}^{2}]=B\_{n}^{-1}\sum\_{P\in\mathbb{P}([n])}\sum\_{R\in P}|R|^{2}=B\_{n}^{-1}\sum\_{R\subseteq[n]}\sum\_{P\in\mathbb{P}([n]),R\in P}|R|^{2}$$
$$=B\_{n}^{-1}\sum\_{R\subseteq[n],R\neq\emptyset}|R|^{2}\cdot B\_{n-|R|}=B\_{n}^{-1}\cdot\sum\_{k=1}^{n}\binom{n}{k}B\_{n-k}k^{2}.$$


Here $\mathbb{P}([n])$ denotes the lattice of partitions of $[n]$ while $B\_{r}$ denotes the $r$-th Bell number.


We now look up $B\_{n}\cdot E[\|\mathcal{A}\|\_{2}^{2}]$ from the OEIS, and this is sequence [A175716](https://oeis.org/A175716), and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value of the norm squared
$$B\_{n}\cdot E[\|\mathcal{A}\|\_{2}^{2}]=n\big{[}(n-1)B\_{n-1}+B\_{n}\big{]}.$$


By Jensen's inequality (or the formula of the variance), we have $E[\|\mathcal{A}\|\_{2}]^{2}\leq E[\|\mathcal{A}\|\_{2}^{2}],$ so
$$E[\|\mathcal{A}\|\_{2}]\leq\sqrt{n[1+(n-1)B\_{n-1}B\_{n}^{-1}]}.$$


For a lower bound of $E[\|\mathcal{A}\|\_{2}]$, we have
$\|\mathcal{A}\|\_{2}\geq\frac{n}{\sqrt{m}}$ where $|\mathcal{A}|=m$. Therefore, by Jensen's inequality, we have
$$E(\|\mathcal{A}\|\_{2})\geq E(\frac{n}{\sqrt{m}})\geq\frac{n}{\sqrt{E(m)}}.$$


However, we know that $E(m)=(B\_{n+1}/B\_{n})-1$.


Therefore, $$\frac{n}{\sqrt{(B\_{n+1}/B\_{n})-1}}\leq E(\|\mathcal{A}\|\_{2})\leq\sqrt{n[1+(n-1)B\_{n-1}B\_{n}^{-1}]}.$$


We therefore conclude that
$$\text{Var}(\|\mathcal{A}\|\_{2})=E(\|\mathcal{A}\|\_{2}^{2})-E(\|\mathcal{A}\|)^{2}\leq n[1+(n-1)B\_{n-1}B\_{n}^{-1}]-\frac{n^{2}}{(B\_{n+1}/B\_{n})-1}.$$


We can therefore conclude that $\|\mathcal{A}\|\_{2}$ does concentrate around its expected value.


