login
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.
2
1, 2, 7, 48, 678, 20152, 1261136, 164218384, 43821994928, 23658787655424, 25616559766429056, 55340791084814653184, 237922643333653801371136, 2033513411062585410717731840, 34548374878763336687563800988672, 1167171416692672748287791275387179008
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
Sequence in context: A317666 A316567 A304968 * A206153 A326338 A119668
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Apr 12 2017
STATUS
approved