login
A279045
Number of pairs of vertices that share no common neighbor summed over all simple labeled graphs on n nodes.
1
0, 2, 18, 216, 4320, 155520, 10450944, 1337720832, 330225942528, 158508452413440, 148786600665415680, 274243462346494181376, 995653355660871966130176, 7136843253377130253221101568, 101189457574036357559516418539520, 2842093839245162883865914859459706880
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
Sequence in context: A153647 A052726 A217239 * A155666 A355723 A227934
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Dec 04 2016
STATUS
approved