= Solution
Count each unordered triple once. For a three-element <vertex set> $S$, let $I_S$ indicate that its three <edges> are present. Then $X=\sum_{|S|=3}I_S$ and
$$
\mathbb E X^2=\sum_{S,T}\mathbb E[I_SI_T].
$$
If $|S\cap T|=\ell$, their edge sets have $\binom\ell2$ edges in common, so their union contains $6-\binom\ell2$ distinct <edges>. Independence gives $\mathbb E[I_SI_T]=p^{6-\binom\ell2}$. There are $\binom n3\binom3\ell\binom{n-3}{3-\ell}$ such ordered pairs: choose $S$, its shared vertices, and the remaining vertices of $T$. Thus
$$
\boxed{\mathbb E X^2=
\binom n3\sum_{\ell=0}^3
\binom3\ell\binom{n-3}{3-\ell}
p^{6-\binom\ell2}}.
$$
This overlap count is the basis of <triangle variance in a binomial random graph>.
Back to article page
