|
|
A281263
|
|
Number of ordered pairs (G,S), where G is a simple labeled graph on n nodes and S is a subset of the vertices of G, such that G[S], the subgraph of G induced by S, is connected.
|
|
1
|
|
|
1, 2, 7, 48, 678, 20152, 1261136, 164218384, 43821994928, 23658787655424, 25616559766429056, 55340791084814653184, 237922643333653801371136, 2033513411062585410717731840, 34548374878763336687563800988672, 1167171416692672748287791275387179008
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The null graph is considered to be a connected graph.
a(n)/(2^n * 2^binomial(n,2)) is the probability that a random subset of vertices chosen from a random graph will induce a connected subgraph. This probability is a minimum at n=7 and approaches 1 as n gets big.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{j=0..n} A001187(j)/2^binomial(j,2) * binomial(n,j) * 2^binomial(n,2).
|
|
MATHEMATICA
|
nn = 15; A[z_] := Sum[2^Binomial[n, 2] z^n/n!, {n, 0, nn}]; list = Range[0, nn]! CoefficientList[Series[Log[A[z]] + 1, {z, 0, nn}], z]; Table[ Sum[list[[i]]/2^Binomial[i - 1, 2] Binomial[n, i - 1] 2^ Binomial[n, 2], {i, 1, Length[list]}], {n, 0, nn}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|