= Tree-component expectation in the Erdős-Rényi model
{title2=$\mathbb EX_j=\binom njj^{j-2}p^{j-1}(1-p)^{j(n-j)+\binom j2-j+1}$}
For $X_j$ the number of <tree components> of order $j$ in a <binomial random graph>, choose their <vertices>, choose one of $j^{j-2}$ labelled <trees> by the <Cayley formula>, require its $j-1$ <edges>, and exclude both the remaining internal <edges> and all crossing <edges>. For $j=1$ interpret $j^{j-2}=1$, recovering the <isolated vertex> count. If $p=\lambda/n$ for fixed positive $\lambda$ and $j=O(\log n)$, the <Stirling formula> gives $\mathbb EX_j\sim n(\lambda e^{1-\lambda})^j/(\lambda\sqrt{2\pi}\,j^{5/2})$. Distinct overlapping vertex sets cannot both be <graph components>; for disjoint sets their joint occurrence gains the factor $(1-p)^{-j^2}$ relative to the product, because their between-set <edges> must be absent only once.
Back to article page
