OFFSET
1,2
COMMENTS
a(n)/2^binomial(n,2) is the expected number of pairs of vertices in a simple labeled graph on n nodes that share no common neighbor. This expectation approaches 0 as n gets big. Hence almost all graphs have diameter 2.
REFERENCES
D. B. West, Introduction to Graph Theory, Pearson, 2015, page 432.
LINKS
Georg Fischer, Table of n, a(n) for n = 1..80 [corrected; first 29 terms by Indranil Ghosh]
FORMULA
a(n) = 2^binomial(n, 2)*binomial(n, 2)*(1 - (1/2)^2)^(n - 2).
EXAMPLE
a(3)=18. There are 3 such pairs of vertices in the empty graph. There are 3 pairs in each of the 3 labelings of the graph with one edge. There are 2 pairs in each of the 3 labelings of the path of length two. 3 + 3*3 + 2*3 = 18.
MATHEMATICA
Table[2^Binomial[n, 2] Binomial[n, 2] (1 - (1/2)^2)^(n - 2), {n, 1, 15}]
PROG
(Magma) [2^Binomial(n, 2)*Binomial(n, 2)*(1-(1/2)^2)^(n-2): n in [1..20]]; // Vincenzo Librandi, Dec 08 2016
(PARI) a(n) = 2^binomial(n, 2)*binomial(n, 2)*(1-(1/2)^2)^(n-2) \\ Indranil Ghosh, Feb 25 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Dec 04 2016
STATUS
approved