A [question](https://math.stackexchange.com/questions/326804/probability-of-two-vertices-to-be-connected-in-gn-p) 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?



Probability of two vertices to be connected in G(n,p)
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](http://www.ams.org/mathscinet-getitem?mr=0108839) (21 #7551)


