|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|