# "Shape"/"norm" of a uniformly random set partition

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.

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, 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.

• Are you sure that OEIS sequence is the right one? It looks like you've got a $k^2$ in your identity and the linked sequence has a $k$. Sep 13 at 15:14
• @MarcusM Thanks for spotting that. The correct link should be oeis.org/A175716. These are closely related sequences since A175716(n) = n*A124427(n), so I must have put the wrong sequence in the clipboard. Sep 13 at 15:25
• Are you sure about that? You should double check your answer; if you make that edit then you'd end up with $E [|A|^2 ] = \Theta (n^2 )$, which doesn't seem like the right order. Sep 14 at 13:05
• I just verified these identities with code that produces the exact same sequence in 3 different ways. Here is the code in GAP. par:=[]; par:=[[]]; for n in [2..10] do par[n]:=[]; for a in par[n-1] do Add(par[n],Concatenation(a,[[n]])); for i in [1..Length(a)] do aa:=StructuralCopy(a); Add(aa[i],n); Add(par[n],aa); od; od; od; mak:=function(xx) return Sum(List(xx,v->Length(v)^2)); end; List(par,v->Sum(List(v,mak))); moo:=function(n) return Sum(List([1..n],k->Binomial(n,k)*Bell(n-k)*k^2)); end; List([1..10],moo); List([1..n],v->v*((v-1)*Bell(v-1)+Bell(v))); Sep 14 at 14:23