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, 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

Alois P. Heinz, Table of n, a(n) for n = 0..81

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

Cf. A001187, A249754.

Sequence in context: A317666 A316567 A304968 * A206153 A326338 A119668

Adjacent sequences: A281260 A281261 A281262 * A281264 A281265 A281266

Keyword

nonn

Author

Geoffrey Critzer, Apr 12 2017

Status

approved