A249754 The number of ordered pairs (G,S) where G is a simple labeled graph of order n and S is a subset of the vertices of G such that every element (vertex) in S is in the same connected component of G.

1, 2, 7, 51, 814, 27562, 1881132, 252352192, 66437453648, 34544598832464, 35670629662833824, 73386908116413720320, 301341520134976454507520, 2471940307185604520086223360, 40530105576773294054842498631680, 1328619037998490196005266772240585728, 87091009170221273841091095272951672891392

Offset

0,2

Comments

Every graph paired with the empty set is included in this count. Every graph paired with a single vertex is also included.

a(n)/(2^binomial(n,2)*2^n) is the probability that a random simple labeled graph contains a random subset of its vertices in a single connected component.

Links

Table of n, a(n) for n=0..16.

Example

a(2)=7 because every such ordered pair is counted except (G,{1,2}) where G is the disconnected graph on 2 labeled nodes.

Mathematica

nn = 16; f[list_] :=
Table[Sum[list[[i, j]]*Binomial[i, j], {j, 1, i}] + list[[i, 1]], {i,
    1, Length[list]}];
a[x_] := Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn + 100}];
c[x_] := Log[a[x]]; Prepend[
f[Table[Table[
     PadLeft[Range[0, nn]! CoefficientList[
        Series[ D[c[ x], {x, n}] a[x], {x, 0, nn}], x], nn + n], {n,
      1, nn}][[All, j]], {j, 1, nn}]], 1]

Crossrefs

Sequence in context: A324513 A086902 A265042 * A224879 A345678 A279198

Adjacent sequences: A249751 A249752 A249753 * A249755 A249756 A249757

Keyword

nonn

Author

Geoffrey Critzer, Nov 04 2014

Status

approved