login
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

%I #4 Nov 04 2014 22:49:15

%S 1,2,7,51,814,27562,1881132,252352192,66437453648,34544598832464,

%T 35670629662833824,73386908116413720320,301341520134976454507520,

%U 2471940307185604520086223360,40530105576773294054842498631680,1328619037998490196005266772240585728,87091009170221273841091095272951672891392

%N 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.

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

%C 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.

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

%t nn = 16; f[list_] :=

%t Table[Sum[list[[i, j]]*Binomial[i, j], {j, 1, i}] + list[[i, 1]], {i,

%t 1, Length[list]}];

%t a[x_] := Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn + 100}];

%t c[x_] := Log[a[x]]; Prepend[

%t f[Table[Table[

%t PadLeft[Range[0, nn]! CoefficientList[

%t Series[ D[c[ x], {x, n}] a[x], {x, 0, nn}], x], nn + n], {n,

%t 1, nn}][[All, j]], {j, 1, nn}]], 1]

%K nonn

%O 0,2

%A _Geoffrey Critzer_, Nov 04 2014