A question I asked at math.SE without elliciting an answer.
Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed (distinct) vertices $u,v$ lie in the same connected component of $G(n,p)$?
I'm familiar with the standard asymptotic results about connected components in Erdős–Rényi graphs but was unable to find explicit results for $P_{n,p}$ for finite $n$. I expect these probabilities to be polynomials in $p$ of degree $n(n-1)/2$ but did not succeed in determining the coefficients for general $n$ and $p$.
I fed the values of $P_{n,1/2}$, for $n=2,3,4,5$, into OEIS, but did not obtain a match.
Edit (14 March 2014)
After Brendan McKay's helpful comment, I found the formula
$$
R_n(p) = \sum_{j=1}^{n-1}{\binom{n-1}{j-1}(1-p)^{j(n-j)}R_j(p)},\quad R_1(p)=1,
$$
for the all-terminal reliability polynomial $R_n$ of the complete graph on $n$ vertices (i.e. the probability that the graph remains connected after deleting edges with probability $p$) and the formula
$$
T_n(p) = \sum_{j=2}^{n}{\binom{n-2}{j-2}(1-p)^{j(n-j)}R_j(p)}
$$
for the 2-terminal reliability polynomial (i.e. the probability that vertices 1 and 2 are in the same connected component after deleting edges with probability $p$).
The experimentalist that I am, I used the first recursion to compute $R_n$ for a few values of $n$ and tried to guess a pattern for its coefficients.
What I found is that $\frac{R_n(1-p)}{(1-p)^{n-1}}$ is a polynomial of degree $(n-2)(n-1)/2$ and that the coefficients of its monomials with small exponent seem to be given by
$$
[p^i]\frac{R_n(1-p)}{(1-p)^{n-1}} = \color{blue}{\binom{n-2+i}{n-2},\quad i=0,1,\ldots,n-2}.\tag{*}
$$
For the monomials with large exponents there appear to exist polynomials $\mathfrak{p}_j$ of degree $j$ such that, for $\color{green}{i=\frac{(n-2)(n-1)}{2}-n+1,\ldots,\frac{(n-2)(n-1)}{2}}$,
$$
[p^i]\frac{R_n(1-p)}{(1-p)^{n-1}}=\color{green}{\frac{(n-1)!}{\left[2\left(\frac{(n-2)(n-1)}{2}-i\right)\right]!!}\mathfrak{p}_{\frac{(n-2)(n-1)}{2}-i}(n)},\tag{**}
$$
where !! denotes the double factorial.
The first few polynomials $\mathfrak{p}_j$ appear to be given by
$$
\begin{array}{c|c}
j&\mathfrak{p}_j\\\hline
0 & 1 \\
1 & n-2\\
2 & n^2-3 n\\
3 & n^3-3 n^2-2 n\\
4 & n^4-2 n^3-5 n^2-18 n\\
5 & n^5-5 n^3-80 n^2+4 n\\
6 & n^6+3 n^5+5 n^4-195 n^3-86 n^2-848 n\\
7 & n^7+7 n^6+35 n^5-315 n^4-476 n^3-6132 n^2+160 n
\end{array}
$$
The leading coefficients seems to be one; the next-to-leading coefficient in $\mathfrak{p}_j$, i.e. $[p^{j-1}]\mathfrak{p}_j$, appears (tentatively) to be given by $j(j-5)/2$. I haven't had a chance to look at the other coefficients yet.
Unfortunately, the two formulas (*) and (**) cover only a small proportion of the quadratically many coefficients of $\frac{R_n(1-p)}{(1-p)^{n-1}}$, as indicated in the next coefficient table.
$$
\scriptsize{
\begin{array}{c|cccccccccccccccccccccc}
n,i & 0 & 1 & 2 & \ldots\\\hline
2 & \color{blue} 1\\
3 & \color{blue} 1 & \color{blue}2\\
4 & \color{blue} 1 & \color{blue}3 & \color{blue}6 & \color{green}6\\
5 & \color{blue}1 & \color{blue}4 & \color{blue}{10} & \color{blue}{20} & \color{green}{30} & \color{green}{36} & \color{green}{24}\\
6 & \color{blue}{1} & \color{blue}{5} & \color{blue}{15} & \color{blue}{35} & \color{blue}{70} & \color{green}{120} & \color{green}{180} & \color{green}{240} & \color{green}{270} & \color{green}{240} & \color{green}{120}\\
7 & \color{blue}{1} & \color{blue}{6} & \color{blue}{21} & \color{blue}{56} & \color{blue}{126} & \color{blue}{252} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{green}{1610} & \color{green}{2100} & \color{green}{2520} & \color{green}{2730} & \color{green}{2520} & \color{green}{1800} & \color{green}{720}\\
8 & \color{blue}{1} & \color{blue}{7} & \color{blue}{28} & \color{blue}{84} & \color{blue}{210} & \color{blue}{462} & \color{blue}{924} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{green}{24640} & \color{green}{29400} & \color{green}{32970} & \color{green}{34230} & \color{green}{31920} & \color{green}{25200} & \color{green}{15120} & \color{green}{5040}
\end{array}
}
$$
Up to $n=6$, the reliability polynomial of $K_n$ is correctly computed by (*) and (**) but beyond that a growing chunk of coefficients is missing in the middle.
Questions:
What are the polynomials $\mathfrak{p}_j$? How can one compute the $\color{red}?$ coefficients?
Best Answer
Explicit expressions for the all-terminal reliabilty were established back in 1959 by Gilbert.
Gilbert, E. N. Random graphs. Ann. Math. Statist. 30 1959 1141--1144. MR0108839 (21 #7551)